Pythonで算術演算子を使わずにxが2のn乗で割り切れるか判定する方法

問題の概要

二つの整数 x と n が与えられたとき、算術演算子（+、-、*、/、%など）を使わずに、x が 2 の n 乗（2^n）で割り切れるかどうかを判定します。

例えば、入力が x = 32、n = 5 の場合、32 = 2^5 であるため、出力は True になります。

解法の考え方

この問題はビット演算を使うことでエレガントに解くことができます。ポイントは以下の通りです。

• 2^n で割り切れる数は、2進数表現において下位 n ビットがすべて 0 になっています。
• (1 << n) - 1 を計算すると、下位 n ビットだけが 1 になったマスクが得られます（例：n = 5 なら 0b11111 = 31）。
• x とこのマスクを AND 演算した結果が 0 であれば、x の下位 n ビットはすべて 0、つまり x は 2^n で割り切れることになります。

アルゴリズムの手順

• x AND ((1 << n) - 1) の結果が 0 であれば、True を返す。
• それ以外の場合は False を返す。

実装例（Python）

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

def solve(x, n):
    if (x & ((1 << n) - 1)) == 0:
        return True
    return False

x = 32
n = 5
print(solve(x, n))

入力

32, 5

出力

True

動作の解説

x = 32（2進数で 100000）、n = 5 の場合を具体的に見てみます。

• (1 << 5) - 1 = 32 - 1 = 31（2進数で 11111）
• 100000 AND 11111 = 000000 → 結果は 0
• したがって、32 は 2^5 = 32 で割り切れるため True が返されます。

この手法では剰余演算（%）や除算を一切使わず、ビット演算だけで判定できるため、非常に高速です。計算量は O(1) となり、大きな数値に対しても効率的に動作します。