Pythonで部分集合のビットごとのANDが2のべき乗になるかどうかを判定する方法

数値の配列 nums があるとします。このとき、ビットごとのAND（論理積）が2のべき乗となる部分集合が存在するかどうかを判定する必要があります。

問題の例

例えば、入力が nums = [22, 25, 9] の場合、出力は True になります。その理由は、部分集合 {22, 9} を2進数で表すと {10110, 1001} となり、この2つのANDを計算すると 10000 = 16 になり、16は2のべき乗（2⁴）だからです。

解決のための手順

この問題を解くために、以下のアルゴリズムに従います。

• MAX := 32 — 最大32ビットの整数を想定して定義します。
• 関数 solve() を定義します。引数として nums を受け取ります。
• nums のサイズが1の場合、nums[0] が2のべき乗であれば true を返し、そうでなければ false を返します。
• total := 0 と初期化します。
• i を 0 から MAX-1 までループし、total := total OR 2^i を実行します（すべてのビットが立ったマスクを作成）。
• 再び i を 0 から MAX-1 までループし、以下を実行します。
  • ret := total と初期化します。
  • j を 0 から nums のサイズまでループし、nums[j] AND (2^i) がゼロでない場合（つまり i ビット目が立っている場合）、ret := ret AND nums[j] を実行します。
  • ループ終了後、ret が2のべき乗であれば True を返します。
• すべてのビット位置を試しても見つからなければ、False を返します。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

MAX = 32
def is_2s_pow(v):
    return v and (v & (v - 1)) == 0
def solve(nums):
    if len(nums) == 1:
        return is_2s_pow(nums[0])
        total = 0
    for i in range(0, MAX):
        total = total | (1 << i)
    for i in range(0, MAX):
        ret = total
        for j in range(0, len(nums)):
            if nums[j] & (1 << i):
                ret = ret & nums[j]
        if is_2s_pow(ret):
            return True
    return False
nums = [22, 25, 9]
print(solve(nums))

補足：2のべき乗の判定方法

関数 is_2s_pow() では、v & (v - 1) == 0 というビット演算の性質を利用しています。2のべき乗の数値は2進表現で1つのビットだけが立っているため、そこから1を引くと立っているビットより下がすべて1になります。したがって、元の値とのANDが0になれば、その数は2のべき乗だと判定できます。

入力

[22, 25, 9]

出力

True

計算量について

このアルゴリズムの時間計算量は O(MAX × N) です。ここで N は配列の要素数、MAX は32（ビット数）です。各ビット位置ごとに配列全体を一度走査するため、配列サイズが大きくなっても効率的に処理できます。