第n个格雷码

Question

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

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

我把它编码为:

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

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

Answer 1

如果你看一下二进制计数序列,你会注意到,相邻的代码在最后几位(没有空洞)有所不同,所以如果你对它们进行xor,则会出现几个尾随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

原始Xor结果和移位结果在单个位中有所不同(我用上面的点标记它们).这意味着如果你对它们进行xor,你将获得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进行xored),因此我们可以恢复整数.