c - 生成反向位查找表(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 序列。您应该问自己“为什么？”。这是构建所需的构建基 block 。二进制中的数字 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 个条目)，您将发现第 3 个 2 位具有 00 10 01 11 序列，如果您对表进行排序16 列和最后 2 位，当您按 64 列排序时。

现在我隐含地告诉你原始宏扩展中的数字 16 和 64 是从哪里来的。

这就是细节，概括地说:递归的最高层生成最低有效的 2 位，中间两层执行它们的操作，最低层生成最高有效的 2 位。