algorithm - 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 のパターンが表示されます。また、数値を右にシフトすると、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

元の Xor 結果とシフトされた結果は 1 ビット異なります (上のドットでマークされています)。これは、それらを 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 を与えるので、どの隣接コードが 1 ビットだけ異なるかを証明し、それが取得したいグレイ コードの主な特性です。

したがって、完全を期すために、N はその N ^ (N>>1) 値から復元できることが証明される必要があります。コードの n 番目のビットを知っていると、xor を使用して n-1 番目のビットを復元できます。

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

最大ビット (0 と xor されている) から開始すると、整数を復元できます。

Answer 2

あなたが参照するウィキペディアのエントリは、方程式を非常に遠回りに説明しています。

ただし、次のことから始めると役立ちます。

したがって、2 進数が Gn に表示されると、それはすべての長いリストの同じ位置に表示されるという意味で、コーディングは安定しています。したがって、数値の反射グレー コード値について話すのは理にかなっています。G(m) = 0 から数えて 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場合、 が反映された (ビット単位の逆数) になることがわかります。m2^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))と、ゼロベースのグレイ コードが得られます。

Answer 3

帰納法で証明します。

ヒント: 1<<kth からth の値は、 th からth の値(1<<(k+1))-1の 2 倍に0 または 1 を加えたものです。1<<(k-1)(1<<k)-1

編集：それはあまりにも混乱しました。私が本当に言いたいのは、

gray(2*n)とgray(2*n+1)は2*gray(n)、2*gray(n)+1ある順序で。

Answer 4

数値をインクリメントすると、ビット単位で見ると、後続のすべての 1 がゼロに反転し、最後の 0 が 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 を反転する) だけで十分なようです。