n & -n devuelve el 1 bit más a la derecha en n .
Una nota rápida para las personas que no están familiarizadas con la sintaxis tipo C: el operador & es un AND bit a bit. Esto significa tomar dos números y combinarlos bit por bit, produciendo un 1 solo si ambas entradas son también 1. Aquí hay un ejemplo rápido:
11010101 01001100 -------- 01000100
Ahora, veamos cómo funciona la negación con números binarios. En general, almacenamos enteros como 1 o 2 como números de 32 o 64 bits. Sin embargo, por simplicidad, imaginemos que solo estamos trabajando con 8 bits; los principios son los mismos. Entonces 11, por ejemplo, se vería así:
- ¿Cuál es la prueba de primitiva determinista más rápida?
- Coloque números de cinco bits en los vértices de un hipercubo de 9 dimensiones de modo que, desde cualquier vértice, pueda alcanzar cualquier número en no más de dos movimientos a lo largo de los bordes del hipercubo.
- ¿Qué ventaja tiene la lógica difusa en las ollas arroceras sobre la lógica digital / sensor convencional?
- ¿Cuál es un ejemplo de un operador XOR que utiliza conceptos del mundo real?
- ¿Por qué el Complemento 2 se llama Complemento 2 '?
00001011
Una manera simple de hacer negación es el llamado “complemento de uno”. Para hacer un número negativo, todo lo que hacemos es voltear todos los bits. Entonces -11 sería:
11110100
Si este fuera realmente el método que utilizamos, entonces n & -n siempre sería 0. Dado que complementamos el número, ¡ni un solo bit permanece sin cambios!
Sin embargo, en realidad, utilizamos un método ligeramente diferente para hacer la negación: “complemento de dos”. Para obtener -11, primero volteamos todos los bits y luego agregamos 1 al resultado. Entonces obtendríamos:
11110101
Como agregamos 1 al resultado anterior, siempre habrá exactamente 1 bit que sea 1 entre ambos números. En este caso, es el bit más a la derecha, por lo que 11 y -11 es 1. La razón por la que funcionó es que no tuvimos que cargar ningún bit después de sumar 1 al número complementado.
Ahora veamos 12 y -12. 12 es 00001100 ; la versión invertida es 11110011 . Si agregamos 1 a 11110011 , necesitaríamos llevar dos veces: 11110100 . Ahora mira cómo se juntan:
00001100 11110100 -------- 00000100
Entonces, el resultado de 12 y -12 es 4, que es el bit al que teníamos que llevar nuestra adición. ¡Y esto siempre es igual al 1 más a la derecha en el número positivo!
Por eso, n & -n devuelve el 1 bit más a la derecha en n. También tenga en cuenta cómo, gracias al complemento de dos, el 1 bit más a la derecha en n es también el 1 bit más a la derecha en -n.
Trucos similares
Una buena fuente para encontrar trucos similares de bit-twiddling es el libro Hacker’s Delight que contiene un montón de tales trucos, que varían en complejidad, con explicaciones.
Otra opción es escribir un programa de computadora que busque programas eficientes de giro de bits como este: un superoptimizador. El sitio web de Hacker’s Delight en realidad contiene un superoptimizador muy simple al que llama “Asistente de Hacker”.
El libro también ha sido una fuente de puntos de referencia para nuevos sistemas de superoptimización como STOKE. ¡En algunos casos, el superoptimizador incluso logró encontrar programas algorítmicamente distintos para las mismas tareas!
