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 的模式。此外，当您将数字右移时，xors 也会右移:(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 位代码，我们可以使用异或恢复第 n-1 位。

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

从最大位开始(它与 0 异或)因此我们可以恢复整数。