第n个格雷码

Question

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

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

我对它进行了编码：

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

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

- sud03r

---

我想知道这里是否真的需要 n--。当从0开始计算代码时，n ^ (n>>1) 是完整的。 - Vovanium

是的，代码从1开始计数，否则公式中的（n-1）将变成n。在我看来，“第一格雷码”比“零号格雷码”更有意义。 - sud03r

Answer 1

如果你观察二进制计数序列，你会发现相邻的代码在最后几位上有所不同（没有空缺），因此如果你对它们进行异或运算，就会出现几个末尾为1的模式。另外，当你向右移动数字时，异或运算也会向右移动：(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)

作为异或运算可以在不同位上给我们带来1，它证明了相邻的代码只有一个位不同，这是我们想要获得的格雷码的主要属性。

因此，为了完整起见，需要证明N可以从其N ^（N >> 1）值中恢复：知道代码的第n位，我们可以使用异或运算恢复第n-1位。

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

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

- Vovanium

Answer 2

你所提到的维基百科条目非常迂回地解释了该方程。

然而，从这里开始会有所帮助：

因此编码是稳定的，也就是说，一旦二进制数出现在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)。现在，我们知道如果 m 大于 2^n-1，那么 Gn(m) & 2^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)) 作为基于零的格雷码。

- MSN

Answer 3

使用归纳法证明。

提示：第1<<k个到(1<<(k+1))-1个值是前1<<(k-1)个到(1<<k)-1个值的两倍，加上零或一。

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

gray(2*n) 和 gray(2*n+1) 是以某种顺序的2*gray(n) 和 2*gray(n)+1。

- aschepler

Answer 4

当你以二进制方式查看一个数字并将其递增时，它会将所有末尾的1翻转为0，并将最后一个0翻转为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 中的最高位）就足以获得格雷码。

- Rafał Dowgird