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

我最近遇到了灰色代码，我一直在努力把我的头围绕着有效的算法，用来将灰色代码转换回二进制（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);

我试过了，结果似乎是一样的。

最佳答案

例如，以位为单位（取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（2k）中是乘法的，奇数乘法在gf（2k）中是可逆的，3的乘法逆是“所有位集”，如下所示：
从y=3和临时逆i=1开始
将y中的第一个位（不是lsb）与3进行异或运算，然后将相应的位设置为相反
循环直到y=1
所以第一步是y=3, i=1，y=5, i=3，y=9, i=7等，直到您设置了i中的所有位，让我们调用这个finaliinv。
然后我们有(x ⊗ 3) ⊗ inv = x ⊗ (3 ⊗ inv) = x ⊗ 1 = x
乘以“所有位集”意味着每一位最终都是其自身和所有较低位的异或，您可以使用它

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

首先，所有的位都是由它们旁边的位进行异或运算，然后由接下来的两个位（它们已经被异或运算在一起，所以这只需要一步）进行异或运算，然后由接下来的四个位进行异或运算。
再倒过来看看你是怎么开始的。
但现在有趣的事情。
为什么订单不重要？
（是的，事实上你不仅可以反转这些步骤，还可以任意洗牌）
好的，反转这些位，回到gf（2k）。另一种写每一行的方法是

x = x ⊗ 3
x = x ⊗ 5
x = x ⊗ 17
...

最终结果当然是((x ⊗ 3) ⊗ 5) ⊗ 17 = x ⊗ (3 ⊗ 5 ⊗ 17) = x ⊗ 127
gf（2k）中的乘法是很好的和可交换的，所以它可以很好地以任何顺序完成。
其他数字呢
当然，只要他们的产品是inv但是所有其他的选择都会导致烦人的/许多被乘数出现。例如，也许我们希望9是一个因子，那么剩下的是199，它可以分解成9⊗63，依此类推，但这会持续一段时间，直到你有了3，5，9，9，17，65，这很糟糕（注意，9⊗9⊗65=1，不管怎样，如果有8位，那么是的，把它踢出来，回到原来的3，5，17）不过，有可能。

关于algorithm - 格雷码算法(32位或更少)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37047941/