Pythonで数値が2の累乗かどうかを判定するプログラム

本記事では、与えられた数値が2の累乗（べき乗）であるかどうかを判定する方法について、考え方と実装手順をわかりやすく解説します。

問題の定義

ある整数 n が与えられたとき、その数が2の累乗（1, 2, 4, 8, 16, …）であるかどうかを判定します。

アプローチ

判定には「繰り返し2で割る」というシンプルな方法を使います。考え方は以下の通りです。

• 入力された数値 n を、1になるまで繰り返し2で割っていきます（n = n // 2）。

• 割る過程で n % 2 の結果が0以外（奇数）になり、かつ n が1でない場合は、その数は2の累乗ではありません。

• 最終的に n がちょうど1になれば、その数は2の累乗であると判定できます。

それでは、実際の実装を見てみましょう。

実装例

def isPowerOfTwo(n):
    if (n == 0):
        return False
    while (n != 1):
        if (n % 2 != 0):
            return False
        n = n // 2
    return True

# メイン処理
if(isPowerOfTwo(40)):
    print('Yes')
else:
    print('No')

出力結果

No

この例では40を判定しています。40を2で割ると20、さらに10、5となり、5は奇数のため2の累乗ではないと正しく判定されました。

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

より効率よく判定したい場合は、ビット演算を利用する方法もあります。2の累乗は二進表現で「1桁だけ1が立っている」特徴を持つため、n & (n - 1) の結果が0になれば2の累乗であると判定できます。

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

print(isPowerOfTwo(64))   # True
print(isPowerOfTwo(100))  # False

この方法ならループ処理が不要で、O(1)の定数時間で判定できるため、大きな数値を扱う場合にも有効です。

まとめ

本記事では、繰り返し2で割る方法とビット演算を使う方法の2つのアプローチにより、数値が2の累乗かどうかを判定するPythonプログラムを紹介しました。状況に応じて使い分けることで、より効率的なコードを書くことができます。