C++でグレイコード（Gray Code）を生成するアルゴリズムと実装例

グレイコード（Gray Code）とは、隣り合う2つの値が必ず1ビットだけ異なるという性質を持つ二進数体系のことです。本記事では、コードのビット数を表す非負整数 n が与えられたときに、グレイコードの列を出力する方法を解説します。グレイコードの列は必ず 0 から始まる必要があります。

例えば、入力が 2 の場合、出力は [0, 1, 3, 2] となります。これは、0 のグレイコードが 00、1 が 01、2 が 11、3 が 10 であるためです。隣接する値同士を比較すると、それぞれ1ビットしか変わっていないことが確認できます。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 結果を格納するための配列 ans を用意します。
• 各数値についてグレイコードを求め、ans 配列へ順番に追加していきます。
• 数値をグレイコードへ変換するには、元の数値と、それを1ビット右にシフトした値との排他的論理和（XOR）を計算します。

グレイコードへの変換は「g = i ^ (i >> 1)」という非常にシンプルな式で表されます。この変換を用いると、隣接する数値間で必ず1ビットのみが変化することが数学的に保証されるため、複雑な再帰処理や条件分岐は一切不要です。

C++による実装例

理解を深めるために、以下のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        for(int i = 0; i<1<<n; i++){
            ans.push_back(i^(i>>1));
        }
        return ans;
    }
};

main(){
    Solution ob;
    print_vector(ob.grayCode(4));
}

入力

4

出力

[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]

処理のポイント

この実装では、ループを 0 から 2^n - 1 まで回し、各インデックス i に対して i ^ (i >> 1) を計算しています。ビットシフトとXORだけで構成されているため、処理は極めて高速で、計算量は O(2^n) となります。

また、出力されたリストを2進数で確認すると、隣接する要素間で常に1ビットだけが反転していることが分かります。この性質により、グレイコードはデジタル通信やエラー検出、ロータリーエンコーダなど、誤読を防ぎたい場面で広く活用されています。