第n个灰色代码

如果你看二进制计数序列,你会注意到,相邻的代码在最后几位不同(没有空穴),所以如果你异或它们,几个尾随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>gt;1)值恢复:知道第N位代码,我们可以使用xor恢复第N位代码。

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

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

通过归纳证明。

1<<k 到 (1<<(k+1))-1 1<<(k-1) 到 (1<<k)-1 th值,加上0或1。

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

Wikipedia entry 你指的是用一种非常迂回的方式解释这个方程。

不过,这有助于从以下方面入手:

感觉到一个二进制数 在所有长列表中的位置;因此 反射灰码值 数量:G(m)=第m次反射

换句话说, Gn(m) & 2^n-1 不是 Gn-1(m & 2^n-1) ~Gn-1(m & 2^n-1) . 例如, G(3) & 1 不是 G(1) 或 ~G(1) . 现在,我们知道了 Gn(m)和2^n-1 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翻转为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 10..0 到 11..0 (即翻转尾随0中的最高0)就足以得到一个灰色代码。