Pythonで2進数表現における最長の連続する1を見つけるプログラム

問題の概要

負でない整数 n が与えられたとき、その2進数表現の中に現れる「1」が連続して並んでいる区間のうち、最も長いものの長さを求めることを考えます。

例として、入力が n = 1469 の場合を見てみましょう。1469 を2進数に変換すると「10110111101」となり、この中には「1」が4個連続して並んでいる箇所が存在します。したがって、出力は 4 となります。

解法のアプローチ

この問題は、ビット演算を活用することで非常にエレガントに解くことができます。手順は以下の通りです。

• カウント用の変数 count を 0 で初期化します。
• n が 0 になるまで、次の処理を繰り返します。
  • n := n AND(n を1ビット左シフトした値)
  • count := count + 1
• 最後に count を返します。

なぜこの方法が有効なのかというと、「n & (n << 1)」という操作によって、隣り合う2つのビットがどちらも1である位置だけが残るためです。つまり、ループを1回実行するごとに、連続する「1」の列の長さが1ずつ短くなっていきます。その結果、最初に存在していた最長の連続「1」の長さと同じ回数だけループが実行され、それがそのまま答えになります。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

def solve(n):
    count = 0
    while n != 0:
        n = n & (n << 1)
        count = count + 1

    return count

n = 1469
print(solve(n))

入力

1469

出力

4

計算量の評価

このアルゴリズムの時間計算量は O(log n) です。各ループの実行ごとに連続する「1」の長さが少なくとも1ずつ減少し、ループの回数は n のビット長(およそ log₂n)を超えないためです。また、追加のメモリをほとんど必要としないため、空間計算量は O(1) と非常に効率的です。ビット演算のみで構成されているため、文字列変換などを用いる方法よりも高速に動作する点も大きなメリットといえます。