Méthode la plus rapide pour calculer la somme de bits dans le tableau d'octets

Question

J'ai deux tableaux d'octets de même longueur. J'ai besoin d'effectuer une opération XOR entre chaque octet et après cette somme de bits calculée.

Par exemple:

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

Je dois faire la même opération pour chaque élément de tableau d'octets.

Answer 1

Utilisez une table de correspondance. Il n'y a que 256 valeurs possibles après XORing, donc cela ne va pas prendre beaucoup de temps. Contrairement à la solution d'izb, je ne suggérerais pas de mettre toutes les valeurs manuellement - calculons la table de recherche une fois au démarrage en utilisant l'une des réponses en boucle.

Par exemple:

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

(Vous pourrait faire une méthode d'extension si vous vouliez vraiment ...)

Notez l'utilisation de byte[] dans la méthode CountBitsAfterXor - vous pourrait en faire un IEnumerable<byte> pour plus de généralité, mais itérer sur un tableau (qui est connu pour être un tableau au moment de la compilation) sera plus rapide. Probablement plus rapide microscopiquement, mais bon, vous avez demandé le plus rapide façon :)

Je certainement effectivement exprimer comme

public static int CountBitsAfterXor(IEnumerable<byte> data) 

dans la vie réelle, mais voyez ce qui fonctionne mieux pour vous .

Notez également le type de la variable xor en tant que int. En fait, il n'y a pas d'opérateur XOR défini pour les valeurs byte et si vous avez fait xor un byte il compilerait encore en raison de la nature des opérateurs d'affectation composés, mais il effectuerait un cast à chaque itération - au moins dans l'IL.Il est tout à fait possible que le JIT prenne soin de cela, mais il n'est même pas nécessaire de le demander :) :)

Answer 2

Les éléments suivants doivent faire

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

Comme je l'ai bien compris, vous voulez résumer les bits de chaque XOR entre la gauche et à droite octets.

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

Je ne suis pas sûr si vous voulez dire la somme des octets ou des bits. Pour résumer les bits dans un octet, cela devrait fonctionner:

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

Vous aurez alors besoin du XOR, et le réseau en boucle autour de cela, bien sûr.

Answer 5

moyen le plus rapide serait probablement une table de recherche 256 éléments ...

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

par exemple

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

Answer 6

Ceci est plus communément appelé le comptage de bits. Il y a littéralement des douzaines d'algorithmes différents pour ce faire. Here est un site qui énumère quelques-unes des méthodes les plus connues. Il y a même des instructions spécifiques au CPU pour ce faire.

Théoriquement, Microsoft pourrait ajouter une fonction BitArray.CountSetBits qui est JITed avec le meilleur algorithme pour cette architecture CPU. Pour ma part, j'accueillerais un tel ajout.

Answer 7

Une fonction générale pour compter les bits pourrait ressembler à:

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

Les moins 1 bits, plus vite cela fonctionne. Il boucle simplement sur chaque octet, et bascule le 1 bit le plus bas de cet octet jusqu'à ce que l'octet devienne 0. Les castings sont nécessaires pour que le compilateur cesse de se plaindre du type élargissement et rétrécissement.

Votre problème pourrait alors être résolu en utilisant ceci:

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

Il peut être réécrite comme ulong et utiliser un pointeur unsafe, mais byte est plus facile à comprendre:

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

Une table de consultation devrait Soyez le plus rapide, mais si vous voulez le faire sans une table de recherche, cela fonctionnera pour les octets en seulement 10 opérations.

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

Ceci est une version d'octets de la fonction générale de comptage de bits décrit à Sean Eron Anderson's bit fiddling site.