¿Cómo contar la cantidad de bits configurados en un entero de 32 bits?

8 bits que representan el número 7 se ven así:

00000111 

Tres bits están establecidos.

¿Qué son los algoritmos para determinar el número de bits establecidos en un entero de 32 bits?

Esto se conoce como ‘ Hamming Weight ‘, ‘popcount’ o ‘sideways addition’.

El ‘mejor’ algoritmo realmente depende de la CPU en la que se encuentre y cuál sea su patrón de uso.

Algunas CPU tienen una sola instrucción incorporada para hacerlo y otras tienen instrucciones paralelas que actúan sobre vectores de bits. Las instrucciones paralelas (como popcnt x86, en las CPU donde es compatible) serán casi con certeza las más rápidas. Algunas otras architectures pueden tener una instrucción lenta implementada con un bucle microcodificado que prueba un bit por ciclo ( cita requerida ).

Un método de búsqueda de tabla precompuesto puede ser muy rápido si su CPU tiene un caché grande y / o está haciendo muchas de estas instrucciones en un ciclo cerrado. Sin embargo, puede sufrir debido al gasto de una “falta de caché”, donde la CPU tiene que recuperar parte de la tabla de la memoria principal.

Si sabe que sus bytes serán mayoritariamente 0 o mayormente 1, entonces existen algoritmos muy eficientes para estos escenarios.

Creo que un algoritmo de propósito general muy bueno es el siguiente, conocido como ‘paralelo’ o ‘algoritmo SWAR de precisión variable’. He expresado esto en un pseudo idioma similar a C, es posible que deba ajustarlo para que funcione para un idioma en particular (por ejemplo, usando uint32_t para C ++ y >>> en Java):

 int numberOfSetBits(int i) { // Java: use >>> instead of >> // C or C++: use uint32_t i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } 

Este tiene el mejor comportamiento en el peor de los casos de cualquiera de los algoritmos analizados, por lo que se ocupará de manera eficiente de cualquier patrón de uso o valores que arroje sobre él.


Este algoritmo de SWAR bitwise podría paralelizarse para hacerse en múltiples elementos de vectores a la vez, en lugar de en un solo registro de enteros, para una aceleración en las CPU con SIMD pero ninguna instrucción de cuenta de usuario utilizable. (por ejemplo, código x86-64 que tiene que ejecutarse en cualquier CPU, no solo en Nehalem o posterior).

Sin embargo, la mejor forma de usar instrucciones vectoriales para popcount es usualmente usando un cambio de variable para hacer una búsqueda de tabla de 4 bits a la vez de cada byte en paralelo. (Los 4 bits indexan una tabla de entrada 16 mantenida en un registro vectorial).

En las CPU Intel, la instrucción popcnt de hardware de 64 bits puede superar en rendimiento a una PSHUFB SSSE3 PSHUFB bit paralelo en un factor de 2, pero solo si el comstackdor lo hace correctamente . De lo contrario, SSE puede salir significativamente adelante. Las versiones de comstackdor más nuevas son conscientes del problema de falsa y popcnt en Intel .

Referencias

https://graphics.stanford.edu/~seander/bithacks.html

https://en.wikipedia.org/wiki/Hamming_weight

http://gurmeet.net/puzzles/fast-bit-counting-routines/

http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)

También considere las funciones incorporadas de sus comstackdores.

En el comstackdor de GNU, por ejemplo, puedes usar:

 int __builtin_popcount (unsigned int x); int __builtin_popcountll (unsigned long long x); 

En el peor de los casos, el comstackdor generará una llamada a una función. En el mejor de los casos, el comstackdor emitirá una instrucción de CPU para hacer el mismo trabajo más rápido.

Los intrínsecos de GCC incluso funcionan en múltiples plataformas. Popcount se convertirá en la stream principal en la architecture x86, por lo que tiene sentido comenzar a usar lo intrínseco ahora. Otras architectures tienen la cuenta durante años.


En x86, puede decirle al comstackdor que puede asumir soporte para instrucciones -mpopcnt con -mpopcnt o -msse4.2 para habilitar también las instrucciones vectoriales que se agregaron en la misma generación. Vea las opciones de GCC x86 . -march=nehalem (o -march= cualquier CPU que desee que su código asum y sintonice) podría ser una buena opción. Ejecutar el binario resultante en una CPU anterior dará como resultado una falla de instrucción ilegal.

