ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Java »【Java】グレイコード変換をする

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


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


 まずは2進数のグレイコード変換の関数を作ってみる。『「変換したい2進数」と、「変換したい2進数を1ビット右にシフトし、先頭に0をつけたもの」との排他的論理和をとる。例えば、変換したい2進数が「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】平衡三進数変換をする


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/217-f85ef972
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop