Pythonで指定した数のグレイコードを求めるプログラムの作成方法

グレイコードとは？

グレイコード（Gray Code）とは、隣り合う数値同士のビット表現が必ず「ちょうど1ビットだけ」異なるように並べた、二進数の順序付け方式です。デジタル回路やエンコーダなど、誤読を防ぎたい場面で活用されていることで知られています。

グレイコードの一例は次の通りです。
[0, 1, 11, 10, 110, 111, …]

問題の定義

ある数 n が与えられたとき、n 番目のグレイコードを求めることを考えます。

例： 入力が n = 12 の場合、出力は 10 になります。これは、12 を二進数で表すと (1100) であり、それに対応するグレイコードは (1010)、その十進数での値が 10 となるためです。

解法のアルゴリズム

この問題は、再帰呼び出しを使うことでシンプルに解くことができます。手順は以下の通りです。

• solve() 関数を定義し、引数として n を受け取ります。
• n が 0 の場合は、0 を返します。
• 変数 x を 1 で初期化します。
• x * 2 <= n が成り立つ間、x を 2 倍し続けます。これにより、n 以下で最大の 2 のべき乗が求まります。
• x + solve(2 * x - n - 1) を返します。

ポイントは、n 以下で最大の 2 のべき乗 x を見つけた後、残りの下位ビット部分を再帰的に処理する点です。これにより、各桁が順番にグレイコードへと変換されていきます。

Pythonでの実装例

class Solution:
    def solve(self, n):
        if n == 0:
            return 0
        x = 1
        while x * 2 <= n:
            x *= 2
        return x + self.solve(2 * x - n - 1)

ob = Solution()
n = 12
print(ob.solve(n))

入力

12

出力

10

補足：ビット演算によるより簡潔な解法

実は、グレイコードには有名な変換公式があります。「n」と「n を1ビット右シフトした値」の排他的論理和（XOR）を取るだけで、一発で求められます。

def solve(n):
    return n ^ (n >> 1)

検証してみましょう。n = 12（二進数で 1100）の場合、12 >> 1 は 6（0110）となり、両者のXORは 1010、つまり十進数で 10 となり、先ほどの結果と一致します。この方法なら再帰もループも不要で、計算量は O(1)。実務ではこちらの公式を使うのが一般的です。