1ビットずつ変えていって全部の数を列挙するグレイコードの生成

一ビットずつ変えていって全部の数を列挙するのをグレイコードというらしいです。
で、通常の連番の２進数の一番上の桁はそのまま、それより下の桁は該当桁と左の桁をXORしていくと、グレイコードになるらしいです。
ということで、bビットのグレイコードを生成するプログラムを書いてみた。

public class GrayCode {

    public static void main(String[] args) {
        int b = 4;//求めるビット数
        int n = 1 << b;
        String form = String.format("%%%ds", b);
        for(int i = 0; i < n; ++i){
            int xor = i ^ (i / 2);
            // int result = i & (n / 2) | xor & (n / 2 - 1);
            int result = xor;//コンパイルエラーだったｗ
            System.out.printf("%3d %s %s%n", i,
                    String.format(form, Integer.toBinaryString(i)).replaceAll(" ", "0"),
                    String.format(form, Integer.toBinaryString(result)).replaceAll(" ", "0"));
        }
    }
}

結果はこんな感じになる。左の２進数が、通常の連番。右の２進数がグレイコード。右のグレイコードのほうは、１ビットずつ変えていけば次の数になる。

  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

グレイコードについては「ハッカーのたのしみ」に書いてありました。
この本、「x & (-x)で一番右の1のビットだけとりだす」とかの計算ハックがたくさん載ってて楽しいです。

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

追記 2012/6/11 14:07 指摘をうけて不要な行をコメントアウト
追記 2012/6/11 15:00 コンパイルとおってなかった