La forma más rápida de calcular la suma de bits en el conjunto de bytes

Question

Tengo dos matrices de bytes con la misma longitud. Necesito realizar la operación XOR entre cada byte y luego calcular la suma de bits.

Por ejemplo:

11110000^01010101 = 10100101 -> so 1+1+1+1 = 4 

Necesito hacer la misma operación para cada elemento de matriz de bytes.

Answer 1

Utilice una tabla de búsqueda. Solo hay 256 valores posibles después de XORing, por lo que no va a llevar mucho tiempo. Sin embargo, a diferencia de la solución de izb, no recomendaría poner todos los valores en su sitio manualmente: calcule la tabla de búsqueda una vez al inicio usando una de las respuestas de bucle.

Por ejemplo:

public static class ByteArrayHelpers 
{ 
    private static readonly int[] LookupTable = 
     Enumerable.Range(0, 256).Select(CountBits).ToArray(); 

    private static int CountBits(int value) 
    { 
     int count = 0; 
     for (int i=0; i < 8; i++) 
     { 
      count += (value >> i) & 1; 
     } 
     return count; 
    } 

    public static int CountBitsAfterXor(byte[] array) 
    { 
     int xor = 0; 
     foreach (byte b in array) 
     { 
      xor ^= b; 
     } 
     return LookupTable[xor]; 
    } 
} 

(Usted podría que sea un método de extensión, si realmente quería ...)

Nota el uso de byte[] en el método CountBitsAfterXor - que podía hágala IEnumerable<byte> para más generalidad, pero iterar sobre una matriz (que se sabe que es una matriz en tiempo de compilación) será más rápida. Probablemente sólo microscópicamente más rápido, pero bueno, en que pidió la manera más rápida :)

Me es casi seguro que en realidad expresarla como

public static int CountBitsAfterXor(IEnumerable<byte> data) 

en la vida real, sino ver qué funciona mejor para usted .

También tenga en cuenta el tipo de la variable xor como int. De hecho, no hay ningún operador XOR definido para los valores byte, y si hizo xor un byte aún se compilaría debido a la naturaleza de los operadores de asignación compuesta, pero estaría realizando un molde en cada iteración, al menos en el IL.Es muy posible que el JIT se ocupe de esto, pero no hay necesidad de preguntárselo :)

Answer 2

Lo que sigue debe hacer

int BitXorAndSum(byte[] left, byte[] right) { 
    int sum = 0; 
    for (var i = 0; i < left.Length; i++) { 
    sum += SumBits((byte)(left[i]^right[i])); 
    } 
    return sum; 
} 

int SumBits(byte b) { 
    var sum = 0; 
    for (var i = 0; i < 8; i++) { 
    sum += (0x1) & (b >> i); 
    } 
    return sum; 
} 

Answer 3

Según entendí que desea sumar los bits de cada XOR entre los bytes izquierdo y derecho.

for (int b = 0; b < left.Length; b++) { 
    int num = left[b]^right[b]; 
    int sum = 0; 

    for (int i = 0; i < 8; i++) { 
    sum += (num >> i) & 1; 
    } 

    // do something with sum maybe? 
} 

Answer 4

No estoy seguro de si quiere decir suma de bytes o bits. para sumar los bits dentro de un byte, esto debería funcionar:

int nSum = 0; 
for (int i=0; i<=7; i++) 
{ 
    nSum += (byte_val>>i) & 1; 
} 

A continuación, se necesitaría la operación XOR, y la matriz de bucle alrededor de esto, por supuesto.

Answer 5

manera más rápida, probablemente sería una tabla de consulta de 256 elementos ...

int[] lut 
{ 
    /*0x00*/ 0, 
    /*0x01*/ 1, 
    /*0x02*/ 1, 
    /*0x03*/ 2 
    ... 
    /*0xFE*/ 7, 
    /*0xFF*/ 8 
} 

por ejemplo,

11110000^01010101 = 10100101 -> lut[165] == 4 

Answer 6

Esto se conoce comúnmente como conteo de bits. Hay literalmente docenas de algoritmos diferentes para hacer esto. Here es un sitio que enumera algunos de los métodos más conocidos. Incluso hay instrucciones específicas de CPU para hacer esto.

Teóricamente, Microsoft podría agregar una función BitArray.CountSetBits que obtiene JIT con el mejor algoritmo para esa arquitectura de CPU. Yo, por mi parte, agradecería tal adición.

Answer 7

una función general para contar los bits podrían ser:

int Count1(byte[] a) 
{ 
    int count = 0; 
    for (int i = 0; i < a.Length; i++) 
    { 
    byte b = a[i]; 
    while (b != 0) 
    { 
     count++; 
     b = (byte)((int)b & (int)(b - 1)); 
    } 
    } 
    return count; 
} 

Cuanto menos bits 1, más rápido funciona esto. Simplemente pasa por encima de cada byte y alterna el 1 bit más bajo de ese byte hasta que el byte se convierte en 0. Las fundiciones son necesarias para que el compilador deje de quejarse sobre el tipo de ampliación y estrechamiento.

Su problema, entonces podría resolverse mediante el uso de esto:

int Count1Xor(byte[] a1, byte[] a2) 
{ 
    int count = 0; 
    for (int i = 0; i < Math.Min(a1.Length, a2.Length); i++) 
    { 
    byte b = (byte)((int)a1[i]^(int)a2[i]); 
    while (b != 0) 
    { 
     count++; 
     b = (byte)((int)b & (int)(b - 1)); 
    } 
    } 
    return count; 
} 

Answer 8

Se puede reescribirse como ulong y utilizar unsafe puntero, pero byte es más fácil de entender:

static int BitCount(byte num) 
{ 
    // 0x5 = 0101 (bit) 0x55 = 01010101 
    // 0x3 = 0011 (bit) 0x33 = 00110011 
    // 0xF = 1111 (bit) 0x0F = 00001111 
    uint count = num; 
    count = ((count >> 1) & 0x55) + (count & 0x55); 
    count = ((count >> 2) & 0x33) + (count & 0x33); 
    count = ((count >> 4) & 0xF0) + (count & 0x0F); 
    return (int)count; 
} 

Answer 9

una tabla de consulta debe sea ​​el más rápido, pero si quiere hacerlo sin una tabla de búsqueda, esto funcionará para bytes en solo 10 operaciones.

public static int BitCount(byte value) { 
    int v = value - ((value >> 1) & 0x55); 
    v = (v & 0x33) + ((v >> 2) & 0x33); 
    return ((v + (v >> 4) & 0x0F)); 
} 

Esta es una versión byte de la función general de recuento de bits descrito en Sean Eron Anderson's bit fiddling site.