dietro la generazione della tabella di ricerca dei bit di inversione (8 bit)

Question

Ho trovato la tabella di ricerca here. La tabella è generata come una tabella di bit inversa di 8 bit.

Non riesco a capire perché funzioni. Si prega di spiegare la teoria dietro di esso. Grazie

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

Answer 1

Prima di tutto un commento: Questo genere di cose avviene normalmente solo nel IOCCC. Codice come questo non dovrebbe essere usato in ambienti di produzione perché è non ovvio. Il motivo per cui menziono questo è quello di rimuovere la falsa impressione che questo abbia un vantaggio in termini di prestazioni o spazio, il codice compilato conterrà lo stesso numero di byte che otterresti scrivendo i 256 numeri direttamente nell'array.

Ok, ora come funziona. Ovviamente funziona in modo ricorsivo, definendo due bit ad un livello superiore R6, quindi altri due al prossimo ... Ma come in dettaglio? Ok:

Il primo indizio che ottieni è l'interessante sequenza 0-> 2-> 1-> 3. Dovresti chiederti "why?". Questo è il blocco predefinito necessario per la costruzione. I numeri 0 1 2 3 in binario sono 00 01 10 11 e se si annulla ciascuno: 00 10 01 11 che è 0 2 1 3!

Ora ti permette di dare un'occhiata a quello che vogliamo il tavolo per fare: Dovrebbe diventare qualcosa di simile:

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

perché si vuole che la mappa Indice 0 a 0, l'indice 00.000.001-10.000.000 e così via .

Si noti che il più significativo (a sinistra) 2 bit di ogni numero: 00 10 01 11 per ogni riga!

Ora notare che i secondi 2 bit più significativi di ciascun numero aumentano allo stesso modo (00 10 01 11) ma per le "colonne".

Il motivo per cui ho scelto di ordinare l'array in righe di lunghezza 4 è che abbiamo scoperto che 2 bit sono scritti alla volta e 2 bit possono creare 4 pattern.

Se si continua a osservare i restanti numeri della tabella (256 voci totali), si vedrà che il 3 ° 2 bit può essere trovato con la sequenza 00 10 01 11 se si ordina la tabella in colonne di 16 e gli ultimi 2 bit quando lo ordinate in colonne di 64.

Ora ho implicitamente detto da dove provenivano i numeri 16 e 64 della macro-espansione originale.

Questi sono i dettagli e per generalizzare: il livello più alto della ricorsione genera i 2 bit meno significativi, i due livelli centrali fanno la loro cosa e il livello più basso genera i 2 bit più significativi.