反向位查询表生成的算法（8位） [英] algorithm behind the generation of the reverse bits lookup table(8 bit)

问题描述

我在此处找到了查找表。该表生成为反向位表的8位。

I found the lookup table here. The table is generated as a reverse bits table of 8 bits.

我不知道它为什么起作用。请解释其背后的理论。谢谢

I can not figure out why it works. Please explain the theory behind it. Thanks

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)
};

推荐答案

首先发表评论：这种事情通常是仅在 IOCCC 中完成。此类代码不应在生产环境中使用，因为它不明显。我之所以提及这一点，是为了消除错误的印象，即它对性能或空间都有好处，编译后的代码将包含与直接将256个数字直接写入数组时所获得的字节数相同的字节数。

First off a comment: This kind of thing is normally only done in the IOCCC. Code like this should not be used in production-environments because it is non-obvious. The reason why i mention this is to remove the false impression that this has any performance- or space benefit, the compiled code will contain the same (number of) bytes you would get if writing the 256 numbers directly into the array.

好的，现在看看它是如何工作的。当然，它是递归工作的，在顶级R6上定义两个位，然后在下一个R2上定义两个位……但是如何详细？好的：

Ok, now to how it works. It works recursively of course, defining two bits at a top level R6, then two more at the next... But how in detail? Ok:

您得到的第一个线索是有趣的0-> 2-> 1-> 3序列。您应该问自己 为什么？。这是构造所需的构造块。二进制数字0 1 2 3是 00 01 10 11 ，如果将每个数字都反转： 00 10 01 11 其中是0 2 1 3！

The first clue you get is the interesting 0->2->1->3 sequence. You should ask yourself "why?". This is the building block that is required for the construction. The numbers 0 1 2 3 in binary are 00 01 10 11 and if you reverse each: 00 10 01 11 which is 0 2 1 3!

现在让我们看一下我们希望表格执行的操作：它应该变成这样：

Now lets take a look at what we want the table to do: It should become something like this:

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

因为您希望它将索引0映射到0，将索引00000001映射到10000000，依此类推。

because you want it to map index 0 to 0, index 00000001 to 10000000 and so on.

请注意，每个数字的最高有效（最左边）2位：每行 00 10 01 11 ！

Notice that the most significant (leftmost) 2 bits of each number: 00 10 01 11 for every line!

现在注意，每个数字的第二个最高有效2位以相同的方式（00 10 01 11）增加，但对于列增加。

Now notice that the second most significant 2 bits of each number increase the same way (00 10 01 11) but for the "columns".

我选择在长度为4的行中对数组进行排序的原因是，我们发现一次写入2位，而2位可以创建4种模式

The reason why i chose to order the array in rows of length 4 is, that we found out that 2 bits are written at a time and 2 bits can create 4 patterns.

如果您继续观察表格的剩余数字（总共256个条目），您会发现第3个2位具有 00 10 01 11 序列，如果您在16列中对表进行排序，而在64列中对表进行排序时的最后2位。

If you then continue observing the remaining numbers of the table (256 entries total) you will see that the 3rd 2 bits can be found having the 00 10 01 11 sequence if you order the table in columns of 16 and the last 2 bits when you order it in columns of 64.

现在，我隐式告诉您原始宏扩展中的数字16和64的来源。

Now i implicitly told you where the numbers 16 and 64 in the original macro-expansion came from.

这就是细节，并概括如下：递归的最高级别生成最低有效2位，中间的两个级别执行其操作，最低的级别生成该位最高2位。

That are the details, and to generalize: The highest level of the recursion generates the least significant 2 bits, the middle two levels do their thing and the lowest level generates the most significant 2 bits.

这篇关于反向位查询表生成的算法（8位）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！