¿Cómo contar el número de bits establecidos en un entero de 32 bits?

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

00000111

Se establecen tres bits.

¿Cuáles son los algoritmos para determinar el número de bits establecidos en un entero de 32 bits?

Esto se conoce como el ' Peso Hamming ', 'popcount' o 'adición lateral'.

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 en vectores de bits. Las instrucciones paralelas (como x86 popcnt, en las CPU donde es compatible) seguramente serán las más rápidas. Algunas otras arquitecturas 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 rellenado previamente puede ser muy rápido si su CPU tiene una memoria 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. (Busque cada byte por separado para mantener la tabla pequeña).

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

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

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and 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;
}

JavaScript: coaccionar a número entero con |0el rendimiento: cambiar la primera línea dei = (i|0) - ((i >> 1) & 0x55555555);

Este tiene el mejor comportamiento en el peor de los casos de cualquiera de los algoritmos discutidos, por lo que tratará de manera eficiente cualquier patrón de uso o valores que le arroje.

Cómo funciona este bithack SWAR:

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

El primer paso es una versión optimizada de enmascaramiento para aislar los bits pares / impares, cambiar para alinearlos y agregarlos. Esto efectivamente hace 16 adiciones separadas en acumuladores de 2 bits ( SWAR = SIMD dentro de un registro ). Al igual (i & 0x55555555) + ((i>>1) & 0x55555555).

El siguiente paso toma los pares / impares de esos 16x acumuladores de 2 bits y los agrega nuevamente, produciendo sumas de 8x 4 bits. La i - ...optimización no es posible esta vez, por lo que solo enmascara antes / después del cambio. Usar la misma 0x33...constante en ambas ocasiones en lugar de 0xccc...antes de cambiar es algo bueno cuando se compilan ISA que necesitan construir constantes de 32 bits en registros por separado.

El paso final de cambiar y agregar se (i + (i >> 4)) & 0x0F0F0F0Famplía a 4x acumuladores de 8 bits. Se enmascara después de agregar en lugar de antes, porque el valor máximo en cualquier acumulador de 4 bits es 4, si se establecieron los 4 bits de los bits de entrada correspondientes. 4 + 4 = 8 que todavía cabe en 4 bits, por lo que es imposible llevar entre elementos de mordisco i + (i >> 4).

Hasta ahora, esto es SIMD bastante normal usando técnicas SWAR con algunas optimizaciones inteligentes. Continuar con el mismo patrón durante 2 pasos más puede ampliarse a 2x 16 bits y luego 1x 32 bits. Pero hay una forma más eficiente en máquinas con multiplicación rápida de hardware:

Una vez que tengamos suficientes "elementos", una multiplicación con una constante mágica puede sumar todos los elementos en el elemento superior . En este caso elementos de byte. La multiplicación se realiza desplazando a la izquierda y sumando, por lo que se multiplican los x * 0x01010101resultados x + (x<<8) + (x<<16) + (x<<24). Nuestros elementos de 8 bits son lo suficientemente anchos (y tienen conteos lo suficientemente pequeños) que esto no produce acarreo en esos 8 bits superiores.

Una versión de 64 bits de esto puede hacer elementos de 8x 8 bits en un entero de 64 bits con un multiplicador 0x0101010101010101, y extraer el byte alto con >>56. Por lo tanto, no requiere ningún paso adicional, solo constantes más amplias. Esto es lo que GCC utiliza __builtin_popcountllen sistemas x86 cuando la popcntinstrucción de hardware no está habilitada. Si puede usar los componentes internos o intrínsecos para esto, hágalo para darle al compilador la oportunidad de realizar optimizaciones específicas de destino.

Con SIMD completo para vectores más anchos (por ejemplo, contando una matriz completa)

Este algoritmo SWAR bit a bit podría paralelizarse para hacerse en múltiples elementos vectoriales a la vez, en lugar de en un solo registro de enteros, para acelerar las CPU con SIMD pero sin instrucción popcount utilizable. (por ejemplo, código x86-64 que debe ejecutarse en cualquier CPU, no solo Nehalem o posterior).

