Pythonで数値が2の累乗かどうかを判定する方法

プログラミングでは、ある正の整数が2の累乗（べき乗）であるかどうかを判定したい場面がよくあります。例えば、1024は 2¹⁰ なので2の累乗ですが、1000は2の累乗ではありません。

この記事では、Pythonを使って数値が2の累乗かどうかを判定するシンプルなアルゴリズムを紹介します。

判定の考え方

2の累乗には重要な性質があります。それは、2で繰り返し割り続けると、最終的に必ず1になるという点です。

• 1024 ÷ 2 = 512
• 512 ÷ 2 = 256
• 256 ÷ 2 = 128
  …（中略）…
  4 ÷ 2 = 2、2 ÷ 2 = 1

一方、2の累乗ではない数（例えば6など）を2で割り続けると、最終的に1にならず小数や端数が残ります。この性質を利用して判定を行います。

アルゴリズムの手順

1. n が 1 より大きい間、n を 2 で割り続ける
2. ループ終了後、n が 1 と等しければ True（2の累乗）、そうでなければ False を返す

Pythonでの実装例

class Solution:
    def solve(self, n):
        while n > 1:
            n /= 2
        return n == 1

ob = Solution()
print(ob.solve(1024))

入力

1024

出力

True

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

上記の方法は直感的で分かりやすいですが、除算を繰り返すため計算量は O(log n) となります。より高速に判定したい場合は、ビット演算を活用する方法が有名です。

2の累乗はバイナリ表現で「1桁だけ1が立っている」特徴があります。

• 1 → 0001
• 2 → 0010
• 4 → 0100
• 8 → 1000

この性質から、次の式で1回の演算で判定できます。

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_two(1024))  # True
print(is_power_of_two(1000))  # False

n & (n - 1) は、n の最下位の1ビットを消す操作です。結果が0になるのは、n に1ビットしか立っていない場合、つまり n が2の累乗の場合だけです。

まとめ

2の累乗の判定には、①2で割り続けて1になるか確認する方法と、②ビット演算 n & (n - 1) == 0 を使う方法があります。学習用途や可読性重視なら前者、パフォーマンス重視なら後者がおすすめです。状況に応じて使い分けましょう。