Pregunta ¿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?


751


origen


Respuestas:


Esto se conoce como 'Hamming peso',' 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 sobre vectores de bits. Las instrucciones paralelas (como x86 popcnt, en las CPU donde es compatible) será casi con certeza el más rápido. Algunas otras arquitecturas pueden tener una instrucción lenta implementada con un ciclo 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 en un idioma 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, el código x86-64 que se debe ejecutar 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 de Intel, el hardware de 64 bits de instrucción popcnt puede superar a un SSSE3 PSHUFB implementación bit-parallel por alrededor de un factor de 2, pero solo si tu compilador lo hace bien. De lo contrario, SSE puede salir significativamente adelante. Las versiones de compilador más nuevas conocen el popcnt falsa dependencia  problema 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)


764



También considere las funciones incorporadas de sus compiladores.

En el compilador 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 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 la cuenta durante años.


En x86, puede decirle al compilador que puede asumir soporte para popcnt instrucción con -mpopcnt o -msse4.2 para habilitar también las instrucciones vectoriales que se agregaron en la misma generación. Ver Opciones de GCC x86. -march=nehalem (o -march= cualquier CPU que desee que su código asuma 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 hacer binarios optimizados para la máquina en la que los construyes, utiliza -march=native  (con gcc, clang o ICC).

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


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

En teoría, cualquier compilador que sepa cómo contar de forma eficiente para la CPU objetivo 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 arquitecturas de destino donde hardware popcount es una extensión opcional (como x86), no todos los compiladores tienen una std::bitset que lo aprovecha cuando está disponible. Por ejemplo, MSVC no tiene forma de habilitar popcnt soporte en tiempo de compilación, y siempre usa una tabla de búsqueda, 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 arquitecturas que lo soportan.

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

Ver asm de gcc, clang, icc y MSVC en el explorador del compilador 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 emite (para el int versió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 para x86 o específica de GNU, pero solo 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 tablas byte-a-time. Esto no es maravilloso para ARM, por ejemplo.


185



En mi opinión, la "mejor" solución es la que puede leer otro programador (o el programador 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  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 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.


168



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 ¡encantador! Muy recomendable.


94



Creo que es la manera más rápida, sin usar tablas de búsqueda y popcount-es el 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 sumarlos. También conocido como Divide and Conquer paradigma. Vamos a entrar en detalles ...

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

La cantidad 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) entonces and produce 0b01de lo contrario, produce 0b00.

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

Esta declaración 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 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 la cuenta total de bits establecidos en 4 bits. La última declaración 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 declaración; 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 mordisco 0b01100010 y por lo tanto, enmascaramos los últimos cuatro bytes de todos los bytes en el número (descartándolos).

0b01100010 & 0xF0 = 0b01100000

Ahora cada byte tiene el recuento de bits establecidos. Necesitamos sumarlos todos juntos. El truco es multiplicar el resultado por 0b10101010 que tiene una propiedad interesante. Si nuestro número tiene cuatro bytes, A B C D, dará 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 configurados, que se pueden 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 conseguimos >> 24. Este algoritmo fue diseñado para 32 bit palabras, pero se pueden modificar fácilmente para 64 bit palabras.


69



Me aburrí y cronometré mil millones de iteraciones de tres enfoques. El compilador 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í.


53



Si está usando Java, el método incorporado Integer.bitCount lo haré.


52



Esta es una de esas preguntas donde ayuda a 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 de función, mil millones de iteraciones, manteniendo la suma corriente de todos los conteos para asegurar que el compilador 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 + y 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 integral de la unidad. El programador 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 suma 64, suma 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 sumados 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 sumados en 9.5s transcurridos. Entonces hay otro 20% Ahora a 800ms por 32 billones de bits.


28



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

28