Para optimizar los binarios para la máquina en la que los construye, use -march=native (con gcc, clang o ICC).

MSVC proporciona una instrucción intrínseca para popcnt x86 , pero a diferencia de gcc, es realmente una intrínseca para las instrucciones de hardware y requiere soporte de hardware.


Usar std::bitset<>::count() lugar de un built-in

En teoría, cualquier comstackdor que sepa cómo contar eficientemente para la CPU objective debe exponer esa funcionalidad a través de ISO C ++ std::bitset<> . En la práctica, es posible que esté mejor con el bit-hack AND / shift / ADD en algunos casos para algunas CPU de destino.

Para las architectures de destino donde hardware popcount es una extensión opcional (como x86), no todos los comstackdores tienen un std::bitset que lo aprovecha cuando está disponible. Por ejemplo, MSVC no tiene manera de habilitar el soporte de popcnt en tiempo de comstackción, y siempre usa una búsqueda de tabla , incluso con /Ox /arch:AVX (lo que implica SSE4.2, aunque técnicamente hay un bit de función separado para popcnt ).

Pero al menos obtienes algo portátil que funciona en todas partes, y con gcc / clang con las opciones de destino correctas, obtienes la cuenta de hardware para las architectures que lo soportan.

 #include  #include  #include  template //static inline // static if you want to compile with -mpopcnt in one comstacktion unit but not others typename std::enable_if::value, unsigned >::type popcount(T x) { static_assert(std::numeric_limits::radix == 2, "non-binary type"); // sizeof(x)*CHAR_BIT constexpr int bitwidth = std::numeric_limits::digits + std::numeric_limits::is_signed; // std::bitset constructor was only unsigned long before C++11. Beware if porting to C++03 static_assert(bitwidth <= std::numeric_limits::digits, "arg too wide for std::bitset() constructor"); typedef typename std::make_unsigned::type UT; // probably not needed, bitset width chops after sign-extension std::bitset bs( static_cast(x) ); return bs.count(); } 

Ver asm de gcc, clang, icc y MSVC en el explorador del comstackdor Godbolt.

x86-64 gcc -O3 -std=gnu++11 -mpopcnt emite esto:

 unsigned test_short(short a) { return popcount(a); } movzx eax, di # note zero-extension, not sign-extension popcnt rax, rax ret unsigned test_int(int a) { return popcount(a); } mov eax, edi popcnt rax, rax ret unsigned test_u64(unsigned long long a) { return popcount(a); } xor eax, eax # gcc avoids false dependencies for Intel CPUs popcnt rax, rdi ret 

PowerPC64 gcc -O3 -std=gnu++11 -O3 gcc -O3 -std=gnu++11 emite (para la versión int arg):

  rldicl 3,3,0,32 # zero-extend from 32 to 64-bit popcntd 3,3 # popcount blr 

Esta fuente no es específica para x86 o específica de GNU, pero solo comstack bien para x86 con gcc / clang / icc.

También tenga en cuenta que el respaldo de gcc para architectures sin popcount de instrucción única es una búsqueda de tablas byte-a-time. Esto no es maravilloso para ARM, por ejemplo .

