算法後面生成反向位查找表（8位）

Question

我找到了查找表here.該表生成爲8位的反向位表。

我想不通它爲什麼起作用。請解釋它背後的理論。由於

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

首先評論：這種事情通常只在IOCCC完成。這樣的代碼不應該在生產環境中使用，因爲它是非顯而易見的。我之所以提到這一點，是爲了消除這樣的錯誤印象，即它具有任何性能或空間優勢，編譯後的代碼將包含如果將256個數字直接寫入數組，則會得到相同（數字）的字節。

好的，現在到它是如何工作的。它當然遞歸地工作，在頂層R6上定義兩個位，然後在另一個位上定義兩個位...但詳細情況如何？好的：

你得到的第一條線索是有趣的0-> 2-> 1-> 3序列。你應該問自己「爲什麼？」。這是施工所需的構件。二進制中的數字0 1 2 3是00 01 10 11，並且如果您反轉了每個：00 10 01 11即0 2 1 3！

現在讓我們來看看我們想要的表做：它應該成爲這樣的：

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

，因爲你希望它索引0映射到0，指數00000001〜10000000等。

請注意，每個數字中最重要的（最左邊的）2位：00 10 01 11！

現在注意到每個數字的第二個最重要的2位以相同的方式增加（00 10 01 11），但是對於「列」。

我選擇在長度爲4的行中排列數組的原因是，我們發現一次寫入2位，2位可以創建4個模式。

如果您繼續觀察表中剩餘的數字（總共256個條目），您將看到如果您按16位列排序表，並且在排列最後2位時發現第3個2位具有00 10 01 11序列你在64列中訂購它。

現在我含蓄地告訴你原始宏擴展中的數字16和64來自哪裏。

這是細節，並概括：遞歸的最高級別生成最低有效2位，中間兩級完成它們的事情，最低級別生成最重要的2位。