Algorithmus hinter der Erzeugung der umgekehrten Bits Nachschlagtabelle (8 Bit)

Question

fand ich die Nachschlagetabelle here. die Tabelle als Umkehr Bits Tabelle von 8 Bits erzeugt wird.

Ich kann nicht herausfinden, warum es funktioniert. Bitte erläutern Sie die Theorie dahinter. Dank

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

Zunächst einmal ein Kommentar: Diese Art der Sache ist in der Regel nur in den IOCCC getan. Code wie dieser sollte nicht in Produktionsumgebungen verwendet werden, da er nicht offensichtlich ist. Der Grund, warum ich dies erwähne, ist, den falschen Eindruck zu beseitigen, dass dies irgendeinen Leistungs- oder Platznutzen hat, der kompilierte Code wird die gleiche (Anzahl von) Bytes enthalten, wenn man 256 Nummern direkt in das Array schreibt.

Ok, jetzt, wie es funktioniert. Es arbeitet natürlich rekursiv, definiert zwei Bits auf einer obersten Ebene R6, dann zwei weitere auf der nächsten ... Aber wie im Detail? Ok:

Der erste Hinweis, den Sie erhalten, ist die interessante 0-> 2-> 1-> 3-Sequenz. Sie sollten sich fragen "warum?". Dies ist der Baustein, der für den Bau benötigt wird. Die Zahlen 0 1 2 3 in binär sind 00 01 10 11 und wenn Sie jeweils umgekehrt: 00 10 01 11, die 0 2 1 3 ist!

Jetzt können Sie einen Blick darauf werfen, was wir auf den Tisch zu tun: Es ist etwas wie dieses werden sollte:

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

, weil Sie es wollen Index abzubilden 0 bis 0, Index 00.000.001-10.000.000 und so weiter .

Beachten Sie, dass die höchstwertigen (ganz links) 2 Bits jeder Nummer: 00 10 01 11 für jede Zeile!

bemerken, dass nun das zweithöchstwertige 2 Bits jeder Zahl, die die gleiche Art und Weise erhöhen, (00 10 01 11), aber für die „Spalten“.

Der Grund, warum ich wählte das Array in Reihen der Länge 4 ist, um zu bestellen, dass wir herausgefunden, dass 2 Bits zu einem Zeitpunkt, und 2 Bits 4 Muster kann geschrieben werden, erstellen.

Wenn Sie dann fortfahren, die restlichen Nummern der Tabelle (256 Einträge insgesamt) zu beobachten, sehen Sie, dass die 3. 2 Bits die 00 10 01 11 Sequenz haben, wenn Sie die Tabelle in Spalten von 16 und die letzten 2 Bits wenn bestellen Sie bestellen sie in Spalten von 64.

nun implizit Sie mir gesagt, wo die Zahlen 16 und 64 in der ursprünglichen Makro-Expansion kam.

Das sind die Details, und zu verallgemeinern: Die höchste Ebene der Rekursion erzeugt die niedrigstwertigen 2 Bits, die mittleren zwei Ebenen tun ihr Ding und die niedrigste Ebene erzeugt die höchstwertigen 2 Bits.