algoritmo detrás de la generación de la tabla de búsqueda de bits inversos (8 bits)

Encontré la tabla de búsqueda aquí. La tabla se genera como una tabla de bits inversa de 8 bits.

No puedo entender por qué funciona. Por favor explique la teoría detrás de esto. Gracias

static const unsigned char BitReverseTable256[256] = { # define R2(n) n, n + 2*64, n + 1*64, n + 3*64 # define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) # define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 ) R6(0), R6(2), R6(1), R6(3) }; 

Primero, un comentario: este tipo de cosas normalmente solo se hace en el IOCCC . El código como este no debe usarse en entornos de producción porque no es obvio . La razón por la que menciono esto es para eliminar la falsa impresión de que esto tiene algún beneficio de rendimiento o espacio, el código comstackdo contendrá el mismo (número de) bytes que obtendría si escribiera los 256 números directamente en la matriz.

Ok, ahora a cómo funciona. Funciona recursivamente, por supuesto, definiendo dos bits en un nivel superior R6, luego dos más en el siguiente … ¿Pero en detalle? De acuerdo:

La primera pista que obtienes es la interesante secuencia 0-> 2-> 1-> 3. Deberías preguntarte ” ¿por qué? “. Este es el bloque de construcción que se requiere para la construcción. Los números 0 1 2 3 en binario son 00 01 10 11 y si invierte cada uno: 00 10 01 11 que es 0 2 1 3!

Ahora echemos un vistazo a lo que queremos que haga la tabla: debería convertirse en algo como esto:

 00000000 10000000 01000000 11000000 00100000 10100000 01100000 11100000 00010000 10010000 01010000 11010000 00110000 10110000 01110000 11110000 ... 

porque desea que asigne el índice 0 a 0, el índice 00000001 a 10000000 y así sucesivamente.

Observe que los 2 bits más significativos (más a la izquierda) de cada número: 00 10 01 11 para cada línea.

Ahora note que los segundos 2 bits más significativos de cada número aumentan de la misma manera (00 10 01 11) pero para las “columnas”.

La razón por la que elegí ordenar la matriz en filas de longitud 4 es que descubrimos que 2 bits se escriben a la vez y que 2 bits pueden crear 4 patrones.

Si continúa observando los números restantes de la tabla (256 entradas en total), verá que se pueden encontrar los 3er 2 bits con la secuencia 00 10 01 11 si ordena la tabla en columnas de 16 y los últimos 2 bits cuando Pídelo en columnas de 64.

Ahora le dije implícitamente de dónde venían los números 16 y 64 en la macroexpansión original.

Estos son los detalles, y para generalizar: el nivel más alto de la recursión genera los 2 bits menos significativos, los dos niveles intermedios hacen lo suyo y el nivel más bajo genera los 2 bits más significativos.