algorithm - 第n个格雷码

计算第n个灰色代码的公式为：

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

我把它编码成：

int gray(int n)
{
  n--;
  return n ^ (n >> 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)

当异或在不同的位上给我们1时，它证明了相邻的码只在一个位上不同，这是我们想要得到的灰色码的主要性质。
所以为了完整性，我们可以证明，n可以从它的n^（n>>1）值恢复：知道第n位代码，我们可以使用xor恢复第n位。

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

从最大位开始（与0进行异或），这样我们就可以恢复整数。