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

この記事では、以下の問題に対する解決策について詳しく解説します。

問題文

ある整数が与えられたとき、その数が2の累乗であるかどうかを判定する必要があります。

この問題は、主に次の2つのアプローチで解くことができます。

アプローチ1: 繰り返し2で割って判定する

数値を順に2で割っていき、途中で割り切れなくなった場合（奇数が出現した場合）は2の累乗ではありません。最終的に1に到達できれば、その数は2の累乗であると判定できます。なお、0は2の累乗に含まれないため、あらかじめ除外しています。この方法の時間計算量は O(log n) です。

サンプルコード

# power of 2
def find(n):
    if (n == 0):
        return False
    while (n != 1):
        if (n % 2 != 0):
            return False
        n = n // 2
    return True
# Driver code
if(find(98)):
    print('Yes')
else:
    print('No')

実行結果

No

アプローチ2: ビット演算を使う

2の累乗となる数値は、2進表現において最上位の1ビットのみが1になっています（例：8 は「1000」）。この性質を利用すると、x と (x - 1) の論理積（AND）が必ず0になることを使って、非常に効率的に判定できます。この方法の時間計算量は O(1) であり、大きな数値を扱う場合にも高速です。

サンプルコード

# power of 2
def find(x):
    # x が 0 でないかどうかのチェックも含まれる
    return (x and (not(x & (x - 1))))
# Driver code
if(find(98)):
    print('Yes')
else:
    print('No')

実行結果

No

まとめ

この記事では、与えられた数値が2の累乗であるかどうかを判定する2つの方法を学びました。ひとつはシンプルに除算を繰り返す方法、もうひとつはビット演算を活用した高速な方法です。特にビット演算による手法は定数時間で判定できるため、パフォーマンスが求められる場面で非常に有効です。用途に応じて使い分けるとよいでしょう。