Compter les bits dans le nombre [dupliquer]

Question

Dupliquer:

  

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 binaire 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, j'ai presque oublié, j'en ai besoin pour le langage C ou l'assembleur est également bon.

Answer 1

Il existe un algorithme de comptage de bits sans boucle à l'adresse http: //graphics.stanford. edu / ~ seander / bithacks.html . Nombreux algorithmes de comptage de bits à l'adresse http: //gurmeetsingh.wordpress .com / 2008/08/05 / routines de comptage rapide /

Answer 2

Bien sûr, il y en a un, mais vous n'allez pas aimer ça.

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

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

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

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 dans la valeur à vérifier en faisant la somme des résultats de la recherche dans la 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

Answer 3

Oui, vous pouvez le faire en utilisant un tableau de recherche . .