Pythonで整数をゼロに変換するための最小ビット演算回数を求めるプログラム

問題概要

整数 n が与えられます。この n を、以下の2種類の操作を何度でも繰り返し適用して 0 に変換することを考えます。

• 操作1: n の2進表現の中で最も右側のビット(最下位ビット)を選び、その値を反転する。
• 操作2: 第 i ビットについて、「第 (i−1) ビットが 1 であり、第 (i−2) ビットから第 0 ビットまですべて 0 である」という条件を満たす場合にのみ、そのビットを反転できる。

目的は、n を 0 に変換するために必要な最小の操作回数を求めることです。

具体例

入力が n = 6 の場合を考えてみます。6 の2進表現は "110" なので、出力は 4 となります。実際の変換手順は次のとおりです。

1. "110" → 操作2で第2ビットを反転して "010" へ
2. "010" → 操作1で最右ビットを反転して "011" へ
3. "011" → 操作2で第1ビットを反転して "001" へ
4. "001" → 操作1で最右ビットを反転して "000" へ

解法のアプローチ

すべての状態を幅優先探索で調べることも可能ですが、この問題にはエレガントな数学的性質があります。n を 0 にする最小操作回数は、n の2進表現をグレイコードとみなし、それを通常の2進数へ変換した値と一致することが知られています。

グレイコードから2進数への変換は、以下のシンプルな手順で行えます。

• 最上位ビットから順に各ビット d を走査する。
• 直前に確定させた累積ビット(last)が 1 の場合は、現在のビットを反転する(d = 1 - d)。
• 処理後のビットを結果リスト m に追加し、last を更新する。

最後に、得られたビット列を2進数として解釈し、10進数の整数に変換して返します。計算量は O(log n) と非常に効率的で、大きな数でも即座に答えを導き出せます。

Pythonでの実装例

def solve(n):
    # 整数nを2進数のビット列(リスト)に変換
    n = list(map(int, bin(n)[2:]))
    m = []
    last = 0
    for d in n:
        if last == 1:
            d = 1 - d  # 直前の累積ビットが1なら現在のビットを反転
        last = d
        m.append(d)
    # 結果のビット列を連結し、2進数として10進数に変換
    m = ''.join(map(str, m))
    return int(m, 2)

n = 6
print(solve(n))

入力

n = 6

出力

4

まとめ

この問題を効率的に解く鍵となるのは、グレイコードとの対応関係に気づくことです。ビット列を一度だけ左から右へ走査すれば答えが求まるため、状態を網羅的に探索する手法よりもはるかに高速です。ビット操作と符号理論の性質を活かした美しいアルゴリズムの好例と言えるでしょう。