グレイコード

先日某勉強会で出たグレイコードについて、一応概念的には知っていたのですが、実装とかをよく知らなかったため調査。

グレイコードについてはWikipediaに結構詳しく書いてあります。
グレイコード - Wikipedia

このグレイコード、何がいいかというと、数字的な近さがそのままグレイコード表現でも近くなることです。

普通の２進数の場合だと、例えば、

7 => 0111
8 => 1000

となって、数字上ではとなりの数字なのに、２進数では４ビットも違う表現になってしまいます。
しかし、グレイコードの場合は、

7 => 0100
8 => 1100

のようになって、数字上のとなりの数字が、グレイコード表現でも１ビット違いで表現されます。

このグレイコードの構成方法ですが、いろいろとあるのですが、ひとつの簡単な方法としては「反射２進グレイコード」というものがあります。
これは前半部分のグレイコードを反転して、先頭に0,1をつけることによってグレイコードの続きを作っていく方法です。

説明だとよくわからないので、実例で。

 0          0            00
 1   反転   1  0,1付与   01
---  ===>  ---  ======> ----
            1            11
            0            10

この数字 => グレイコード変換は単純な２進演算で実装できます。
この変換を実装するとこんな感じ。

#!/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

こんな感じで数字からグレイコードへの変換は簡単にできます。
ただ、逆のグレイコードから数字への変換はちょっと難しいようです。
ここら辺は後でもうちょっと詳しく調ベる。