Sin embargo, la mejor manera de usar instrucciones de vectores para popcount es usualmente usando una combinación aleatoria variable para hacer una búsqueda en la tabla de 4 bits a la vez de cada byte en paralelo. (Los 4 bits indexan una tabla de 16 entradas contenida en un registro vectorial).

En las CPU Intel, la instrucción popcnt de hardware de 64 bits puede superar a una implementación SSSE3 PSHUFBen paralelo en un factor de 2, pero solo si su compilador lo hace bien . De lo contrario, SSE puede salir significativamente adelante. Las versiones más recientes del compilador son conscientes del problema popcnt de dependencia falsa 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)

Considere también las funciones integradas de sus compiladores.

En el compilador de GNU, por ejemplo, puede usar:

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

En el peor de los casos, el compilador generará una llamada a una función. En el mejor de los casos, el compilador 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 corriente principal en la arquitectura x86, por lo que tiene sentido comenzar a usar lo intrínseco ahora. Otras arquitecturas tienen el popcount por años.

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

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

MSVC proporciona un intrínseco para la popcntinstrucción x86 , pero a diferencia de gcc, es realmente intrínseco para la instrucción de hardware y requiere soporte de hardware.

Usando en std::bitset<>::count()lugar de un incorporado

En teoría, cualquier compilador que sepa explotar eficientemente para la CPU de destino debería exponer esa funcionalidad a través de ISO C ++ std::bitset<>. En la práctica, podría ser mejor con el bit-hack AND / shift / ADD en algunos casos para algunas CPU de destino.

Para las arquitecturas de destino donde el popcount de hardware es una extensión opcional (como x86), no todos los compiladores tienen una std::bitsetventaja que se aprovecha cuando está disponible. Por ejemplo, MSVC no tiene forma de habilitar el popcntsoporte en tiempo de compilació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 una cuenta de hardware para arquitecturas que lo admiten.

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

Vea asm de gcc, clang, icc y MSVC en el explorador del compilador Godbolt.

x86-64 gcc -O3 -std=gnu++11 -mpopcntemite 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

gcc -O3 -std=gnu++11Emite PowerPC64 (para la intversión arg):

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

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

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

En mi opinión, la "mejor" solución es la que puede leer otro programador (o el programador original dos años después) sin comentarios copiosos. Es posible que desee la solución más rápida o inteligente que algunos ya han proporcionado, pero prefiero la legibilidad a la 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 la documente bien para ayudar a sus sucesores), puede usar una búsqueda de tabla:

// 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  A  B  C  D  E  F (<- 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 tipo de datos específicos, por lo que 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 desea portabilidad, me quedaría con la solución legible.

De Hacker's Delight, pág. 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 ~ 20-ish instrucciones (dependiente del arco), sin ramificación.

Hacker's Delight es una delicia! Muy recomendable.

Creo que la forma 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 el número total de bits establecidos dividiendo en dos mitades, contando el número de bits establecidos en ambas mitades y luego sumando. También se conoce como Divide and Conquerparadigma. Vamos a entrar en detalles ...

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

El número de bits en dos bits puede ser 0b00, 0b01o 0b10. Vamos a tratar 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 dos bits es >= 2 (0b10)entonces andproduce 0b01, de lo que produce 0b00.

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

Esta declaración debe ser fácil de entender. Después de la primera operación tenemos el recuento de bits establecidos en cada dos bits, ahora sumamos 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 el recuento total de bits establecidos en 4 bits. La última declaración es la más complicada.

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

Vamos a desglosarlo aún más ...

v + (v >> 4)

Es similar a la segunda declaración; Estamos contando los bits establecidos en grupos de 4 en su lugar. Sabemos, debido a nuestras operaciones anteriores, que cada mordisco tiene la cuenta 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 sumamos esos mordiscos juntos.

0b01000010 + 0b01000000

Nos da el recuento de bits establecidos en un byte, en el primer mordisco 0b01100010y, 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 en él. Necesitamos sumarlos todos juntos. El truco consiste en multiplicar el resultado por el 0b10101010que tiene una propiedad interesante. Si nuestro número tiene cuatro bytes, A B C Ddará como resultado un nuevo número con estos bytes A+B+C+D B+C+D C+D D. Un número de 4 bytes puede tener un máximo de 32 bits establecido, que se puede representar como 0b00100000.

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

