Pythonで解く「バイナリギャップ」問題：2進数表現における連続する1同士の最大距離を求める方法

この記事では、正の整数 N が与えられたとき、その2進数表現の中で隣り合う2つの「1」の間の距離として最も長いもの（バイナリギャップ）を求めるアルゴリズムを、Pythonのコード例とともにわかりやすく解説します。

問題の概要

正の整数 N の2進数表現において、連続して出現する2つの「1」の間の距離のうち最大のものを求めます。ここでいう「距離」とは、2つの「1」の位置（インデックス）の差のことです。もし「1」が2つ以上存在しない場合は、0 を返します。

具体例：入力が 22 の場合

22 を2進数に変換すると 10110 となります。この中には3つの「1」があり、「1」が連続するペアは2組あります。

• 最初のペア（先頭の「1」と次の「1」）の距離は 2
• 次のペア（2つ目と3つ目の「1」）の距離は 1

したがって、答えはこれらのうち大きい方である 2 となります。

解法のアプローチ

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

1. N の2進数表現を文字列として取得し、各ビットをリスト K に格納する
2. 最大距離を記録する変数 Max、直前に見つけた「1」の位置 C、現在の「1」の位置 S を初期化する（Max = 0、C = 0、S = 0）
3. フラグ Flag を False に設定し、最初の「1」を検出したかどうかを管理する
4. リスト K を先頭から順に走査する
   • K[i] が「1」であり、まだ最初の「1」を見つけていない場合 → その位置 i を C に記録し、Flag を True にする
   • K[i] が「1」であり、すでに Flag が True の場合 → その位置 i を S に記録し、|S − C| が Max より大きければ Max を更新する。その後、C を S に更新する
5. 走査が終わったら Max を返す

Pythonによる実装例

以下は、上記のロジックを実装したPythonコードです。bin() 関数で2進数文字列を取得し、1文字ずつリストとして処理しています。なお、文字列や整数の比較には is ではなく == を使うのがPythonのベストプラクティスです。

class Solution:
    def binaryGap(self, N):
        # 2進数表現を文字列として取得し、リスト化する
        B = bin(N).replace('0b', '')
        K = list(B)

        Max = 0   # 最大距離
        C = 0     # 直前の「1」の位置
        S = 0     # 現在の「1」の位置
        Flag = False  # 最初の「1」を検出済みかどうか

        for i in range(len(K)):
            if K[i] == '1' and C == 0 and not Flag:
                # 最初の「1」を検出
                C = i
                Flag = True
            elif K[i] == '1' and Flag:
                # 次の「1」を検出し、距離を計算
                S = i
                if Max < abs(S - C):
                    Max = abs(S - C)
                C = S

        return Max

ob = Solution()
print(ob.binaryGap(22))

実行結果

入力：22
出力：2

処理の流れを追ってみる

入力 22（2進数で 10110）の場合、処理は以下のように進みます。

• i = 0：K[0] が「1」でまだ Flag が False → C = 0、Flag = True
• i = 2：K[2] が「1」→ S = 2、|2 − 0| = 2 > Max(0) なので Max = 2、C = 2
• i = 3：K[3] が「1」→ S = 3、|3 − 2| = 1 < Max(2) なので Max は変わらず、C = 3

最終的に Max = 2 が返され、期待どおりの出力が得られます。

計算量について

このアルゴリズムは2進数表現の各ビットを一度だけ走査するため、時間計算量は O(log N)、使用する補助記憶域もビット列の長さ分だけなので O(log N) となります。N の桁数に対して線形に動作するため、非常に効率的な解法です。

まとめ

バイナリギャップ問題は、2進数変換と一次元の走査を組み合わせた基本的なアルゴリズム問題です。「最初の1を見つける」「以降の1との距離を測り最大値を更新する」というシンプルな状態管理の考え方は、他の文字列・ビット操作系の問題にも応用できます。ぜひ実際にコードを動かして、挙動を確認してみてください。