Bucle sobre la permutación de bits de una en una

Question

Una cadena de bits se define por una secuencia de unos y ceros, por ejemplo "0101110111". Equivalentemente, se define por un número entero como su representación binaria.

Quiero calcular una cierta función de una cadena de bits para todas las cadenas de bits de una cierta longitud $l$ . Esto equivale a calcular dicha función para todos los números enteros desde 0 hasta $2^l-1$

Quiero optimizar mi código haciendo menos cálculos. He observado que si la diferencia entre la cadena de bits anterior y la siguiente es sólo de 1 bit arbitrario (por ejemplo, para "110010" y "111010" sólo difiere el 3er bit), el resultado de la función para la cadena de bits anterior puede reutilizarse para reducir significativamente el coste de cálculo de la función para la cadena de bits siguiente.

Pregunta: ¿Existe un algoritmo sencillo para recorrer todas las cadenas de bits de longitud $l$ de forma que la diferencia entre dos cadenas de bits consecutivas sea de sólo 1 bit.

B 00 -> 01 -> 10 -> 11: el segundo paso tiene una diferencia de 2 bits

Buen ejemplo de longitud 2: 00 -> 01 -> 11 -> 10: todos los pasos tienen una diferencia de sólo 1 bit

Answer 1

Lo que buscas se llama Código gris . Hay muchas maneras de construir algo así (hay 9 secuencias, después de considerar la inversión del significado de los bits, el cambio del orden de los bits y transformaciones simples similares para números de cuatro bits, y más de 200.000 para números de 5 bits), pero hay una que es "el" código Gray, y esto es sencillo de implementar si se dispone de XOR a nivel de bits y desplazamientos de bits en el lenguaje de su elección: gray = x ^ (x >> 1) convertirá un número positivo en el número del código Gray en ese índice.

Answer 2

Lo que pides es equivalente a encontrar un camino hamiltoniano en un hipercubo, ya que puedes equiparar la cadena $000100$ por ejemplo, con el punto $(0,0,0,1,0,0)\in\mathbb R^6$ y las cadenas vecinas son exactamente las que comparten un lado del $6$ -hipercubo dimensional.

El camino hamiltoniano en un hipercubo existe, así que tu bucle también existe. Véase Wikipedia al respecto.