Plus rapide pour calculer la somme des bits dans le tableau d'octets

Question

J'ai deux tableaux d'octets avec la même longueur. Je besoin d'effectuer l'opération XOR entre chaque octet et après cela, calculer la somme de bits.

Par exemple:

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

J'ai besoin faire la même opération pour chaque élément de tableau d'octets.

Answer 1

Utilisez une table de consultation. Il n'y a que 256 valeurs possibles après XOR, donc il va pas exactement à prendre beaucoup de temps. Contrairement à la solution de IZB cependant, je ne suggérera pas mettre manuellement toutes les valeurs bien -. Calculer la table de recherche une fois au démarrage en utilisant l'une des réponses looping

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 peut en faire une méthode d'extension si vous vouliez vraiment ...)

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

Je presque certainement en fait exprimer comme

public static int CountBitsAfterXor(IEnumerable<byte> data)

dans la vraie vie, mais voir ce qui fonctionne mieux pour vous.

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

Answer 2

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 3

Ceci est plus communément appelé comptage de bits. Il y a littéralement des douzaines de différents algorithmes pour ce faire. Voici un seul site qui liste quelques-unes des méthodes les plus connues. Il y a même des instructions spécifiques du processeur pour ce faire.

Theorectically, Microsoft pourrait ajouter une fonction BitArray.CountSetBits qui obtient JITed le meilleur algorithme pour cette architecture CPU. Pour ma part, accueillerait favorablement une telle addition.

Answer 4

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

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 5

Je ne sais pas si vous entendez somme les octets ou les 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, bien sûr.

Answer 6

Les points 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 7

Il peut être réécrite comme pointeur ulong de unsafe et d'utilisation, 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 8

Une fonction générale de 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 suffit de boucles au-dessus de chaque octet, et active ou désactive la plus faible de 1 bit de cet octet jusqu'à ce que l'octet devient 0. Les pièces coulées sont alors nécessaire que le compilateur cesse de se plaindre du type élargissement et le 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 9

A la table doit être le plus rapide, mais si vous voulez le faire sans une table de consultation, cela fonctionnera pour les octets en 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'octet de la fonction générale de comptage de bits décrit au bit Sean Anderson Eron le site tripoter .