格雷码算法（32 位或更少）

Question

我最近遇到了格雷码，我一直在试图围绕用于将格雷码转换回二进制（32 位或更少）的高效算法进行思考。

num = num ^ (num >> 16);
num = num ^ (num >> 8);
num = num ^ (num >> 4);
num = num ^ (num >> 2);
num = num ^ (num >> 1);

这是我正在谈论的代码。现在这是我的问题：

• 这与普通代码（右移 1 和 XOR 直到mask == 0）有什么区别？
• 为什么要专门使用 16、8、4、2、1，而不是任何其他小于 32 位的数字？

• 如果我们反过来做，有什么区别：

  num = num ^ (num >> 1);
  num = num ^ (num >> 2);
  num = num ^ (num >> 4);
  num = num ^ (num >> 8);
  num = num ^ (num >> 16);
  

  我已经试过了，它似乎产生了相同的结果。

Answer 1

例如，以位为单位（让我们以 8 为单位）

h g^h f^g e^f d^e c^d b^c a^b

那么如果我们申请会发生什么x ^= x >> 1？我们得到这个

h g f^h e^g d^f c^e b^d a^c

这看起来就像我们刚开始的时候一样，好像它是由x ^ (x >> 2)而不是 制作的x ^ (x >> 1)，所以同样的想法只用 2 的移位来反转：

h g f e d^h c^g b^f a^e

看起来不错，现在很明显为什么x ^= x >> 4会完全恢复正常。对于更多位，相同的模式只会持续一段时间。

看这个的其他方式，暂时反转比特，把“以灰色”到x ? 3与?在GF（2为乘法^ķ），乘以奇数是在GF（2可逆^ķ）和3乘法逆是“所有位设置”，您可以找到如下：

• 开始于y=3和一个临时的逆i=1
• y通过与 3 异或来杀死（不是 lsb）中的第一个位，在逆中设置相应的位
• 循环直到 y=1

因此，第一个步骤是y=3, i=1，y=5, i=3，y=9, i=7等，直到你将所有的位i，让呼叫最后i inv。

然后我们有 (x ? 3) ? inv = x ? (3 ? inv) = x ? 1 = x

乘以“所有位设置”意味着每一位最终都是它自己和所有低位的异或，你可以用

x ^= x << 1
x ^= x << 2
x ^= x << 4
...

首先所有位与它们旁边的位进行异或，然后是接下来的两个位（它们已经被异或在一起，所以这只需要一个步骤），然后是接下来的四位等。

再次反转位以获得您开始的内容。

但现在有趣的东西。

为什么顺序无关紧要？

（是的，实际上你不仅可以颠倒步骤，还可以任意洗牌）

好的，反转位并返回 GF(2 ^k )。写每一行的另一种方法是

x = x ? 3
x = x ? 5
x = x ? 17
...

最终的结果当然是 ((x ? 3) ? 5) ? 17 = x ? (3 ? 5 ? 17) = x ? 127

GF(2 ^k ) 中的乘法非常好且可交换，因此它可以按任何顺序完成。

其他号码呢

当然，只要他们的产品是inv. 但是所有其他选择都会导致出现烦人/许多被乘数。例如，也许我们希望 9 是一个因子，那么剩下的就是 199，它可以分解为 9 ？63，等等，但这会持续一段时间，直到你可能有 3、5、9、9、17、65，这太糟糕了（请注意，如果有 8 位，无论如何 9 ? 9 ? 65 = 1是的，把它踢出去，回到原来的 3、5、17）。不过有可能。