生成反向位查找表(8位)背后的算法

Question

我在这里找到了查找表.该表生成为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个条目),您将看到00 10 01 11如果您按16列中的顺序排序表,则可以找到具有序列的第3个2位,当您在列中进行排序时,可以看到最后2位64.

现在我隐含地告诉你原始宏观扩张中的数字16和64来自何处.

这是细节,并概括:递归的最高级别生成最低有效2位,中间两级执行它们的操作,最低级别生成最高有效2位.