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

整数が与えられたとき、その2進表現（バイナリ表現）の中で最も長く連続する「1」の長さを求めるPythonプログラムを紹介します。

例

入力: n = 15
出力: 4
15 の2進表現は 1111 です。

この場合、「1」が4つ連続しているため、答えは4となります。

アルゴリズム

1. 数値を入力として受け取ります。
2. カウンタ変数 c を 0 で初期化します。
3. n が 0 になるまでの反復回数を数えます。
4. ビット演算 n & (n << 1) を行うことで、1の連続列の長さが毎回1つずつ短くなっていきます。

アルゴリズムのポイント

この手法の鍵となるのは n & (n << 1) というビット演算です。n を1ビット左にシフトした値と元の n の論理積（AND）を取ると、それぞれの「1」の連続列から末尾の1ビットが取り除かれます。これを繰り返し、n が 0 になるまでのループ回数を数えれば、それが最長の連続する1の長さになります。

例えば n = 15（2進数で 1111）の場合：

1111 & 11110 = 1110 （c = 1）
1110 & 11100 = 1100 （c = 2）
1100 & 11000 = 1000 （c = 3）
1000 & 10000 = 0000 （c = 4）

4回の反復で 0 になったため、答えは 4 です。

サンプルコード

# 数値の2進表現における
# 最長の連続する1の長さを求める
# Pythonプログラム
def maxlength(n):
    # 結果を初期化
    c = 0
    # n = 0 に到達するまでの
    # 反復回数を数える
    while (n != 0):
        # この操作により、
        # 1の各連続列の長さが1ずつ減る
        n = (n & (n << 1))
        c = c + 1
    return c

# ドライバーコード
n = int(input("Enter The Number ::>"))
print("Maximum Length of 1's ::>", maxlength(n))

実行結果

Enter The Number ::>15
Maximum Length of 1's ::>4

まとめ

このアルゴリズムは、2進文字列を文字ごとに走査する方法と比べて、ビット演算だけで処理できるため非常に効率的です。計算量は最長の連続する1の長さに比例し、実装もシンプルなので、ビット操作の練習題材としてもおすすめです。