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

Question

La tâche consiste à implémenter une logique de comptage de bits en utilisant uniquement des opérateurs au niveau du bit. Je l'ai bien fonctionné, mais je me demande si quelqu'un peut suggérer une approche plus élégante.

Seules les opérations au niveau du 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); 

Merci.

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é qui le rend plus difficile à lire. Il est plus facile à lire que:

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, ajoute des bits voisins en groupes de 1, puis 2, puis 4, etc. La méthode est basée à diviser pour mieux régner.

Dans la première étape, nous additionnons les bits 0 et 1 et mettons le résultat dans le segment de deux bits 0-1, ajoutez les bits 2 et 3 et placez le résultat dans le segment de deux bits 2-3 etc ... Dans la deuxième étape, nous ajoutons ensemble les deux bits 0-1 et 2-3 et mettons le résultat dans un bit de 0-3, additionnez deux bits 4-5 et 6-7 et mettez le résultat à 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, qui est le résultat correct

Answer 2

Plusieurs solutions intéressantes here.

Si les solutions ci-dessus sont trop ennuyeux, voici une version récursive C exempt de test de condition ou de la 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)); 

Answer 3

Je voudrais utiliser un tableau précalculé

uint8_t set_bits_in_byte_table[ 256 ]; 

Le i - l'entrée dans cette table stocke le nombre de bits définis dans l'octet i, par ex. set_bits_in_byte_table[ 100 ] = 3 car il y a 3 1 bits en représentation binaire de 100 décimal (= 0x64 = 0110-0100).

Je voudrais essayer

size_t count_set_bits(uint32_t x) { 
    size_t count = 0; 
    uint8_t * byte_ptr = (uint8_t *) &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 4

Voici une illustration simple au answer:

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 est ce dont nous avons besoin pour stocker leur somme. À l'étape suivante, nous aurons 4 bits pour stocker la somme des valeurs de 2 bits, etc.