Pythonで数値の全ビットがセット（1）されているかどうかを確認する方法

問題の概要

ある整数 n が与えられたとき、その数値のすべてのビットが 1（セット済み）になっているかどうかを判定します。

例えば、n = 255 の場合、255 の2進表現は「11111111」となり、すべてのビットが 1 なので、結果は True になります。一方、n = 10（2進数で「1010」）のように 0 のビットが含まれる場合は False となります。

解決のアプローチ

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

• 数値が 0 と等しい場合は False を返す
• 数値が 0 より大きい間、以下を繰り返す
  • 最下位ビットが 0（つまり偶数）であれば False を返す
  • 数値を右に1ビットシフトする（2で割った商に更新する）
• ループを最後まで抜けたら True を返す

ここでのポイントは、2進数で「111…1」という形の数値は必ず奇数になるという性質です。途中で偶数が出現した時点で、少なくとも1つのビットが 0 であることが確定します。

実装例

以下のコードで実際の動作を確認してみましょう。

例

def solve(number):
    if number == 0:
        return False
    while number > 0:
        if (number & 1) == 0:
            return False
        number = number >> 1
    return True

n = 255
print(solve(n))

入力

255

出力

True

別の方法：ビット演算を使った効率的な判定

実は、もっと簡潔で効率的な方法があります。すべてのビットが 1 である数 n に対しては、「n & (n + 1) == 0」が常に成り立つという性質を利用します。

例えば n = 255 の場合、n + 1 = 256 となり、255 & 256 = 0 になります。これは、すべてのビットが 1 の数に 1 を加えると桁上がりが発生し、元の数との共通ビットがなくなるためです。

def solve(number):
    return number != 0 and (number & (number + 1)) == 0

n = 255
print(solve(n))  # True

この方法ならループ処理が不要になり、O(1) の時間計算量で判定できます。数値が非常に大きい場合や、何度も判定を行う場合には特に有効です。