第n个灰色code [英] the nth gray code

问题描述

的计算公式第n个灰色code是：

the formula for calculating nth gray code is :

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

我的连接codeD它：

I encoded it as:

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

有人可以解释上述公式工作，或可能的deriviation？

Can someone explain how the above formula works, or possibly its deriviation?

推荐答案

如果你看一下二进制计数序列，你注意，相邻codeS在几个最后两位不同（无孔），所以如果你异或他们，几尾1的模式出现。此外，当您移动号码的权利，异或也随之向右移位：（A XOR B）>> N ==一个>> N XOR B >> N

If you look at binary counting sequence, you note, that neighboring codes differ at several last bits (with no holes), so if you xor them, pattern of several trailing 1's appear. Also, when you shift numbers right, xors also will be shifted right: (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位设置。因此，

Original Xor results and shifted results differ in single bit (i marked them by dot above). This means that if you xor them, you'll get pattern with 1 bit set. So,

(A xor B) xor (A>>1 xor B>>1) == (A xor A>>1) xor (B xor B>>1) == gray (A) xor gray (B)

由于XOR给我们1S在不同的位，它证明，什么邻国codeS的区别仅在于单个位，这是灰色code主要性能，我们希望得到的。

As xor gives us 1s in differing bits, it proves, what neighbouring codes differ only in single bit, and that's main property of Gray code we want to get.

所以为了完整性，必须对子级证明，即n可以根据其N ^（N >> 1）值恢复：得知code第n个位，我们可以第n-1使用XOR位恢复。

So for completeness, whould be proven, that N can be restored from its N ^ (N>>1) value: knowing n'th bit of code we can restore n-1'th bit using xor.

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

这是最大的位（其异或0），因此，我们可以恢复的整数。启动

Starting from largest bit (it is xored with 0) thus we can restore whole number.

这篇关于第n个灰色code的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！