【Java】グレイコード変換をする

　せっかくなので、前回の「基数変換」で作ったライブラリを使って、「グレイコード変換」をやってみよう。グレイコード自体の説明は Wikipedia(日本語版) に丸投げするが、実のところを言うと Wikipedia の英語版のページには C言語ソースも載っている。これらを参考に、簡単なグレイコード変換の関数を作ってみよう。

■2進数のグレイコード変換
■n進数のグレイコード変換

　まずは２進数のグレイコード変換の関数を作ってみる。『「変換したい２進数」と、「変換したい２進数を１ビット右にシフトし、先頭に０をつけたもの」との排他的論理和をとる。例えば、変換したい２進数が「1010」であれば、「0101」との排他的論理和をとる。その結果、グレイコードは「1111」になる』(Wikipedia) と書いてあるが、英文ページのソースを見た方が早いだろう。そのまま Java にしてみた。

●2進数グレイコード変換

/**<h1>2進数グレイコードに変換する</h1>
 * @param bin ： 2進数表現値
 * @return<b>int</b> ： 2進数グレイコード表現値
 */
public static final int binaryToGray(final int bin) {
    return (bin ^ (bin >>> 1));
}

/**<h1>2進数グレイコードから2進数値へ変換する</h1>
 * @param gray ： 2進数グレイコード表現値
 * @return<b>int</b> ： 2進数表現値
 */
public static final int grayToBinary(int gray) {
    for (int mask = (gray >>> 1); mask != 0; mask >>>= 1) {
        gray = gray ^ mask;
    }
    return gray;
}


//メインでは...
int n = 20;
for (int i = 0; i <= n; i++) {
    System.out.print("i = " + i + " -> " + Integer.toString(i, 2) + " (2)");    //普通の2進数
    int gray = binaryToGray(i);
    System.out.println(", " + Integer.toString(gray, 2) + " (Gray2)");    //グレイコード
}

i = 0 -> 0 (2), 0 (Gray2)
i = 1 -> 1 (2), 1 (Gray2)
i = 2 -> 10 (2), 11 (Gray2)
i = 3 -> 11 (2), 10 (Gray2)
i = 4 -> 100 (2), 110 (Gray2)
i = 5 -> 101 (2), 111 (Gray2)
i = 6 -> 110 (2), 101 (Gray2)
i = 7 -> 111 (2), 100 (Gray2)
i = 8 -> 1000 (2), 1100 (Gray2)
i = 9 -> 1001 (2), 1101 (Gray2)
i = 10 -> 1010 (2), 1111 (Gray2)
i = 11 -> 1011 (2), 1110 (Gray2)
i = 12 -> 1100 (2), 1010 (Gray2)
i = 13 -> 1101 (2), 1011 (Gray2)
i = 14 -> 1110 (2), 1001 (Gray2)
i = 15 -> 1111 (2), 1000 (Gray2)
i = 16 -> 10000 (2), 11000 (Gray2)
i = 17 -> 10001 (2), 11001 (Gray2)
i = 18 -> 10010 (2), 11011 (Gray2)
i = 19 -> 10011 (2), 11010 (Gray2)
i = 20 -> 10100 (2), 11110 (Gray2)

　「grayToBinary()」は使ってないが、グレイコードから2進数表現に戻す関数なので、「binaryToGray()」の値を与えると元に戻る。ビット演算しかしてないので、コードは丸写しである(笑)。他の言語に移植するときもあまり変わらないだろう。


●n進数でのグレイコード変換

　次に、n進数でのグレイコード変換をやってみよう。これも考え方自体は同じなので、前回作った「baseRemainder()」を使って基数分解し、それぞれの桁の排他的論理和を取れば良い。それを「digitsToInt()」で数値に戻してやれば完了だ。

　なお、n進数での排他的論理和は「2つの数 a, b の差を基数で割った余り」(ただし、正の値にする)で計算できる。気をつけなくてはいけないのは、剰余を計算する場合、Java は「-5 % 2 = -1」のように負の値になるが、Ruby では「-5 % 2 = 1」のように正の値になる点だ。除算もそうだが、負の剰余を使うときには言語によって仕様が違うので、他の言語に移植するときには答えの符号がどうなるのか、一旦確認した方が良いだろう。

●n進数グレイコード変換

import java.util.ArrayList;
import java.util.List;

/**<h1>n進数グレイコードに変換する</h1>
 * @param value ： 元のn進数表現値
 * @param radix ： 変換する基数
 * @return<b>int</b> ： n進数グレイコード表現値
 */
public static final int toGray(final int value, final int radix) {
    if (radix == 2) {
        return binaryToGray(value);
    }

    final List<Integer> digits = baseRemainder(value, radix);    //前回作った関数
    final int len = digits.size();
    for (int i = 0; i < len - 1; i++) {
        int m = (digits.get(i) - digits.get(i + 1)) % radix;    //n進数の排他的論理和
        int x = (m < 0) ? (m + radix) : m;        //剰余を正の値にする
        digits.set(i, x);
    }

    return digitsToInt(digits, radix);    //前回作った関数
}


//メインでは...
int radix = 3;    //n進数
int n = 26;
for (int i = 0; i <= n; i++) {
    System.out.print("i = " + i + " -> " + Integer.toString(i, radix) + " (" + radix + ")");    //普通のn進数
    int v = toGray(i, radix);
    System.out.println(", " + Integer.toString(v, radix) + " (Gray" + radix + ")");    //グレイコード
}

i = 0 -> 0 (3), 0 (Gray3)
i = 1 -> 1 (3), 1 (Gray3)
i = 2 -> 2 (3), 2 (Gray3)
i = 3 -> 10 (3), 12 (Gray3)
i = 4 -> 11 (3), 10 (Gray3)
i = 5 -> 12 (3), 11 (Gray3)
i = 6 -> 20 (3), 21 (Gray3)
i = 7 -> 21 (3), 22 (Gray3)
i = 8 -> 22 (3), 20 (Gray3)
i = 9 -> 100 (3), 120 (Gray3)
i = 10 -> 101 (3), 121 (Gray3)
i = 11 -> 102 (3), 122 (Gray3)
i = 12 -> 110 (3), 102 (Gray3)
i = 13 -> 111 (3), 100 (Gray3)
i = 14 -> 112 (3), 101 (Gray3)
i = 15 -> 120 (3), 111 (Gray3)
i = 16 -> 121 (3), 112 (Gray3)
i = 17 -> 122 (3), 110 (Gray3)
i = 18 -> 200 (3), 210 (Gray3)
i = 19 -> 201 (3), 211 (Gray3)
i = 20 -> 202 (3), 212 (Gray3)
i = 21 -> 210 (3), 222 (Gray3)
i = 22 -> 211 (3), 220 (Gray3)
i = 23 -> 212 (3), 221 (Gray3)
i = 24 -> 220 (3), 201 (Gray3)
i = 25 -> 221 (3), 202 (Gray3)
i = 26 -> 222 (3), 200 (Gray3)

　「baseRemainder()」と「digitsToInt()」は前回作ったものをそのままコピーしてきて欲しい。これも英語版ページのソースと内容的には同じものとなる。


（関連記事）
【Java】n進数変換（基数変換）・桁の分割をする
【Java】平衡三進数変換をする

■参考になる書籍