algorytm za generowaniem tabeli wyszukiwania bitów wstecznych (8 bitów)

Question

Znalazłem tabelę odnośników here. Tabela jest generowana jako tabela bitów odwrotnych z 8 bitów.

Nie mogę zrozumieć, dlaczego to działa. Proszę wyjaśnić tę teorię. Dzięki

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

pierwsze komentarz: Tego rodzaju rzeczy jest zazwyczaj tylko zrobić w IOCCC. Kod taki jak ten nie powinien być używany w środowiskach produkcyjnych, ponieważ jest to nieoczywisty. Powodem, dla którego wspominam o tym, jest usunięcie fałszywego wrażenia, że ​​ma to jakąkolwiek korzyść z wydajności lub przestrzeni, skompilowany kod będzie zawierał ten sam (numer) bajtów, które uzyskałbyś, pisząc 256 liczb bezpośrednio do tablicy.

Ok, teraz jak to działa. Działa oczywiście rekurencyjnie, definiując dwa bity na najwyższym poziomie R6, a następnie dwa kolejne na następnym ... Ale jak szczegółowo? Ok:

Pierwszą wskazówką, którą otrzymasz, jest interesująca sekwencja 0-> 2-> 1-> 3. Powinieneś zadać sobie pytanie "dlaczego?". Jest to element konstrukcyjny wymagany do budowy. Liczby 0 1 2 3 w postaci binarnej to 00 01 10 11, a jeśli odwrócisz każdą z nich: 00 10 01 11, która wynosi 0 2 1 3!

Teraz pozwala spojrzeć na to, co chcemy tabelę zrobić: Powinno się coś takiego:

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

bo chcesz go map indeksu 0 do 0, indeks 00000001 do 10000000 i tak dalej .

Należy zauważyć, że najważniejsze (po lewej) 2 bity każdej liczby: 00 10 01 11 dla każdej linii!

Teraz zauważ, że drugie najważniejsze 2 bity każdej liczby rosną w ten sam sposób (00 10 01 11), ale w przypadku "kolumn".

Powodem, dla którego zdecydowałem się zamówić tablicę w rzędach o długości 4 jest to, że dowiedzieliśmy się, że 2 bity są zapisywane na raz, a 2 bity mogą tworzyć 4 wzory.

Jeśli nadal będziesz obserwować pozostałe numery w tabeli (łącznie 256 wpisów), zobaczysz, że można znaleźć 3 bity o sekwencji 00 10 01 11, jeśli uporządkujesz tabelę w kolumnach 16 i 2 ostatnich bitów, gdy zamawiasz go w kolumnach 64.

Teraz domyślnie powiedziałem ci, skąd wzięły się liczby 16 i 64 w oryginalnym makro-ekspansji.

To są szczegóły i uogólnienie: najwyższy poziom rekursji generuje najmniej znaczące 2 bity, dwa środkowe poziomy robią swoje, a najniższy poziom generuje najbardziej znaczące 2 bity.