Il modo più veloce per calcolare la somma di bit nell'array di byte

Question

Ho due array di byte con la stessa lunghezza. Ho bisogno di eseguire l'operazione XOR tra ogni byte e dopo questo calcolare la somma dei bit.

Ad esempio:

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

devo fare la stessa operazione per ogni elemento dell'array di byte.

Answer 1

Utilizzare una tabella di ricerca. Ci sono solo 256 valori possibili dopo XORing, quindi non ci vorrà molto tempo. A differenza della soluzione di izb, tuttavia, non suggerirei di inserire manualmente tutti i valori: calcolare la tabella di ricerca una volta all'avvio utilizzando una delle risposte di loop.

Ad esempio:

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]; 
    } 
} 

(È potrebbe renderlo un metodo di estensione se si voleva davvero ...)

Nota l'uso della byte[] nel metodo CountBitsAfterXor - si poteva renderlo un IEnumerable<byte> per maggiore generalità, ma l'iterazione su un array (che è noto per essere un array in fase di compilazione) sarà più veloce. Probabilmente solo al microscopio più veloce, ma hey, avete chiesto il modo più veloce :)

avrei quasi certamente realtà esprimerlo come

public static int CountBitsAfterXor(IEnumerable<byte> data) 

nella vita reale, ma vedere quale funziona meglio per voi .

Nota anche il tipo della variabile xor come int. Infatti, non esiste un operatore XOR definito per i valori byte e, se è stato effettuato xor a byte, esso si compilerebbe comunque a causa della natura degli operatori di assegnazione composti, ma eseguirà un cast su ciascuna iterazione, almeno nell'IL.È possibile che la JIT si occupi di questo, ma non c'è nemmeno bisogno di chiederlo :)

Answer 2

Il seguente dovrebbe fare

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

Come ho capito che si desidera sommare i bit di ogni XOR tra il byte sinistro e destro.

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

Non sono sicuro se si intende sommare i byte oi bit. Riassumendo i bit all'interno di un byte, questo dovrebbe funzionare:

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

Si sarebbe quindi bisogno di XOR, e la matrice loop intorno a questo, naturalmente.

Answer 5

modo più veloce sarebbe probabilmente una tabella di ricerca 256 elementi ...

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

esempio

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

Answer 6

Questo è più comunemente indicato come il conteggio dei bit. Ci sono letteralmente dozzine di diversi algoritmi per farlo. Here è un sito che elenca alcuni dei metodi più noti. Ci sono anche istruzioni specifiche per CPU per fare questo.

Teoricamente, Microsoft potrebbe aggiungere una funzione BitArray.CountSetBits che ottiene JIT con il migliore algoritmo per l'architettura della CPU. Io, per esempio, darei il benvenuto a questa aggiunta.

Answer 7

una funzione generale per contare i bit potrebbero apparire come:

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; 
} 

I meno 1-bit, il più veloce questo funziona. Semplicemente scorre su ogni byte e commuta il minimo 1 bit di quel byte fino a quando il byte diventa 0. I getti sono necessari in modo che il compilatore smetta di lamentarsi dell'ampliamento e del restringimento del tipo.

Il tuo problema potrebbe quindi essere risolto utilizzando questo:

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

Può essere riscritta come ulong e utilizzare unsafe puntatore, ma byte è più facile da capire:

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 tabella di ricerca dovrebbe essere il più veloce, ma se vuoi farlo senza una tabella di ricerca, questo funzionerà per byte in sole 10 operazioni.

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

Questa è una versione byte della funzione di conteggio bit generale descritta in Sean Eron Anderson's bit fiddling site.