Me aburrí y cronometré mil millones de iteraciones de tres enfoques. El compilador es gcc -O3. CPU es lo que sea que pusieron en el Macbook Pro de primera generación.

La más rápida es la siguiente, con 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 buscando 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 tardó 8,6 segundos.

El cuarto lugar es para __builtin_popcount () de GCC, con 11 segundos vergonzosos.

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

Entonces, si le importa el rendimiento por encima de todo, utilice el primer enfoque. Si le importa, pero no lo suficiente como para gastar 64Kb de RAM, use el segundo enfoque. 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 desee utilizar el enfoque de giro de bits.

Editar: resultados similares aquí .

Si está utilizando Java, el método incorporado Integer.bitCountlo 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 explicarte este algoritmo.

Este algoritmo se basa en el algoritmo de división y conquista. Supongamos que hay un número entero de 8 bits 213 (11010101 en binario), el algoritmo funciona así (cada vez que combina dos bloques vecinos):

+-------------------------------+
| 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 en las que es útil conocer su microarquitectura. Acabo de cronometrar dos variantes en gcc 4.3.3 compiladas con -O3 usando líneas en C ++ para eliminar la sobrecarga de llamadas a funciones, mil millones de iteraciones, manteniendo la suma de todos los conteos para asegurar que el compilador no elimine nada importante, usando rdtsc para el tiempo ( ciclo de reloj preciso).

en línea int pop2 (sin signo x, sin signo y)
{
    x = x - ((x >> 1) y 0x55555555);
    y = y - ((y >> 1) y 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
    x = (x + (x >> 4)) y 0x0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    y = y + (y >> 8);
    x = x + (x >> 16);
    y = y + (y >> 16);
    retorno (x + y) & 0x000000FF;
}

El Hacker's Delight no modificado tomó 12,2 gigaciclos. Mi versión paralela (contando el doble de bits) se ejecuta en 13.0 gigaciclos. Transcurrieron 10.5s en total para ambos juntos en un Core Duo de 2.4GHz. 25 gigaciclos = poco más de 10 segundos a 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. Casi podría 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 reducir algunos cambios. La versión de 64 bits con algunos pequeños ajustes saldría parejo, pero volvería a contar el doble de bits.

Con 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 razón para que el código sea especialmente transparente. La interfaz es simple, el algoritmo puede ser referenciado en línea en muchos lugares, y es susceptible de una prueba de unidad integral. El programador que se topa con él podría incluso aprender algo. Estas operaciones de bits son extremadamente naturales a nivel de máquina.

OK, decidí probar la versión modificada de 64 bits. Para este un tamaño de (sin firmar largo) == 8

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

Eso parece correcto (aunque no estoy probando con cuidado). Ahora los tiempos salen en 10.70 gigacycles / 14.1 gigacycles. 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 corriendo en modo de 64 bits y le gustan los registros de 64 bits un poco mejor que los registros de 32 bits.

Veamos si hay un poco más de tubería de OOO aquí. Esto fue un poco más complicado, así que en realidad lo probé un poco. Cada término solo suma 64, todos combinados suman 256.

inline int pop4 (unsigned long x, unsigned long y, 
                sin signo largo u, sin signo largo v)
{
  enumeración {m1 = 0x5555555555555555, 
         m2 = 0x3333333333333333, 
         m3 = 0x0F0F0F0F0F0F0F0F, 
         m4 = 0x000000FF000000FF};

    x = x - ((x >> 1) y 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 & m4; 
    x = x + (x >> 32);
    devuelve x & 0x000001FF;
}

Estuve emocionado por un momento, pero resulta que gcc está jugando trucos en línea con -O3 aunque no estoy usando la palabra clave en línea en algunas pruebas. Cuando dejé que gcc jugara trucos, mil millones de llamadas a pop4 () toma 12.56 gigaciclos, pero determiné que estaba doblando argumentos como expresiones constantes. Un número más realista parece ser 19.6 gc para otro 30% de aceleración. Mi ciclo de prueba ahora se ve así, asegurándome 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) 
      suma + = pop4 (i, i ^ 1, ~ i, i | 1); 
   hitime e4 = rdtsc (); 

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

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

¿Por qué no dividir iterativamente por 2?

cuenta = 0
mientras n> 0
  si (n% 2) == 1
    cuenta + = 1
  n / = 2  

Estoy de acuerdo en que este no es el más rápido, pero el "mejor" es algo ambiguo. Yo diría que "lo mejor" debería tener un elemento de claridad

El giro de bits del Hacker's Delight se vuelve mucho más claro cuando escribes los patrones de 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 suma de bits en cada dos. Los otros pasos agregan fragmentos de orden superior a fragmentos de orden bajo, duplicando el tamaño del fragmento hasta el final, hasta que el conteo final ocupe todo el int.

Para un medio feliz entre una tabla de búsqueda 2 ³² e iterar a través de 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

Esto se puede hacer en O(k), donde kes el número de bits establecido.

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

No es la mejor solución ni la más rápida, pero encontré la misma pregunta en mi camino y comencé a pensar y pensar. Finalmente, me di cuenta de que se puede hacer así si obtiene el problema desde el lado matemático y dibuja un gráfico, luego descubre 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);
    }
}

