Pythonで数値の2進表現における連続する1の最長距離を求めるプログラム

整数 N が与えられたとき、その2進表現の中で隣り合う2つの「1」の間の最長距離を求めることを考えます。2つ以上の「1」が存在しない場合は 0 を返します。

たとえば入力が 71 の場合、出力は 4 になります。71 を2進数で表すと 1000111 であり、この中には「1」が4つ含まれています。先頭の「1」と2番目の「1」の間には3つの「0」が挟まれているため距離は 4 となり、それ以降の「1」同士はすべて距離 1 で隣接しています。したがって、この場合の最長距離は 4 です。

解法の考え方

この問題は、ビット列を左から順に走査しながら「1」が出現した位置を記録し、直前の「1」との距離を都度比較することで解けます。具体的な手順は次のとおりです。

1. N の2進表現を文字列として取得し、各ビットを要素とするリスト K を作成します。
2. 変数を初期化します:Max = 0(最大距離)、C = 0(直前の「1」の位置)、S = 0(現在の「1」の位置)。
3. フラグ Flag を False に設定します(最初の「1」を検出済みかどうかを管理します)。
4. i を 0 から K の長さまで繰り返します。
   • K[i] が「1」で、まだ最初の「1」を検出していない場合:C = i として位置を記録し、Flag を True にします。
   • K[i] が「1」で、すでに最初の「1」を検出済みの場合:S = i とし、abs(S − C) が現在の Max より大きければ Max を更新します。その後、C = S として基準位置を移動します。
5. ループ終了後、Max を返します。

Pythonでの実装例

以下が実際の実装コードです。

def solve(N):
    B = bin(N).replace('0b', '')
    K = list(B)
    Max = 0
    C = 0
    S = 0
    Flag = False
    for i in range(len(K)):
        if K[i] == '1' and C == 0 and not Flag:
            C = i
            Flag = True
        elif K[i] == '1' and Flag:
            S = i
            if Max < abs(S - C):
                Max = abs(S - C)
            C = S
    return Max

n = 71
print(solve(n))

入力

71

出力

4

コードのポイント

• bin(N) は整数を 0b... 形式の2進文字列に変換するため、replace('0b', '') で接頭辞を取り除いてからリスト化しています。
• 2進表現には先頭に必ず「1」が現れるため、最初の「1」の位置は常にインデックス 0 になります。
• 「1」を見つけるたびに基準位置 C を更新することで、隣り合う「1」同士の距離だけを正しく測定できます。
• 計算量は、ビット数を d とすると時間計算量 O(d)、空間計算量 O(d)(d = log₂N + 1)となり、非常に効率的です。