第n个格雷码

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

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

我把它编码为：

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

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

已邀请:

4 个回复

艾食魄轻县

如果你看一下二进制计数序列，你会注意到，相邻的代码在最后几位（没有空洞）有所不同，所以如果你对它们进行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），因此我们可以恢复整数。

渴翅吮斡撤

通过归纳证明。提示：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。

场竟矩喘崩

您参考的维基百科条目以非常迂回的方式解释了等式。但是，从这开始是有帮助的：因此编码是稳定的感觉一旦二进制数出现在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))。

吞睫素

增加一个数字，当你按位时，将所有尾随的数字翻转为零，将最后的零翻转为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）足以获得格雷码。

要回复问题请先登录或注册

第n个格雷码

4 个回复

发起人

gray_code

问题状态

第n个格雷码

与内容相关的链接

4 个回复

发起人

gray_code

问题状态