Schnellste Möglichkeit, die Summe der Bits im Byte-Array zu berechnen

Question

Ich habe zwei Byte-Arrays mit der gleichen Länge. Ich muss eine XOR-Operation zwischen jedem Byte durchführen und danach die Summe der Bits berechnen.

Zum Beispiel:

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

Ich brauche für jedes Element in Byte-Array die gleiche Operation zu tun.

Answer 1

Verwenden Sie eine Nachschlagetabelle. Es gibt nur 256 mögliche Werte nach XORing, also wird es nicht lange dauern. Anders als bei der izb-Lösung würde ich jedoch nicht vorschlagen, alle Werte manuell einzugeben - berechne die Nachschlagetabelle einmal beim Start mit einer der loopenden Antworten.

Zum Beispiel:

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

(Sie könnte es eine Erweiterungsmethode, wenn Sie wirklich wollte ...)

Beachten Sie die Verwendung von byte[] im CountBitsAfterXor Methode - Sie konnte Machen Sie es für allgemeinere Zwecke zu einem IEnumerable<byte>, aber das Iterieren über ein Array (das bei der Kompilierung als Array bekannt ist) wird schneller. Wahrscheinlich nur mikroskopisch schneller, aber hey, fragte sie die schnellste Weg :)

würde ich mit ziemlicher Sicherheit tatsächlich es ausdrücken als

public static int CountBitsAfterXor(IEnumerable<byte> data) 

im wirklichen Leben, aber sehen, welche für Sie besser funktioniert .

Beachten Sie auch den Typ der xor Variable als int. Tatsächlich ist kein XOR-Operator für byte Werte definiert, und wenn Sie xor eine byte gemacht hätten, würde es immer noch kompilieren aufgrund der Natur von Compound-Zuweisungsoperatoren, aber es würde bei jeder Iteration eine Umwandlung durchführen - zumindest in der IL.Es ist durchaus möglich, dass das JIT sich darum kümmern würde, aber es gibt keine Notwendigkeit, es sogar zu fragen :)

Answer 2

Die folgende Beschreibung ist

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

Wie ich es verstanden Sie die Bits jedes XOR zwischen dem linken und rechten Bytes summieren möchten.

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

Ich bin nicht sicher, wenn Sie Summe der Bytes oder der Bits meinen. Um die Bits innerhalb eines Bytes zusammenzufassen, sollte diese Arbeit:

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

Sie müssten dann die XOR-Verknüpfung und Anordnung um diese Looping, natürlich.

Answer 5

Der schnellste Weg wäre wahrscheinlich eine 256-Element-Lookup-Tabelle sein ...

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

z.B.

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

Answer 6

Dies wird häufiger als Bit-Zählung bezeichnet. Dafür gibt es buchstäblich Dutzende verschiedener Algorithmen. Here ist eine Seite, die einige der bekannteren Methoden auflistet. Dazu gibt es sogar CPU-spezifische Anweisungen.

Theoretisch könnte Microsoft eine -Funktion hinzufügen, die JITed mit dem besten Algorithmus für diese CPU-Architektur erhält. Ich würde eine solche Ergänzung begrüßen.

Answer 7

Eine allgemeine Funktion Bits aussehen zählen kann:

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

Je weniger 1-Bit arbeitet, desto schneller dies. Es läuft einfach über jedes Byte und schaltet das niedrigste 1 Bit dieses Bytes um, bis das Byte 0 wird. Die Castings sind notwendig, damit der Compiler aufhört, sich über die Typverbreiterung und -verengung zu beschweren.

Ihr Problem dann unter Verwendung dieser gelöst werden könnte:

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

Es als ulong neu geschrieben werden können und unsafe Zeiger verwenden, aber byte leichter zu verstehen:

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

Eine Lookup-Tabelle sollte Seien Sie der schnellste, aber wenn Sie es ohne eine Nachschlagetabelle tun möchten, funktioniert dies für Bytes in nur 10 Operationen.

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

Dies ist eine Byte-Version der allgemeinen Funktion Bit Zählung bei Sean Eron Anderson's bit fiddling site beschrieben.