La función que busca a menudo se denomina "suma lateral" o "recuento de población" de un número binario. Knuth lo analiza en el pre-Fascículo 1A, pp11-12 (aunque hubo una breve referencia en el Volumen 2, 4.6.3- (7)).

El locus classicus es el artículo de Peter Wegner "Una técnica para contar unos en una computadora binaria", de Communications of the ACM , Volumen 3 (1960) Número 5, página 322 . Da dos algoritmos diferentes allí, uno optimizado para los números que se espera que sean "escasos" (es decir, que tengan un pequeño número de unos) y otro para el caso contrario.

  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;
    }

Pocas preguntas abiertas: -

1. Si el número es negativo, entonces?
2. Si el número es 1024, el método "dividir iterativamente por 2" iterará 10 veces.

podemos modificar el algo para admitir el número negativo de la siguiente manera:

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

ahora para superar el segundo problema podemos escribir algo como:

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

para referencia completa ver:

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

Creo que el método de Brian Kernighan también será útil ... Pasa por tantas iteraciones como bits establecidos. Entonces, si tenemos una palabra de 32 bits con solo el conjunto de bits alto, entonces solo pasará una vez por el ciclo.

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; 
}

Publicado en 1988, el lenguaje de programación C 2nd Ed. (por Brian W. Kernighan y Dennis M. Ritchie) menciona esto en el ejercicio 2-9. El 19 de abril de 2006, Don Knuth me señaló que este método "fue publicado por primera vez por Peter Wegner en CACM 3 (1960), 322. (También descubierto independientemente por Derrick Lehmer y publicado en 1964 en un libro editado por Beckenbach)".

Yo uso el siguiente código que es más intuitivo.

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

Lógica: n & (n-1) restablece el último bit establecido de n.

PD: Sé que esto no es una solución O (1), aunque es una solución interesante.

¿Qué quieres decir con "Mejor algoritmo"? ¿El código en corto o el código en ayunas? Su código se ve muy elegante y tiene un tiempo de ejecución constante. El código también es muy corto.

Pero si la velocidad es el factor principal y no el tamaño del código, creo que lo siguiente puede ser más rápido:

       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 );
        }

Creo que esto no será más rápido para un valor de 64 bits, pero un valor de 32 bits puede ser más rápido.

Escribí una macro de conteo de bits rápido para máquinas RISC alrededor de 1990. No utiliza aritmética avanzada (multiplicación, división,%), recuperaciones de memoria (demasiado lenta), ramas (demasiado lenta), pero asume que la CPU tiene un Desplazador de barril de 32 bits (en otras palabras, >> 1 y >> 32 toman la misma cantidad de ciclos). Se supone que las constantes pequeñas (como 6, 12, 24) no cuestan nada cargar en los registros, o se almacenan en temporarios y reutilizados una y otra vez.