En mi opinión, la “mejor” solución es la que puede leer otro progtwigdor (o el progtwigdor original dos años más tarde) sin muchos comentarios. Es posible que desee la solución más rápida o más inteligente que algunos ya han proporcionado, pero prefiero legibilidad sobre inteligencia en cualquier momento.

 unsigned int bitCount (unsigned int value) { unsigned int count = 0; while (value > 0) { // until all bits are zero if ((value & 1) == 1) // check lower bit count++; value >>= 1; // shift bits, removing lower bit } return count; } 

Si desea más velocidad (y suponiendo que lo documenta bien para ayudar a sus sucesores), puede usar una tabla de búsqueda:

 // Lookup table for fast calculation of bits set in 8-bit unsigned char. static unsigned char oneBitsInUChar[] = { // 0 1 2 3 4 5 6 7 8 9 ABCDEF (<- n) // ===================================================== 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n : : : 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn }; // Function for fast calculation of bits set in 16-bit unsigned short. unsigned char oneBitsInUShort (unsigned short x) { return oneBitsInUChar [x >> 8] + oneBitsInUChar [x & 0xff]; } // Function for fast calculation of bits set in 32-bit unsigned int. unsigned char oneBitsInUInt (unsigned int x) { return oneBitsInUShort (x >> 16) + oneBitsInUShort (x & 0xffff); } 

Aunque estos se basan en tamaños de tipos de datos específicos, no son tan portátiles. Pero, dado que muchas optimizaciones de rendimiento no son portátiles de todos modos, eso puede no ser un problema. Si quieres portabilidad, me quedaré con la solución legible.

De Hacker’s Delight, p. 66, Figura 5-2

 int pop(unsigned x) { x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; x = x + (x >> 8); x = x + (x >> 16); return x & 0x0000003F; } 

Se ejecuta en instrucciones ~ 20-ish (depende del arco), sin ramificación.

¡Hacker’s Delight es delicioso! Muy recomendable.

Creo que la manera más rápida, sin usar tablas de búsqueda y popcount, es la siguiente. Cuenta los bits establecidos con solo 12 operaciones.

 int popcount(int v) { v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; } 

Funciona porque puede contar la cantidad total de bits configurados al dividirlos en dos mitades, contar el número de bits establecidos en ambas mitades y luego sumrlos. También se conoce como el paradigma Divide and Conquer . Vamos a entrar en detalles …

 v = v - ((v >> 1) & 0x55555555); 

El número de bits en dos bits puede ser 0b00 , 0b01 o 0b10 . Tratemos de resolver esto en 2 bits.

  --------------------------------------------- | v | (v >> 1) & 0b0101 | v - x | --------------------------------------------- 0b00 0b00 0b00 0b01 0b00 0b01 0b10 0b01 0b01 0b11 0b01 0b10 

Esto es lo que se requería: la última columna muestra el recuento de bits establecidos en cada par de dos bits. Si el número de dos bits es >= 2 (0b10) and luego produce 0b01 , de lo contrario produce 0b00 .

 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

Esta statement debería ser fácil de entender. Después de la primera operación tenemos el recuento de bits establecidos en cada dos bits, ahora summos ese recuento en cada 4 bits.

 v & 0b00110011 //masks out even two bits (v >> 2) & 0b00110011 // masks out odd two bits 

Luego resumimos el resultado anterior, dándonos la cuenta total de bits establecidos en 4 bits. La última statement es la más difícil.

 c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 

Vamos a dividirlo más …

 v + (v >> 4) 

Es similar a la segunda statement; estamos contando los bits establecidos en grupos de 4 en su lugar. Sabemos, debido a nuestras operaciones previas, que cada mordisco tiene el recuento de bits establecidos. Veamos un ejemplo. Supongamos que tenemos el byte 0b01000010 . Significa que el primer mordisco tiene su conjunto de 4 bits y el segundo tiene su conjunto de 2 bits. Ahora agregamos esos nibbles juntos.

 0b01000010 + 0b01000000 

Nos da el recuento de bits establecidos en un byte, en el primer nibble 0b01100010 y, por lo tanto, enmascaramos los últimos cuatro bytes de todos los bytes del número (descartándolos).

 0b01100010 & 0xF0 = 0b01100000 

Ahora cada byte tiene el recuento de bits establecidos. Necesitamos sumrlos todos juntos. El truco es multiplicar el resultado por 0b10101010 que tiene una propiedad interesante. Si nuestro número tiene cuatro bytes, ABCD , dará como resultado un nuevo número con estos bytes A+B+C+D B+C+D C+DD . Un número de 4 bytes puede tener un máximo de 32 bits configurados, que se pueden representar como 0b00100000 .

Todo lo que necesitamos ahora es el primer byte que tiene la sum de todos los bits establecidos en todos los bytes, y lo obtenemos en >> 24 . Este algoritmo fue diseñado para palabras de 32 bit pero puede modificarse fácilmente para palabras de 64 bit .

Me aburrí y cronometré mil millones de iteraciones de tres enfoques. El comstackdor es gcc -O3. La CPU es lo que ponen en la primera generación de Macbook Pro.

Lo más rápido es lo siguiente, a los 3.7 segundos:

 static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 }; static int popcount( unsigned int i ) { return( wordbits[i&0xFFFF] + wordbits[i>>16] ); } 

El segundo lugar va al mismo código pero busca 4 bytes en lugar de 2 medias palabras. Eso tomó alrededor de 5.5 segundos.

El tercer lugar es para el enfoque de “adición lateral”, que requiere poco tiempo, que demoró 8.6 segundos.

El cuarto lugar va para __builtin_popcount () de GCC, en unos vergonzosos 11 segundos.

El método de contar un bit a la vez fue cada vez más lento, y me aburrí de esperar a que se completara.

Entonces, si te importa el rendimiento sobre todo lo demás, utiliza el primer enfoque. Si te importa, pero no lo suficiente como para gastar 64 Kb de RAM, usa el segundo método. De lo contrario, utilice el enfoque legible (pero lento) de un bit a la vez.

Es difícil pensar en una situación en la que te gustaría usar el enfoque de dar vueltas.

Editar: resultados similares aquí .

Si está utilizando Java, el método integrado Integer.bitCount lo hará.

 unsigned int count_bit(unsigned int x) { x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF); return x; } 

