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

Este grupo de trabajo ha estado mucho tiempo buscando la resolución a tus preguntas, te dejamos la respuesta así que nuestro deseo es servirte de mucha apoyo.

Solución:

Bien, repasemos el 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 expresion ((i >> 1) & 0x55555555) así cambia los bits de i a la derecha por uno, y luego pone a cero todos los bits pares. (De manera equivalente, primero podríamos haber establecido todos los bits impares de i a cero con & 0xAAAAAAAA y luego desplazó el resultado un bit a la derecha). Por conveniencia, llamemos a este valor intermedio j.

¿Qué pasa cuando restamos este j del original i? Bueno, veamos qué pasaría si i sólo tenía 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 tiene más de dos bits establecidos? De hecho, es bastante fácil comprobar que los dos bits más bajos de i - j seguirá siendo dado por la tabla de arriba, y también lo harán el tercer y cuarto bits, y el quinto y sexto bits, y así y. En particular:

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

• ya 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: así, los dos bits más bajos de i Tampoco puede 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 de los 16 bloques de dos bits en ien paralelo. Es decir, después de ejecutar esta línea, los dos bits más bajos del nuevo valor de i ahora contendrá el número de bits establecidos entre los bits correspondientes en el valor original de iy también los dos bits siguientes, y así sucesivamente.

Línea 2:

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

Comparado con la primera línea, esta es bastante simple. Primero, tenga en cuenta que

0x33333333 = 0b00110011001100110011001100110011

Por lo tanto, i & 0x33333333 toma los recuentos de dos bits calculados anteriormente y desecha cada segundo uno de ellos, mientras que (i >> 2) & 0x33333333 hace lo mismo después cambiando i a la derecha por dos bits. Luego sumamos los resultados.

Por lo tanto, en efecto, lo que hace esta línea es tomar el recuento de bits de los dos bits más bajos y los dos bits del segundo más bajo de la entrada original, calculados en la línea anterior, y sumarlos para obtener el recuento de bits del más bajo. cuatro bits de la entrada. Y, de nuevo, 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í?

Pues, ante todo, (i + (i >> 4)) & 0x0F0F0F0F hace exactamente lo mismo que la línea anterior, excepto que agrega el adyacente cuatro bits recuentos de bits juntos para dar los recuentos de bits de cada ocho bits bloque (es decir, byte) de la entrada. (Aquí, a diferencia de la línea anterior, podemos salirse con la nuestra moviendo el & fuera de la adición, ya que sabemos que el recuento de bits 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 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, ya que 0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1, tenemos:

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

Por lo tanto, la mas alto byte del resultado termina siendo la suma de:

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

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

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

PD. Este código podría extenderse fácilmente a números enteros de 64 bits, simplemente cambiando el 0x01010101 para 0x0101010101010101 y el >> 24 para >> 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.

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

Este es un comentario a la respuesta de Ilamari. Lo pongo 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 reescribir (1) y (2) para aclarar la explicación:

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

Queremos demostrar que (3) se puede derivar de (4).

i se puede escribir como la suma 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)

Desde el meven máscara borra el último trozo 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

Te mostramos reseñas y calificaciones

Si crees que te ha sido provechoso este post, nos gustaría que lo compartas con más programadores y nos ayudes a extender nuestro contenido.

---

---

Utiliza Nuestro Buscador