グレイコード

1ビットだけ変える方法は幾通りかあるが、グレイコードでは法則性が持たされており、通常の2進数からの直接変換も可能である。

n桁のグレイコードの生成手順は、「0 (n−1)桁までのグレイコードの並び(昇順)」を続けて、そのあとに「1 (n−1)桁までのグレイコードの並び(降順)」を続けたものである。

通常の2進数からグレイコードに直接変換するには、「変換元の2進数」と、「変換元の2進数を1ビット右シフトしたもの」で排他的論理和(XOR)を取る。C/C++であれば、「gc = num ^ (num >> 1);」で得ることができる。

1桁の場合、0(0)→1(1)、よって0:0、1:1 である。

2桁の場合、左の桁の0や1が今回付け足されたものである。残りの桁が上下の列で全く同じ(ただし逆順にたどる)ことに注目。

0 0(0) → 0 1(1)
           ↓
1 0(3) ← 1 1(2)

従って、0:00、1:01、2:11、3:10 である。

0 00(0) → 0 01(1) → 0 11(2) → 0 10(3)
                                  ↓
1 00(7) ← 1 01(6) ← 1 11(5) ← 1 10(4)

よって、0:000、1:001、2:011、3:010、4:110、5:111、6:101、7:100 である。

 (0)    (1)    (2)    (3)    (4)    (5)    (6)    (7)
0 000→0 001→0 011→0 010→0 110→0 111→0 101→0 100
                                                   ↓
1 000→1 001→1 011→1 010→1 110→1 111→1 101→1 100
 (f)    (e)    (d)    (c)    (b)    (a)    (9)    (8)

よって、0:0000、1:0001、2:0011、3:0010、4:0110、5:0111、6:0101、7:0100、8:1100、9:1101、a:1111、b:1110、c:1010、d:1011、e:1001、f:1000 である。