Déjame explicar este algoritmo.

Este algoritmo se basa en el algoritmo Dividir y Conquistar. Supongamos que hay un entero de 8 bits 213 (11010101 en binario), el algoritmo funciona así (cada vez fusiona dos bloques contiguos):

 +-------------------------------+ | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x | 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge | 0 0 1 1 | 0 0 1 0 | <- second time merge | 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5) +-------------------------------+ 

Esta es una de esas preguntas donde ayuda a conocer su microarchitecture. Acabo de cronometrar dos variantes en gcc 4.3.3 comstackdas con -O3 usando líneas en C ++ para eliminar la sobrecarga de llamadas de función, mil millones de iteraciones, manteniendo la sum stream de todos los conteos para asegurar que el comstackdor no elimine nada importante, usando rdtsc para el tiempo ( ciclo de reloj preciso).

 inline int pop2 (unsigned x, unsigned y)
 {
     x = x - ((x >> 1) & 0x55555555);
     y = y - ((y >> 1) & 0x55555555);
     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
     y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
     x = (x + (x >> 4)) & 0x0F0F0F0F;
     y = (y + (y >> 4)) & 0x0F0F0F0F;
     x = x + (x >> 8);
     y = y + (y >> 8);
     x = x + (x >> 16);
     y = y + (y >> 16);
     return (x + y) y 0x000000FF;
 }

El Hacker’s Delight sin modificar tomó 12.2 gigaciclos. Mi versión paralela (que cuenta el doble de bits) se ejecuta en 13.0 gigaciclos. 10.5s total transcurrido para ambos juntos en un Core Duo de 2.4GHz. 25 gigaciclos = poco más de 10 segundos en esta frecuencia de reloj, así que estoy seguro de que mis tiempos son correctos.

Esto tiene que ver con las cadenas de dependencia de instrucciones, que son muy malas para este algoritmo. Podría casi duplicar la velocidad nuevamente usando un par de registros de 64 bits. De hecho, si fuera inteligente y añadiera x + ya un poco antes, podría cambiar algunos turnos. La versión de 64 bits con algunos ajustes pequeños saldría a la par, pero contaría el doble de bits otra vez.

Con los registros SIMD de 128 bits, otro factor más de dos, y los conjuntos de instrucciones SSE a menudo también tienen atajos inteligentes.

No hay ninguna razón para que el código sea especialmente transparente. La interfaz es simple, el algoritmo se puede referenciar en línea en muchos lugares, y es susceptible de una prueba de unidad completa. El progtwigdor que tropieza con él puede incluso aprender algo. Estas operaciones de bit son extremadamente naturales a nivel de máquina.

OK, decidí usar la versión ajustada de 64 bits. Para este tamaño único (largo sin signo) == 8

 inline int pop2 (unsigned long x, unsigned long y)
 {
     x = x - ((x >> 1) & 0x5555555555555555);
     y = y - ((y >> 1) & 0x5555555555555555);
     x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
     y = (y & x3333333333333333) + ((y >> 2) & 0x3333333333333333);
     x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
     y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
     x = x + y; 
     x = x + (x >> 8);
     x = x + (x >> 16);
     x = x + (x >> 32); 
     devolver x y 0xFF;
 }

Eso se ve bien (aunque no estoy probando cuidadosamente). Ahora los tiempos vienen en 10.70 gigaciclos / 14.1 gigaciclos. Ese número posterior sumó 128 mil millones de bits y corresponde a 5.9s transcurridos en esta máquina. La versión no paralela se acelera un poco porque estoy ejecutando en modo de 64 bits y me gustan los registros de 64 bits un poco mejor que los registros de 32 bits.

