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

一ビットずつ変えていって全部の数を列挙するのをグレイコードというらしいです。
で、通常の連番の2進数の一番上の桁はそのまま、それより下の桁は該当桁と左の桁を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;//コンパイルエラーだったw
            System.out.printf("%3d %s %s%n", i,
                    String.format(form, Integer.toBinaryString(i)).replaceAll(" ", "0"),
                    String.format(form, Integer.toBinaryString(result)).replaceAll(" ", "0"));
        }
    }
}


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

  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のビットだけとりだす」とかの計算ハックがたくさん載ってて楽しいです。

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

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

  • 作者: ジュニア,ヘンリー・S.ウォーレン,Jr.,Henry S. Warren,滝沢徹,玉井浩,鈴木貢,赤池英夫,葛毅,藤波順久
  • 出版社/メーカー: エスアイビーアクセス
  • 発売日: 2004/09
  • メディア: 単行本
  • 購入: 35人 クリック: 732回
  • この商品を含むブログ (129件) を見る


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