グレイコードって何ですか

先日, id:nowokay さんの 1ビットずつ変えていって全部の数を列挙するグレイコードの生成 - きしだのはてな という記事 (Jun 10, 2012) が目にとまりました. そもそも, グレイコードというものを, いままで知りませんでした. Wikipedia 日本語版の グレイコード の記事 (as of Oct 11, 2011) などによると, 一般的なアプリケーションソフトウェアよりもむしろハードウェア寄りの分野で応用されることのほうが多いようです. わたしは IT 分野にキャリアチェンジしてからはもっぱらインフラ方面 (OSI 階層モデルでいえばレイヤ 1 から 4 まで) の経験が中心でしたので, そのくせグレイコードのことも知らなかったとあって, ちょっと悔しい気がしてきました.

それで, ここ数日ほど, 少し調べたり考えたりしてみたのですが, ちょっとやそっとではよくわからないことだらけで, 自分にはやはり数学 (特に計算機科学?) のセンスがないのだろうかと落ち込んでいるところです. そのため, ここに何かを書くほどのネタもほとんどないのですが, あとで自分が何かを思い出すときのきっかけにでもなればいいかなと思い, 何かを書きたいと思います.

たとえば 11 という整数を 4 ビット二進法 (符号なし) で表記すると 1011 となります. これをグレイコードで表記すると 1110 となります. 0 から 15 までの各整数について並べてみると, 次のようになります.

十進法	通常の二進法	グレイコード
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

通常の二進法の表記からグレイコードの表記に変換する方法については, いくつかあるようですが, 前掲のブログ記事にも書かれている方法が最も覚えやすいと感じました. すなわち, ある整数 n においては, n を 1 ビットだけ右シフトしたものと n との排他的論理和 (XOR) を計算し, それを二進法で表記すれば, n のグレイコードになります.

たとえば, 11 (二進法では 1011) を 1 ビットだけ右シフトしたものは 5 (同 0101) になりますから, 11 のグレイコードは, 1011 と 0101 の XOR を計算して, 1110 となります.

グレイコードにはいろいろな特色があるようです. たとえば, 隣り合うどの整数の組においても, それぞれのグレイコードは, 必ず 1 ビットだけが異なります. たとえば, 7 と 8 を比較すると, 通常の二進法では第 0 ビットから第 3 ビットまでのすべてのビットの値が異なります. が, それぞれのグレイコードを比較すると, 第 3 ビットの値だけが異なります. (ちなみにここでは右端の最下位ビットを第 0 ビットと呼ぶことにします.)

なるほど. たしかに, そのようですね.

しかし, なぜ, そうなるのでしょう.

なぜそうなるのかが, わたしには不思議で不思議でたまりません. 直感的に理解することのできる証明を何とか見つけたいと思い立ってはみたものの, いまのところさっぱりわかりません.

ただ, ひとつ気になった点があります. 隣り合う 2 つの整数の組において, それぞれのグレイコードを比較した際に, どのビットの値だけが異なるのかを見てみますと, ひとつの法則が見えてくる気がするのです. 仮に, 整数 n のグレイコードを G(n), 整数 n-1 のグレイコードを G(n-1) などと書くことにしますと, たとえば n が 4 の倍数である場合は G(n) と G(n-1) の差も 4 の倍数であるようです.

たとえば, 12 と 11 とでグレイコードを比較 (1010 vs 1110) してみますと, 両者の違いは 4 (0100) です. 12 が 4 の倍数であることに関係ありそうに思えます. また, 10 と 9 とでグレイコードを比較 (1111 vs 1101) してみますと, 両者の違いは 2 (0010) です. 10 が 2 の倍数であることに関係ありそうに思えます.

上記の表には載せていませんが, たとえば 24 と 23 で比較してみましょうか. 8 ビットであらわすことにしますと, グレイコードはそれぞれ 00010100 と 00011100 です. 比較してみますと, 両者の違いは 8 (00001000) です. ここでは, 24 が 8 の倍数であることに関係ありそうに思えます.

