c++ - ¿Cómo funciona este algoritmo para contar el número de bits establecidos en un entero de 32 bits?

algorithm hammingweight

Question

int SWAR(unsigned int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

He visto este código que cuenta el número de bits igual a 1 en un entero de 32 bits, y noté que su rendimiento es mejor que __builtin_popcount pero no puedo entender cómo funciona.

¿Alguien puede dar una explicación detallada de cómo funciona este código?

Answer 1

Este es un comentario a la respuesta de Ilamari . Lo puse como respuesta debido a problemas de formato:

Línea 1:

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

Esta línea se deriva de esta línea más fácil de entender :

i = (i & 0x55555555) + ((i >> 1) & 0x55555555);  // (2)

Si llamamos

i = input value
j0 = i & 0x55555555
j1 = (i >> 1) & 0x55555555
k = output value

Podemos volver a escribir (1) y (2) para que la explicación sea más clara:

k =  i - j1; // (3)
k = j0 + j1; // (4)

Queremos demostrar que (3) puede derivarse de (4).

Se puede escribir como la adición de sus bits pares e impares (contando el bit más bajo como bit 1 = impar):

i = iodd + ieven =
  = (i & 0x55555555) + (i & 0xAAAAAAAA) =
  = (i & modd) + (i & meven)

Como la máscara meven borra el último bit de i , la última igualdad se puede escribir de esta manera:

i = (i & modd) + ((i >> 1) & modd) << 1 =
  = j0 + 2*j1

Es decir:

j0 = i - 2*j1    (5)

Finalmente, reemplazando (5) en (4) logramos (3):

k = j0 + j1 = i - 2*j1 + j1 = i - j1

Answer 2

OK, vamos a ir a través del código línea por línea:

Línea 1:

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

En primer lugar, el significado de la constante 0x55555555 es que, escrito usando la notación literal binaria de estilo Java / GCC),

0x55555555 = 0b01010101010101010101010101010101

Es decir, todos sus bits impares (contando el bit más bajo como bit 1 = impar) son 1 , y todos los bits pares son 0 .

La expresión ((i >> 1) & 0x55555555) tanto, desplaza los bits de i derecha, y luego establece todos los bits pares a cero. (De manera equivalente, primero podríamos establecer todos los bits impares de i en cero con & 0xAAAAAAAA y luego cambiar el resultado a la derecha en un bit). Por conveniencia, llamemos a este valor intermedio j .

¿Qué sucede cuando restamos este j del i original? Bueno, veamos que pasaría si solo tuviera dos bits:

    i           j         i - j
----------------------------------
0 = 0b00    0 = 0b00    0 = 0b00
1 = 0b01    0 = 0b00    1 = 0b01
2 = 0b10    1 = 0b01    1 = 0b01
3 = 0b11    1 = 0b01    2 = 0b10

¡Oye! ¡Hemos logrado contar los bits de nuestro número de dos bits!

OK, pero ¿y si i más de dos bits configurados? De hecho, es bastante fácil comprobar que los dos bits más bajos de i - j todavía estarán dados por la tabla anterior, y también lo serán los bits tercero y cuarto , y los bits quinto y sexto, y así y. En particular:

• a pesar de la >> 1 , los dos bits más bajos de i - j no se ven afectados por el tercer bit o superior de i , ya que estarán enmascarados fuera de j por el & 0x55555555 ; y

• dado que los dos bits más bajos de j nunca pueden tener un valor numérico mayor que los de i , la resta nunca tomará prestado del tercer bit de i : por lo tanto, los dos bits más bajos de i tampoco pueden afectar a los terceros bits o superiores de i - j .

De hecho, al repetir el mismo argumento, podemos ver que el cálculo en esta línea, en efecto, aplica la tabla anterior a cada uno de los 16 bloques de dos bits en i en paralelo . Es decir, después de ejecutar esta línea, los dos bits más bajos del nuevo valor de i ahora contendrán el número de bits establecidos entre los bits correspondientes en el valor original de i , y también lo harán los dos bits siguientes, y así sucesivamente.

Línea 2:

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

En comparación con la primera línea, esta es bastante simple. En primer lugar, tenga en cuenta que

0x33333333 = 0b00110011001100110011001100110011

Por lo tanto, i & 0x33333333 toma los conteos de dos bits calculados anteriormente y desecha cada uno de ellos, mientras que (i >> 2) & 0x33333333 hacen lo mismo después de desplazar i derecha en dos bits. Luego sumamos los resultados juntos.

Por lo tanto, en efecto, lo que hace esta línea es tomar las cuentas de bits de los dos bits más bajos y los dos bits más bajos de la entrada original, calculados en la línea anterior, y sumarlos para obtener la cuenta de bits de los cuatro bits más bajos de la entrada. entrada. Y, nuevamente, lo hace en paralelo para todos los 8 bloques de cuatro bits (= dígitos hexadecimales) de la entrada.

Línea 3:

return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;

OK, ¿qué está pasando aquí?

Bueno, primero que todo, (i + (i >> 4)) & 0x0F0F0F0F hace exactamente lo mismo que la línea anterior, excepto que agrega las cuentas de bits de cuatro bits adyacentes para dar las cuentas de bits de cada bloque de ocho bits (es decir, byte ) de la entrada. (Aquí, a diferencia de la línea anterior, podemos salir moviendo el & fuera de la adición, ya que sabemos que el bitcount de ocho bits nunca puede exceder de 8, y por lo tanto cabrá dentro de cuatro bits sin desbordarse).

Ahora tenemos un número de 32 bits que consta de cuatro bytes de 8 bits, cada byte que contiene el número de 1 bit en ese byte de la entrada original. (Llamemos a estos bytes A , B , C y D ). Entonces, ¿qué sucede cuando multiplicamos este valor (llamémoslo k ) por 0x01010101 ?

Bueno, desde 0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1 , tenemos:

k * 0x01010101 = (k << 24) + (k << 16) + (k << 8) + k

Así, el byte más alto del resultado termina siendo la suma de:

• Su valor original, debido al término k , más
• el valor del siguiente byte inferior, debido al término k << 8 , más
• el valor del segundo byte inferior, debido al término k << 16 , más
• el valor del cuarto y más bajo byte, debido al término k << 24 .

(En general, también podría haber acarreos desde bytes inferiores, pero como sabemos que el valor de cada byte es a lo sumo 8, sabemos que la adición nunca se desbordará y creará un acarreo).

Es decir, el byte más alto de k * 0x01010101 termina siendo la suma de las cuentas de bits de todos los bytes de la entrada, es decir, la cuenta de bits total del número de entrada de 32 bits. El >> 24 final luego simplemente cambia este valor hacia abajo desde el byte más alto al más bajo.

PD. Este código podría extenderse fácilmente a enteros de 64 bits, simplemente cambiando el 0x01010101 a 0x0101010101010101 y el >> 24 a >> 56 . De hecho, el mismo método funcionaría incluso para enteros de 128 bits; Sin embargo, 256 bits requerirían agregar un paso adicional de cambio / agregar / máscara, ya que el número 256 ya no encaja en un byte de 8 bits.

Answer 3

Prefiero este, es mucho más fácil de entender.

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