Pythonで数値の2進表現における連続するセットビットの個数が昇順になっているかを判定する方法

問題概要

正の整数 n が与えられたとき、その2進表現（ビットパターン）の中に現れる「連続した1（セットビット）」の各グループの長さが、左から右へ向かって昇順（直前のグループより短くならない）になっているかどうかを判定する問題です。

具体例

例えば n = 1775 の場合、2進表現は 11011101111 となります。連続する1のグループは [2, 3, 4] であり、左から右へ増加しているため、結果は True になります。

一方、n = 13（2進表現: 1101）の場合、グループは [2, 1] となり後半が短くなるため、結果は False になります。

解法のアプローチ

数値を2進表現の文字列に変換し、先頭から1ビットずつ走査しながら、現在の「1の連続」の長さと直前のグループの長さを比較していくのが基本的な考え方です。手順は以下の通りです。

1. bin(n)[2:] で接頭辞「0b」を除いた2進表現の文字列を取得します。
2. 直前のグループ長 prev と現在のグループ長 curr を 0 で初期化します。
3. 各ビットについて次のように処理します。
   • ビットが '1' の場合は curr を 1 増やします。
   • ビットが '0' で、直前まで1の連なりがあった場合（curr が 0 でない場合）は、curr と prev を比較します。curr が prev より小さければ False を返し、そうでなければ prev = curr として curr を 0 にリセットします。
4. 走査が終わったら、最後のグループについても同じ比較を行い、条件を満たさなければ False を返します。
5. すべてのチェックを通過できれば True を返します。

Pythonでの実装例

def solve(n):
    bits = bin(n)[2:]   # 接頭辞「0b」を除いた2進表現
    prev = 0            # 直前の「1の連続」グループの長さ
    curr = 0            # 現在の「1の連続」グループの長さ

    for bit in bits:
        if bit == '1':
            curr += 1
        else:
            if curr != 0:        # 1の連なりが終わった時点で判定
                if curr < prev:  # 直前のグループより短ければ False
                    return False
                prev = curr
                curr = 0

    # 最後のグループの判定
    if curr != 0 and curr < prev:
        return False
    return True


n = 1775
print(solve(n))

入力

1775

出力

True

計算量の目安

時間計算量はビット数に比例する O(log n)、空間計算量も2進文字列を保持するため O(log n) です。文字列化せずシフト演算などでビットを直接調べるようにすれば、空間計算量を O(1) に抑えることもできます。

まとめ

2進表現を先頭から走査しながら「1の連続」グループの長さを記録し、隣り合うグループ同士を比較するだけで、この問題を効率的に解くことができます。ビット操作の基礎を固めるのに適した練習問題なので、さまざまな数値で動作を確認してみてください。