Con estos supuestos, cuenta 32 bits en aproximadamente 16 ciclos / instrucciones en la mayoría de las máquinas RISC. Tenga en cuenta que 15 instrucciones / ciclos está cerca de un límite inferior en el número de ciclos o instrucciones, porque parece tomar al menos 3 instrucciones (máscara, turno, operador) para reducir el número de sumandos a la mitad, por lo que log_2 (32) = 5, 5 x 3 = 15 instrucciones es un cuasi-inferior.

#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;

Aquí hay un secreto para el primer y más complejo paso:

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

así que si tomo la primera columna (A) arriba, la desplazo a la derecha 1 bit y la resto de AB, obtengo la salida (CD). La extensión a 3 bits es similar; puede verificarlo con una tabla booleana de 8 filas como la mía anterior si lo desea.

• Don gillies

Si está utilizando C ++, otra opción es utilizar la metaprogramación de plantilla:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

el uso sería:

// 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 )

por supuesto, podría ampliar aún más esta plantilla para usar diferentes tipos (incluso el tamaño de bits de autodetección) pero lo he mantenido simple para mayor claridad.

editar: olvidé mencionar que esto es bueno porque debería funcionar en cualquier compilador de C ++ y, básicamente, simplemente desenrolla el bucle si se usa un valor constante para el conteo de bits (en otras palabras, estoy bastante seguro de que es el método general más rápido encontrarás)

Me gusta especialmente este ejemplo del archivo de la fortuna:

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

¡Me gusta más porque es muy bonita!

Java JDK1.5

Integer.bitCount (n);

donde n es el número cuyos 1 se deben contar.

comprobar también

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);
         }

Encontré una implementación de conteo de bits en una matriz usando instrucciones SIMD (SSSE3 y AVX2). Tiene un rendimiento 2-2.5 veces mejor que si usara la función intrínseca __popcnt64.

Versión SSSE3:

#include <smmintrin.h>
#include <stdint.h>

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];
}

Versión AVX2:

#include <immintrin.h>
#include <stdint.h>

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];
}

Siempre uso esto en programación competitiva y es fácil de escribir y eficiente:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

Hay muchos algoritmos para contar los bits establecidos; ¡Pero creo que el mejor es el más rápido! Puedes ver lo detallado en esta página:

Bit Twiddling Hacks

Sugiero este:

Contando bits establecidos en palabras de 14, 24 o 32 bits utilizando instrucciones de 64 bits

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;

Este método requiere una CPU de 64 bits con división rápida de módulo para ser eficiente. La primera opción solo requiere 3 operaciones; la segunda opción toma 10; y la tercera opción toma 15.

Solución rápida de C # que utiliza una tabla precalculada de recuentos de bits de bytes con ramificación en el tamaño de entrada.

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
    };
}

Aquí hay un módulo portátil (ANSI-C) que puede comparar cada uno de sus algoritmos en cualquier arquitectura.

¿Tu CPU tiene bytes de 9 bits? No hay problema :-) Por el momento implementa 2 algoritmos, el algoritmo K&R y una tabla de búsqueda de bytes. La tabla de búsqueda es en promedio 3 veces más rápida que el algoritmo K&R. Si alguien puede encontrar una manera de hacer que el algoritmo "Hacker's Delight" sea portátil, no dude en agregarlo.

#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_

/* Return the Hamming Wieght of val, i.e. 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 <limits.h>

#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 <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 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

lo que puedes hacer es

while(n){
    n=n&(n-1);
    count++;
}

La lógica detrás de esto es que los bits de n-1 se invierten del bit establecido más a la derecha de n. si n = 6, es decir, 110, entonces 5 es 101, los bits se invierten del bit establecido más a la derecha de n. así que si nosotros y estos dos haremos el bit 0 más a la derecha en cada iteración y siempre vamos al siguiente bit establecido más a la derecha. Por lo tanto, contando el bit establecido. La peor complejidad de tiempo será O (log) cuando cada bit esté configurado.