Contar bits en el número [duplicado]

Question

Duplicar:

  

Mejor algoritmo para contar el número de bits establecidos en un entero de 32 bits?

---

Suponga que tiene un número. ¿Hay alguna manera de contar los bits que equivale a 1 en la representación binaria de ese número, sin usar la iteración? Quiero decir, ¿hay alguna manera de hacerlo en tiempo constante usando algunos operadores y máscaras bit a bit? Necesito una solución que funcione bien tanto para arquitecturas de 32 bits como de 64 bits. Ah, casi lo olvido, lo necesito para lenguaje C o ensamblador también es bueno.

Answer 1

Hay un algoritmo de conteo de bits sin bucle en http: //graphics.stanford. edu / ~ seander / bithacks.html . Muchos algoritmos de conteo de bits en http: //gurmeetsingh.wordpress .com / 2008/08/05 / rutinas rápidas de conteo de bits /

Answer 2

Bueno, claro que sí, pero no te va a gustar.

Podría, por supuesto, crear una tabla de búsqueda con todos los valores correctos:

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

Entonces, esto le daría una respuesta realmente rápida , pero es una solución completamente inútil por sí misma, ya que la tabla debería ser muy, muy grande.

Puede optimizar esto un poco, pero requiere solo una pequeña iteración. Simplemente cree una versión de 8 bits de la solución de tabla, una mera tabla de 256 entradas, luego repita cada BYTE en el valor a verificar, sumando los resultados de la búsqueda de la tabla. Algo así como:

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, parece que esto es bien conocido (y aquí estaba haciendo esto fuera de mi cabeza): http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Answer 3

Sí, puede hacerlo utilizando una tabla de búsqueda .