algorithm - 格雷码算法(32位或更少)

Question

我最近遇到了格雷码，并且我一直在努力尝试将我的头脑用于将格雷码转换回二进制(32 位或更少)的有效算法。

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

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

• 这和普通代码(右移 1 并异或直到 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^k) 中的乘法，奇数乘法在 GF(2^k) 中是可逆的，3 的乘法逆元是“所有位集”，您可以可以找到如下:

• 以 y=3 开头和临时逆i=1
• 杀死y中的第一位(不是 lsb)通过将其与 3 进行异或，设置相反的相应位
• 循环直到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)。不过有可能。