Comment implémenter Bitcount en utilisant uniquement des opérateurs Bitwise ?

Question

Il s'agit d'implémenter une logique de comptage de bits en utilisant uniquement des opérateurs bitwise. J'ai réussi à le faire fonctionner correctement, mais je me demande si quelqu'un peut suggérer une approche plus élégante.

Seules les opérations par bit sont autorisées. Pas de "si", "pour", etc.

int x = 4;

printf("%d\n", x & 0x1);
printf("%d\n", (x >> 1) & 0x1);
printf("%d\n", (x >> 2) & 0x1);
printf("%d\n", (x >> 3) & 0x1);

Nous vous remercions.

Answer 1

De http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here

c = v - ((v >> 1) & 0x55555555);
c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
c = ((c >> 4) + c) & 0x0F0F0F0F;
c = ((c >> 8) + c) & 0x00FF00FF;
c = ((c >> 16) + c) & 0x0000FFFF;

Edit : Il est vrai qu'il est un peu optimisé, ce qui le rend plus difficile à lire. Il est plus facile à lire comme :

c = (v & 0x55555555) + ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F);
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF);
c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF);

À chaque étape de ces cinq étapes, les bits voisins sont additionnés par groupes de 1, puis de 2, puis de 4, etc. La méthode est basée sur le principe "diviser pour régner".

Dans la première étape, nous additionnons les bits 0 et 1 et plaçons le résultat dans le segment de deux bits 0-1, nous additionnons les bits 2 et 3 et plaçons le résultat dans le segment de deux bits 2-3, etc...

Dans la deuxième étape, nous additionnons les deux bits 0-1 et 2-3 et plaçons le résultat dans le quatre bits 0-3, nous additionnons les deux bits 4-5 et 6-7 et plaçons le résultat dans le quatre bits 4-7, etc...

Exemple :

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1)
After the first step I have:      0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10
In the second step I have:        0000000100010011 ( 00+00   00+01   01+00   01+10 ) = 0000 0001 0001 0011
In the fourth step I have:        0000000100000100 (   0000+0001       0001+0011   ) = 00000001 00000100
In the last step I have:          0000000000000101 (       00000001+00000100       )

qui est égal à 5, ce qui est le résultat correct

Answer 2

J'utiliserais un tableau précalculé

uint8_t set_bits_in_byte_table[ 256 ];

En i -La quatrième entrée de ce tableau indique le nombre de bits activés dans l'octet. i , par exemple set_bits_in_byte_table[ 100 ] = 3 puisqu'il y a 3 1 bits dans la représentation binaire de la valeur décimale 100 (=0x64 = 0110-0100).

Ensuite, j'essaierais

size_t count_set_bits( uint32_t const x ) {
    size_t count = 0;
    uint8_t const * byte_ptr = (uint8_t const *) &x;
    count += set_bits_in_byte_table[ *byte_ptr++ ];
    count += set_bits_in_byte_table[ *byte_ptr++ ];
    count += set_bits_in_byte_table[ *byte_ptr++ ];
    count += set_bits_in_byte_table[ *byte_ptr++ ];
    return count;
}

Answer 3

Voici une illustration simple de la répondre :

a b c d       0 a b c       0 b 0 d    
&             &             +
0 1 0 1       0 1 0 1       0 a 0 c
-------       -------       -------
0 b 0 d       0 a 0 c       a+b c+d

Nous avons donc exactement 2 bits pour stocker a + b et 2 bits pour stocker c + d. a = 0, 1 etc., donc 2 bits sont nécessaires pour stocker leur somme. À l'étape suivante, nous aurons 4 bits pour stocker la somme des valeurs de 2 bits, etc.

Answer 4

Plusieurs solutions intéressantes aquí .

Si les solutions ci-dessus sont trop ennuyeuses, voici une version récursive en C, exempte de test de condition ou de boucle :

  int z(unsigned n, int count);
  int f(unsigned n, int count);

  int (*pf[2])(unsigned n, int count) = { z,f };

  int f(unsigned n, int count)
  {
     return (*pf[n > 0])(n >> 1, count+(n & 1));
  }

  int z(unsigned n, int count)
  {
     return count;
  }

  ...
  printf("%d\n", f(my_number, 0));