¿Cómo funciona esta manipulación de bits en Java?

Question

Estaba investigando cómo Java cuenta los bits de un int.
que tenía en mi mente algo tan simple como este (que creo que es correcto):

public static int bitCount(int number){ 
     final int MASK = 0x1; 
     int count = 0; 

     for(int i = 0; i < 32; i++){ 
      if(((number >>> i) & MASK) == MASK){ 
       count++; 
      } 
     } 
     return count; 
    } 

su lugar me encontré con un método que no tengo absolutamente ni idea de lo que está haciendo (parece que la magia para mí):

i = i - ((i >>> 1) & 0x55555555); 
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 
i = (i + (i >>> 4)) & 0x0f0f0f0f; 
i = i + (i >>> 8); 
i = i + (i >>> 16); 
return i & 0x3f; 

¿Alguien podría ayudarme a entender lo que hace esto y por qué una función simple como la que pensé fue/podría ser mala?

Answer 1

Claro

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

El patrón de bits de 5 es 0101 (cuatro bits), por lo que la máscara es una repetición de la configuración de bits 01 dieciséis veces. Esta línea cuenta el número de bits en cada par de dos bits del número. Si tiene en cuenta los pares de dos bits, (i >>> 1) & 0x1 obtiene el bit de orden superior en la posición de orden inferior. Ahora, hay cuatro posibles configuraciones de dos bits

00 ~> 00 - 00 = 00 
01 ~> 01 - 00 = 01 
10 ~> 10 - 01 = 01 
11 ~> 11 - 01 = 10 

y cada par de dos bits ahora contiene el número de bits de la original tenía en esas posiciones.

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

A continuación, contamos los bits que había en cada grupo de cuatro bits (también conocido como nibble). Enmascarando un nibble con 0x3 = 0011(b), obtenemos el recuento de bits que estaban en los dos bits de orden inferior del nibble, y (i >>> 2) & 0x3 obtiene el recuento de los dos bits de mayor orden del nibble. Estos conteos ahora se agregan. Como cada conteo fue como máximo 2, la suma es como máximo 4, por lo tanto, no sale del mordisco.

i = (i + (i >>> 4)) & 0x0f0f0f0f; 

Ahora se cuentan los bits en cada octeto. Cada nibble contiene el recuento de bits establecidos en el original en ese lugar. Al desplazar a la derecha en cuatro bits, se mueve el recuento desde el mordisqueo de orden superior en cada lugar hasta el mordisco de orden inferior, estos se agregan. Luego, también movimos el recuento del nibble de orden inferior al nible de orden superior del octeto adyacente, que está enmascarado por el & 0x0f0f0f0f. Dado que cada octeto puede tener como máximo ocho bits establecidos, el recuento no deja el nibble de orden inferior del octeto.

i = i + (i >>> 8); 

Ahora agregamos los recuentos de los pares de octetos adyacentes.

i = i + (i >>> 16); 

Ahora agregamos los totales de los recuentos en los dos octetos de orden superior y los dos de orden inferior.

return i & 0x3f; 

Por último, todos los octetos excepto el octeto de orden más bajo se enmascaran a cabo, ya que los octetos de orden superior aún contenían los recuentos intermedios.

La razón por la cual su implementación simple podría considerarse mala es el rendimiento. El intrincado truco de bits utiliza menos operaciones y no tiene ramas, por lo que es más rápido. Sin embargo, es mucho más fácil equivocarse.

Otra clara forma de contar los bits fijados en un int (o long) es

public static int bitCount(int n) { 
    int count = 0; 
    while(n != 0) { 
     ++count; 
     n = n & (n-1); 
    } 
    return count; 
} 

Eso funciona porque n = n & (n-1) para borrar el último bit activado en n y deja todo lo demás intacto. Si el patrón de bits de n termina con

...100...0 

el patrón de bits de n-1 es

...011...1 

y los bits antes de la última de 1 bit en n son los mismos. En Java, también se garantiza que funciona para números negativos porque el desbordamiento entero tiene semántica envolvente, por lo que si n = Integer.MIN_VALUE, el patrón de bits es 100...0 y n - 1 se convierte en Integer.MAX_VALUE con el patrón de bits 011...1.

Answer 2

el método genial solo funciona ya que la computadora tiene un rango finito de valores para int. no funcionará (y otros algoritmos de bits interesantes) tan fácilmente para un rango infinito (como BigInteger) ya que necesita conocer todas las máscaras necesarias antes del cálculo.

en cualquier caso, se puede leer cómo funciona a través de: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

que está en la parte inferior de este capítulo.