そのようにして, G(n-1) と n から G(n) を得るのが正しいのかどうか, 少しだけテストしてみます.

package tt4cs.bits;

import org.junit.Test;
import static org.junit.Assert.*;

public class TestForGrayCode {
    
    private String formatBinary(int value) {
        int digits = 8;
        if (255 < value)
            digits = 16;
        if (value < 0 || 65535 < value)
            digits = 32;
        char bits[] = new char[digits];
        for (int i = 0; i < digits; i++)
            bits[digits - i - 1] = (value >>> i & 1) == 1 ? '1' : '0';
        return new String(bits);
    }
    
    private int grayValueOf(int value) {
        return value ^ value >>> 1;
    }
    
    private int anotherGrayValueOf(int value) {
        if (value == 0)
            return 0;
        int d = 0;
        while (d < 32) {
            if ((value >>> d & 1) == 1)
                break;
            d++;
        }
        return anotherGrayValueOf(value - 1) ^ (1 << d);
    }
    
    @Test
    public void compareBotnMethods() {
        for (int i = 0; i < 1024; i++) {
            String g1 = formatBinary(grayValueOf(i));
            String g2 = formatBinary(anotherGrayValueOf(i));
            assertEquals(g1, g2);
        }
    }
    
}

一応, grayValueOf(int) メソッドは前掲のブログ記事に書かれていた方法を試したものであり, anotherGrayValueOf(int) メソッドは G(n-1) と n から G(n) を求める方法を試したものであります. 結果は, Failure も Error もなかったので, どちらの方法でも同じグレイコードを返してくれるようです. (ただ, 後者の方法は, 単純に再帰しまくっているので, 引数の整数の値を大きくすると StackOverflowError を発生させてしまいましたが..)

ちなみに, 日本語版 Wikipedia の グレイコード - Wikipedia の記事 (Oct 11, 2011) には, また少し違う説明のしかたがされていました. そのまま引用してしまいますと, 次のとおりでした.

最上位桁から1であれば残り下桁を反転、0であれば残り下桁を変化させない。 例えば、2進数が1010であれば、グレイコードは1111となる。

一読しただけでは, ちょっとわかりにくい気がして, しばらく考え込んでしまいましたが, 要するにこういうことのようです.

たとえば, 5 の場合, 通常の二進法表記ですと 0101 です. 次の手順でグレイコードを得ます.

1. 第 3 ビットは 0 なので, 0 を持ってきます. (「0 x x x」)
2. 第 2 ビットは 1 なので, 1 を持ってきます. (「0 1 x x」) また, 1 でしたので, 残りの各ビット (第 1 ビットと第 0 ビット) を反転させておきます.
3. 第 1 ビットは 0 なのですが, すでに 1 度反転していますので 1 です. この 1 を持ってきます. (「0 1 1 x」) また, 1 になりましたので, 残りのビット (第 0 ビット) を反転させておきます.
4. 第 0 ビットは 1 なのですが, すでに 2 度反転していますので, やはり 1 です. この 1 を持ってきます. (「0 1 1 1」)

したがって, 5 のグレイコードは 0111 となります.

この方法についても, 先ほどの 1 番目の方法 (grayValueOf メソッドで書いた方法) と同じことを言っているのか別のことを言っているのか, どうもよくわかりません. 別のことを言っているのであれば, それでも結果が同じになるというあたりが, やはり, わたしには不思議で不思議でたまらない感じです.

ビット計算にまつわる話というのは, いまのふだんの仕事にはあまり役に立ちそうではありません. が, 何か大事な基本的な事柄にかかわる部分でもあるような気がして, もう少ししっかり勉強しておきたい気もします. せめて, 小気味よい手品を見せられて口をぽかんと開けながら見つめているだけではなく, もう少し早く, 直感的に 「ああ, こういうことか」 と気づけるようになりたいところです. 少年老い易く学成り難し.