グレイコード
先日某勉強会で出たグレイコードについて、一応概念的には知っていたのですが、実装とかをよく知らなかったため調査。
グレイコードについてはWikipediaに結構詳しく書いてあります。
グレイコード - Wikipedia
このグレイコード、何がいいかというと、数字的な近さがそのままグレイコード表現でも近くなることです。
普通の2進数の場合だと、例えば、
7 => 0111 8 => 1000
となって、数字上ではとなりの数字なのに、2進数では4ビットも違う表現になってしまいます。
しかし、グレイコードの場合は、
7 => 0100 8 => 1100
のようになって、数字上のとなりの数字が、グレイコード表現でも1ビット違いで表現されます。
このグレイコードの構成方法ですが、いろいろとあるのですが、ひとつの簡単な方法としては「反射2進グレイコード」というものがあります。
これは前半部分のグレイコードを反転して、先頭に0,1をつけることによってグレイコードの続きを作っていく方法です。
説明だとよくわからないので、実例で。
0 0 00 1 反転 1 0,1付与 01 --- ===> --- ======> ---- 1 11 0 10
この数字 => グレイコード変換は単純な2進演算で実装できます。
この変換を実装するとこんな感じ。
#!/usr/bin/perl use strict; use warnings; for (0 .. 15) { my $gray = $_ ^ ($_ >> 1); print sprintf("%2d => %04b\n", $_, $gray); }
結果
$ ./graycode.pl 0 => 0000 1 => 0001 2 => 0011 3 => 0010 4 => 0110 5 => 0111 6 => 0101 7 => 0100 8 => 1100 9 => 1101 10 => 1111 11 => 1110 12 => 1010 13 => 1011 14 => 1001 15 => 1000
こんな感じで数字からグレイコードへの変換は簡単にできます。
ただ、逆のグレイコードから数字への変換はちょっと難しいようです。
ここら辺は後でもうちょっと詳しく調ベる。