Compter les bits dans le nombre

Dupliquer:

Le meilleur algorithme pour compter le nombre de bits définis dans un entier de 32 bits?


Supposons que vous ayez un numéro. Est-il possible de compter les bits qui sont égaux à 1 dans la représentation binary de ce nombre, sans utiliser l’itération? Je veux dire, est-il possible de le faire en temps constant en utilisant des opérateurs et des masques au niveau des bits? J’ai besoin d’une solution qui fonctionnera bien pour les deux architectures 32 bits et 64 bits. Ah presque oublié, j’en ai besoin pour le langage C ou l’assembleur est aussi bon.

    Un algorithme de comptage de bits sans boucle est disponible à l’ adresse http://graphics.stanford.edu/~seander/bithacks.html . Beaucoup d’algorithmes de comptage de bits à http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

    Bien sûr que oui, mais vous n’allez pas aimer ça.

    Vous pouvez bien sûr construire une table de recherche contenant toutes les valeurs correctes:

    table [1] = 1, table [2] = 1, table [3] = 2, etc.

    Donc, cela vous donnerait une réponse très rapide , mais c’est une solution totalement inutile en soi, car le tableau devrait être très, très grand.

    Vous pouvez l’optimiser un peu, mais cela nécessite juste une petite itération. Créez simplement une version 8 bits de la solution de table, une simple table à 256 entrées, puis parcourez chaque octet BYTE de la valeur à vérifier en faisant la sum des résultats de la recherche de table. Quelque chose comme:

    short int tableLookup[256] = { 0, 1, 1, 2, 1, ... }; unsigned int valueToCheck = 89392491; int result = 0; while ( valueToCheck != 0 ) { result += tableLookup[ (valueToCheck & 0xFF) ]; valueToCheck >>= 8; } // result should now have the correct bit count, if the table is correct. 

    Hmm, cela semble être bien connu (et ici, je le faisais par cœur): http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

    Oui, vous pouvez le faire en utilisant une table de correspondance .