Veamos si hay un poco más de pipelining de OOO aquí. Esto fue un poco más complicado, así que en realidad probé un poco. Cada término solo sum 64, sum combinada a 256.

 inline int pop4 (unsigned long x, unsigned long y, 
                 unsigned long u, unsigned long v)
 {
   enum {m1 = 0x5555555555555555, 
          m2 = 0x3333333333333333, 
          m3 = 0x0F0F0F0F0F0F0F0F, 
          m4 = 0x000000FF000000FF};

     x = x - ((x >> 1) & m1);
     y = y - ((y >> 1) & m1);
     u = u - ((u >> 1) & m1);
     v = v - ((v >> 1) & m1);
     x = (x & m2) + ((x >> 2) & m2);
     y = (y & m2) + ((y >> 2) & m2);
     u = (u & m2) + ((u >> 2) & m2);
     v = (v & m2) + ((v >> 2) & m2);
     x = x + y; 
     u = u + v; 
     x = (x & m3) + ((x >> 4) & m3);
     u = (u & m3) + ((u >> 4) & m3);
     x = x + u; 
     x = x + (x >> 8);
     x = x + (x >> 16);
     x = x y m4; 
     x = x + (x >> 32);
     devolver x y 0x000001FF;
 }

Estuve emocionado por un momento, pero resulta que gcc está jugando trucos en línea con -O3 a pesar de que no estoy usando la palabra clave en línea en algunas pruebas. Cuando dejo que gcc juegue trucos, mil millones de llamadas a pop4 () toman 12.56 gigaciclos, pero determiné que estaba plegando argumentos como expresiones constantes. Un número más realista parece ser 19.6 gc para otro 30% de aceleración. Mi bucle de prueba ahora se ve así, asegurándose de que cada argumento sea lo suficientemente diferente como para evitar que gcc juegue trucos.

    hitime b4 = rdtsc (); 
    para (sin signo largo i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i) 
       sum + = pop4 (i, i ^ 1, ~ i, i | 1); 
    hitime e4 = rdtsc (); 

256 mil millones de bits sumdos en 8.17s transcurridos. Funciona a 1.02 s para 32 millones de bits como punto de referencia en la tabla de búsqueda de 16 bits. No se puede comparar directamente, porque el otro banco no da la velocidad de un reloj, pero parece que he eliminado el moco de la edición de mesa de 64 KB, que es un uso trágico de la memoria caché L1 en primer lugar.

Actualización: decidió hacer lo obvio y crear pop6 () agregando cuatro líneas más duplicadas. Salió a 22.8 gc, 384 mil millones de bits sumdos en 9.5s transcurridos. Entonces hay otro 20% Ahora a 800ms por 32 billones de bits.

¿Por qué no dividir iterativamente por 2?

 recuento = 0
 mientras n> 0
   if (n% 2) == 1
     contar + = 1
   n / = 2  

Estoy de acuerdo en que este no es el más rápido, pero “lo mejor” es algo ambiguo. Sin embargo, discutiría que “lo mejor” debería tener un elemento de claridad

