algorithm - 第n个格雷码

Question

第n个格雷码的计算公式为：

(n-1) XOR (floor((n-1)/2))  
(Source: wikipedia)

我将其编码为：

int gray(int n)
{
  n--;
  return n ^ (n >> 1);
}

有人可以解释上述公式是如何工作的，或者可能是它的推导吗？

Answer 1

如果您查看二进制计数序列，您会注意到，相邻代码在最后几个位（没有孔）处不同，因此如果您对它们进行异或，则会出现几个尾随 1 的模式。此外，当您将数字右移时，xor 也会右移：(A xor B)>>N == A>>N xor B>>N。

    N                    N>>1                  gray
 0000           .        0000           .      0000           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0001          .         0000          .       0001          .
   || >xor = 0011           | >xor = 0001           >xor = 0010
 0010           .        0001           .      0011           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0011         .          0001         .        0010         .
  ||| >xor = 0111          || >xor = 0011           >xor = 0100
 0100                    0010                  0110

原始异或结果和移位结果在单个位上有所不同（我在上面用点标记了它们）。这意味着如果您对它们进行异或，您将获得设置为 1 位的模式。所以，

(A xor B) xor (A>>1 xor B>>1) == (A xor A>>1) xor (B xor B>>1) == gray (A) xor gray (B)

由于 xor 在不同的位上给了我们 1，它证明了哪些相邻代码仅在一个位上不同，这是我们想要获得的格雷码的主要属性。

因此，为了完整性，可以证明，N 可以从其 N ^ (N>>1) 值恢复：知道第 n 位代码，我们可以使用 xor 恢复第 n-1 位。

A_[bit n-1] = A_[bit n] xor gray(A)_[bit n-1]

从最大位开始（与 0 异或），因此我们可以恢复整数。

Answer 2

用归纳法证明。

提示：1<<kth 到th 值是th到(1<<(k+1))-1th 值的两倍，再加上零或一。1<<(k-1)(1<<k)-1

编辑：那太令人困惑了。我真正的意思是，

gray(2*n)并且gray(2*n+1)是2*gray(n)并且2*gray(n)+1以某种顺序。

Answer 3

您引用的维基百科条目以非常迂回的方式解释了这个等式。

但是，从这个开始会有所帮助：

因此，编码是稳定的，因为一旦二进制数出现在 Gn 中，它就会出现在所有较长的列表中的相同位置；所以讨论一个数字的反射格雷码值是有道理的：G(m) = 第 m 个反射格雷码，从 0 开始计数。

换句话说，Gn(m) & 2^n-1要么是Gn-1(m & 2^n-1)要么~Gn-1(m & 2^n-1)。例如，G(3) & 1要么是G(1)要么~G(1)。现在，我们知道如果大于，那Gn(m) & 2^n-1将是反射（按位反转）。m2^n-1

换句话说：

G(m, bits), k= 2^(bits - 1)
G(m, bits)= m>=k ? (k | ~G(m & (k - 1), bits - 1)) : G(m, bits - 1)
G(m, 1) = m

完整地计算数学，你得到(m ^ (m >> 1))从零开始的格雷码。

Answer 4

递增一个数字，当您按位查看它时，会将所有尾随的 1 翻转为零，最后一个零翻转为 1。这是翻转了很多位，格雷码的目的是使其完全一致。这种转换使两个数字（在增量之前和之后）在所有被翻转的位上都相等，除了最高位。

前：

011...11
     + 1 
---------
100...00

后：

010...00
     + 1
---------
110...00
^<--------This is the only bit that differs 
          (might be flipped in both numbers by carry over from higher position)

n ^ (n >> 1)更容易计算，但似乎只需将尾随更改011..1为010..0（即，将除最高 1 之外的 1 的整个尾随块归零）和10..0更改为11..0（即翻转尾随 0 中的最高 0）就足以获得格雷码。