C++プログラムで再帰を使ってバイナリをグレイコードに変換する方法

バイナリ数とは、0と1の2つのビットのみで構成される数値のことです。

グレイコードは、特殊な性質を持つバイナリ数の一種です。その性質とは、隣り合う2つのコード値が最大でも1ビットしか異ならないというものです。この特性により、グレイコードはカルノー図(Kマップ)、誤り訂正、デジタル通信などの分野で広く活用されています。

そのため、バイナリからグレイコードへの変換は重要な処理となります。本記事では、再帰(リカージョン)を使ってバイナリをグレイコードに変換するアルゴリズムとC++での実装例を解説します。

変換例

具体的な入出力の例を見てみましょう。

入力 : 1001
出力 : 1101

アルゴリズム

再帰を用いた変換の手順は以下の通りです。

ステップ1 : 入力 n に対して以下を処理する :
    ステップ1.1 : n = 0 の場合、gray = 0 を返す。
    ステップ1.2 : 下位2ビットが異なる場合、
        gray = 1 + 10 × (n/10 を引数としてステップ1へ)。
    ステップ1.3 : 下位2ビットが同じ場合、
        gray = 10 × (n/10 を引数としてステップ1へ)。
ステップ2 : gray を出力する。
ステップ3 : 終了。

ポイントは、数値を10で割る(右シフトに相当)操作を繰り返しながら、下位2桁の関係を再帰的に判定していく点です。最上位ビットは常に元のバイナリと同じになり、それ以降の各ビットは「隣接する2ビットが一致していれば0、異なっていれば1」という排他的論理和(XOR)の考え方で決まります。

C++による実装例

#include <iostream>
using namespace std;
int binaryGrayConversion(int n) {
    if (!n)
        return 0;
    int a = n % 10;
    int b = (n / 10) % 10;
    if ((a && !b) || (!a && b))
        return (1 + 10 * binaryGrayConversion(n / 10));
    return (10 * binaryGrayConversion(n / 10));
}
int main() {
    int binary_number = 100110001;
    cout<<"The binary number is "<<binary_number<<endl;
    cout<<"The gray code conversion is "<<binaryGrayConversion(binary_number);
    return 0;
}

コードの解説

• n % 10 で最下位ビット(a)を取得し、(n / 10) % 10 でその隣のビット(b)を取得します。
• a と b が異なる場合(XORが1の場合)は 1 + 10 * 再帰呼び出し を返し、同じ場合は 10 * 再帰呼び出し を返します。
• n が 0 になった時点で再帰が終了し、結果が下位の桁から順に組み立てられていきます。

実行結果

The binary number is 100110001
The gray code conversion is 110101001

このように、再帰処理を用いることで、バイナリ数を簡潔かつ効率的にグレイコードへ変換できます。ビット演算(>> や ^)を使えばさらに高速化することも可能ですが、再帰的なアプローチはロジックの理解にも役立つ優れた手法です。