Para un medio feliz entre una tabla de búsqueda 2 32 y recorriendo cada bit individualmente:

 int bitcount(unsigned int num){ int count = 0; static int nibblebits[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; for(; num != 0; num >>= 4) count += nibblebits[num & 0x0f]; return count; } 

De http://ctips.pbwiki.com/CountBits

El truco de Hacker’s Delight se vuelve mucho más claro cuando escribes los patrones de los bits.

 unsigned int bitCount(unsigned int x) { x = (((x >> 1) & 0b01010101010101010101010101010101) + x & 0b01010101010101010101010101010101); x = (((x >> 2) & 0b00110011001100110011001100110011) + x & 0b00110011001100110011001100110011); x = (((x >> 4) & 0b00001111000011110000111100001111) + x & 0b00001111000011110000111100001111); x = (((x >> 8) & 0b00000000111111110000000011111111) + x & 0b00000000111111110000000011111111); x = (((x >> 16)& 0b00000000000000001111111111111111) + x & 0b00000000000000001111111111111111); return x; } 

El primer paso agrega los bits pares a los bits impares, produciendo una sum de bits en cada dos. Los otros pasos agregan trozos de alto orden a trozos de bajo orden, duplicando el tamaño del trozo hasta el último conteo, hasta que el recuento final ocupe todo el int.

No es la solución más rápida ni la mejor, pero encontré la misma pregunta en mi camino, y comencé a pensar y pensar. finalmente me di cuenta que se puede hacer así si se obtiene el problema del lado matemático, y se dibuja un gráfico, luego se encuentra que es una función que tiene una parte periódica, y luego se da cuenta de la diferencia entre los períodos … aqui tienes:

 unsigned int f(unsigned int x) { switch (x) { case 0: return 0; case 1: return 1; case 2: return 1; case 3: return 2; default: return f(x/4) + f(x%4); } } 

This can be done in O(k) , where k is the number of bits set.

 int NumberOfSetBits(int n) { int count = 0; while (n){ ++ count; n = (n - 1) & n; } return count; } 

The function you are looking for is often called the “sideways sum” or “population count” of a binary number. Knuth discusses it in pre-Fascicle 1A, pp11-12 (although there was a brief reference in Volume 2, 4.6.3-(7).)

The locus classicus is Peter Wegner’s article “A Technique for Counting Ones in a Binary Computer”, from the Communications of the ACM , Volume 3 (1960) Number 5, page 322 . He gives two different algorithms there, one optimized for numbers expected to be “sparse” (ie, have a small number of ones) and one for the opposite case.

Few open questions:-

  1. If the number is negative then?
  2. If the number is 1024 , then the “iteratively divide by 2” method will iterate 10 times.

we can modify the algo to support the negative number as follows:-

 count = 0 while n != 0 if ((n % 2) == 1 || (n % 2) == -1 count += 1 n /= 2 return count 

now to overcome the second problem we can write the algo like:-

 int bit_count(int num) { int count=0; while(num) { num=(num)&(num-1); count++; } return count; } 

for complete reference see :

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

I think the Brian Kernighan’s method will be useful too… It goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.

 int countSetBits(unsigned int n) { unsigned int n; // count the number of bits set in n unsigned int c; // c accumulates the total bits set in n for (c=0;n>0;n=n&(n-1)) c++; return c; } 

Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to me that this method “was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)”

What do you means with “Best algorithm”? The shorted code or the fasted code? Your code look very elegant and it has a constant execution time. The code is also very short.

But if the speed is the major factor and not the code size then I think the follow can be faster:

  static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... }; static int bitCountOfByte( int value ){ return BIT_COUNT[ value & 0xFF ]; } static int bitCountOfInt( int value ){ return bitCountOfByte( value ) + bitCountOfByte( value >> 8 ) + bitCountOfByte( value >> 16 ) + bitCountOfByte( value >> 24 ); } 

I think that this will not more faster for a 64 bit value but a 32 bit value can be faster.

I wrote a fast bitcount macro for RISC machines in about 1990. It does not use advanced arithmetic (multiplication, division, %), memory fetches (way too slow), branches (way too slow), but it does assume the CPU has a 32-bit barrel shifter (in other words, >> 1 and >> 32 take the same amount of cycles.) It assumes that small constants (such as 6, 12, 24) cost nothing to load into the registers, or are stored in temporaries and reused over and over again.

With these assumptions, it counts 32 bits in about 16 cycles/instructions on most RISC machines. Note that 15 instructions/cycles is close to a lower bound on the number of cycles or instructions, because it seems to take at least 3 instructions (mask, shift, operator) to cut the number of addends in half, so log_2(32) = 5, 5 x 3 = 15 instructions is a quasi-lowerbound.

 #define BitCount(X,Y) \ Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \ Y = ((Y + (Y >> 3)) & 030707070707); \ Y = (Y + (Y >> 6)); \ Y = (Y + (Y >> 12) + (Y >> 24)) & 077; 

Here is a secret to the first and most complex step:

 input output AB CD Note 00 00 = AB 01 01 = AB 10 01 = AB - (A >> 1) & 0x1 11 10 = AB - (A >> 1) & 0x1 

so if I take the 1st column (A) above, shift it right 1 bit, and subtract it from AB, I get the output (CD). The extension to 3 bits is similar; you can check it with an 8-row boolean table like mine above if you wish.

  • Don Gillies

if you’re using C++ another option is to use template metaprogramming:

 // recursive template to sum bits in an int template  int countBits(int val) { // return the least significant bit plus the result of calling ourselves with // .. the shifted value return (val & 0x1) + countBits(val >> 1); } // template specialisation to terminate the recursion when there's only one bit left template<> int countBits<1>(int val) { return val & 0x1; } 

usage would be:

 // to count bits in a byte/char (this returns 8) countBits<8>( 255 ) // another byte (this returns 7) countBits<8>( 254 ) // counting bits in a word/short (this returns 1) countBits<16>( 256 ) 

you could of course further expand this template to use different types (even auto-detecting bit size) but I’ve kept it simple for clarity.

edit: forgot to mention this is good because it should work in any C++ compiler and it basically just unrolls your loop for you if a constant value is used for the bit count (in other words, I’m pretty sure it’s the fastest general method you’ll find)

I use the below code which is more intuitive.

 int countSetBits(int n) { return !n ? 0 : 1 + countSetBits(n & (n-1)); } 

Logic : n & (n-1) resets the last set bit of n.

PS : I know this is not O(1) solution, albeit an interesting solution.

  private int get_bits_set(int v) { int c; // c accumulates the total bits set in v for (c = 0; v>0; c++) { v &= v - 1; // clear the least significant bit set } return c; } 

I’m particularly fond of this example from the fortune file:

#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

I like it best because it’s so pretty!

Java JDK1.5

Integer.bitCount(n);

where n is the number whose 1’s are to be counted.

check also,

 Integer.highestOneBit(n); Integer.lowestOneBit(n); Integer.numberOfLeadingZeros(n); Integer.numberOfTrailingZeros(n); //Beginning with the value 1, rotate left 16 times n = 1; for (int i = 0; i < 16; i++) { n = Integer.rotateLeft(n, 1); System.out.println(n); } 

I found an implementation of bit counting in an array with using of SIMD instruction (SSSE3 and AVX2). It has in 2-2.5 times better performance than if it will use __popcnt64 intrinsic function.

SSSE3 version:

 #include  #include  const __m128i Z = _mm_set1_epi8(0x0); const __m128i F = _mm_set1_epi8(0xF); //Vector with pre-calculated bit count: const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4); uint64_t BitCount(const uint8_t * src, size_t size) { __m128i _sum = _mm128_setzero_si128(); for (size_t i = 0; i < size; i += 16) { //load 16-byte vector __m128i _src = _mm_loadu_si128((__m128i*)(src + i)); //get low 4 bit for every byte in vector __m128i lo = _mm_and_si128(_src, F); //sum precalculated value from T _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo))); //get high 4 bit for every byte in vector __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F); //sum precalculated value from T _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi))); } uint64_t sum[2]; _mm_storeu_si128((__m128i*)sum, _sum); return sum[0] + sum[1]; } 

AVX2 version:

 #include  #include  const __m256i Z = _mm256_set1_epi8(0x0); const __m256i F = _mm256_set1_epi8(0xF); //Vector with pre-calculated bit count: const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4); uint64_t BitCount(const uint8_t * src, size_t size) { __m256i _sum = _mm256_setzero_si256(); for (size_t i = 0; i < size; i += 32) { //load 32-byte vector __m256i _src = _mm256_loadu_si256((__m256i*)(src + i)); //get low 4 bit for every byte in vector __m256i lo = _mm256_and_si256(_src, F); //sum precalculated value from T _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo))); //get high 4 bit for every byte in vector __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F); //sum precalculated value from T _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi))); } uint64_t sum[4]; _mm256_storeu_si256((__m256i*)sum, _sum); return sum[0] + sum[1] + sum[2] + sum[3]; } 

I always use this in Competitive Programming and it’s easy to write and efficient:

 #include  using namespace std; int countOnes(int n) { bitset<32> b(n); return b.count(); } 

There are many algorithm to count the set bits; but i think the best one is the faster one! You can see the detailed on this page:

Bit Twiddling Hacks

I suggest this one:

Counting bits set in 14, 24, or 32-bit words using 64-bit instructions

 unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v // option 1, for at most 14-bit values in v: c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf; // option 2, for at most 24-bit values in v: c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; // option 3, for at most 32-bit values in v: c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; 

This method requires a 64-bit CPU with fast modulus division to be efficient. The first option takes only 3 operations; the second option takes 10; and the third option takes 15.

Here is a portable module ( ANSI-C ) which can benchmark each of your algorithms on any architecture.

Your CPU has 9 bit bytes? No problem 🙂 At the moment it implements 2 algorithms, the K&R algorithm and a byte wise lookup table. The lookup table is on average 3 times faster than the K&R algorithm. If someone can figure a way to make the “Hacker’s Delight” algorithm portable feel free to add it in.

 #ifndef _BITCOUNT_H_ #define _BITCOUNT_H_ /* Return the Hamming Wieght of val, ie the number of 'on' bits. */ int bitcount( unsigned int ); /* List of available bitcount algorithms. * onTheFly: Calculate the bitcount on demand. * * lookupTalbe: Uses a small lookup table to determine the bitcount. This * method is on average 3 times as fast as onTheFly, but incurs a small * upfront cost to initialize the lookup table on the first call. * * strategyCount is just a placeholder. */ enum strategy { onTheFly, lookupTable, strategyCount }; /* String represenations of the algorithm names */ extern const char *strategyNames[]; /* Choose which bitcount algorithm to use. */ void setStrategy( enum strategy ); #endif 

.

 #include  #include "bitcount.h" /* The number of entries needed in the table is equal to the number of unique * values a char can represent which is always UCHAR_MAX + 1*/ static unsigned char _bitCountTable[UCHAR_MAX + 1]; static unsigned int _lookupTableInitialized = 0; static int _defaultBitCount( unsigned int val ) { int count; /* Starting with: * 1100 - 1 == 1011, 1100 & 1011 == 1000 * 1000 - 1 == 0111, 1000 & 0111 == 0000 */ for ( count = 0; val; ++count ) val &= val - 1; return count; } /* Looks up each byte of the integer in a lookup table. * * The first time the function is called it initializes the lookup table. */ static int _tableBitCount( unsigned int val ) { int bCount = 0; if ( !_lookupTableInitialized ) { unsigned int i; for ( i = 0; i != UCHAR_MAX + 1; ++i ) _bitCountTable[i] = ( unsigned char )_defaultBitCount( i ); _lookupTableInitialized = 1; } for ( ; val; val >>= CHAR_BIT ) bCount += _bitCountTable[val & UCHAR_MAX]; return bCount; } static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount; const char *strategyNames[] = { "onTheFly", "lookupTable" }; void setStrategy( enum strategy s ) { switch ( s ) { case onTheFly: _bitcount = _defaultBitCount; break; case lookupTable: _bitcount = _tableBitCount; break; case strategyCount: break; } } /* Just a forwarding function which will call whichever version of the * algorithm has been selected by the client */ int bitcount( unsigned int val ) { return _bitcount( val ); } #ifdef _BITCOUNT_EXE_ #include  #include  #include  /* Use the same sequence of pseudo random numbers to benmark each Hamming * Weight algorithm. */ void benchmark( int reps ) { clock_t start, stop; int i, j; static const int iterations = 1000000; for ( j = 0; j != strategyCount; ++j ) { setStrategy( j ); srand( 257 ); start = clock( ); for ( i = 0; i != reps * iterations; ++i ) bitcount( rand( ) ); stop = clock( ); printf ( "\n\t%d psudoe-random integers using %s: %f seconds\n\n", reps * iterations, strategyNames[j], ( double )( stop - start ) / CLOCKS_PER_SEC ); } } int main( void ) { int option; while ( 1 ) { printf( "Menu Options\n" "\t1.\tPrint the Hamming Weight of an Integer\n" "\t2.\tBenchmark Hamming Weight implementations\n" "\t3.\tExit ( or cntl-d )\n\n\t" ); if ( scanf( "%d", &option ) == EOF ) break; switch ( option ) { case 1: printf( "Please enter the integer: " ); if ( scanf( "%d", &option ) != EOF ) printf ( "The Hamming Weight of %d ( 0x%X ) is %d\n\n", option, option, bitcount( option ) ); break; case 2: printf ( "Please select number of reps ( in millions ): " ); if ( scanf( "%d", &option ) != EOF ) benchmark( option ); break; case 3: goto EXIT; break; default: printf( "Invalid option\n" ); } } EXIT: printf( "\n" ); return 0; } #endif 

32-bit or not ? I just came with this method in Java after reading ” cracking the coding interview ” 4th edition exercice 5.5 ( chap 5: Bit Manipulation). If the least significant bit is 1 increment count , then right-shift the integer.

 public static int bitCount( int n){ int count = 0; for (int i=n; i!=0; i = i >> 1){ count += i & 1; } return count; } 

I think this one is more intuitive than the solutions with constant 0x33333333 no matter how fast they are. It depends on your definition of “best algorithm” .

Fast C# solution using pre-calculated table of Byte bit counts with branching on input size.

 public static class BitCount { public static uint GetSetBitsCount(uint n) { var counts = BYTE_BIT_COUNTS; return n <= 0xff ? counts[n] : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8] : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff]; } public static readonly uint[] BYTE_BIT_COUNTS = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; }