Pythonで与えられた数がd（2の累乗）の冪乗かどうかを判定する方法

ある数 n と別の値 x が与えられたとき、n が x の冪乗であるかどうかを判定します。ここで、x は必ず 2 の累乗（べき乗）であるものとします。

たとえば、入力が n = 32768、x = 32 の場合、32768 = 32^3 が成り立つため、出力は True になります。

解決のための手順

この問題は、次の手順で解くことができます。

• カウンタ cnt を 0 で初期化します。
• n が 0 ではなく、かつ (n AND (n - 1)) の結果が 0 である場合（つまり n 自身が 2 の累乗である場合）は、以下の処理を行います。
  • n > 1 の間、n を 2 で割り続け、その回数を cnt に加算します。
  • 最後に、cnt mod (log₂ c) が 0 と等しいかどうかを返します。
• 条件を満たさない場合は False を返します。

ポイントとなるのは (n & (n - 1)) == 0 という判定式です。これは「n が 2 の累乗かどうか」を確認する定番のビット演算テクニックです。2 の累乗は二進表現で 1 ビットだけが立っているため、1 を引くとすべての下位ビットが反転し、AND 演算の結果が 0 になります。

実装例

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

def find_pow_of_2(n):
    return (1 + find_pow_of_2(n / 2)) if (n > 1) else 0

def solve(n, c):
    cnt = 0
    if n and (n & (n - 1)) == 0:
        while n > 1:
            n >>= 1
            cnt += 1
        return cnt % (find_pow_of_2(c)) == 0
    return False

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

入力

32768, 32

出力

True

コードの解説

補助関数 find_pow_of_2() は再帰的に呼び出され、引数として渡された数が 2 の何乗であるか（すなわち log₂ の値）を計算します。

メインの solve() 関数では、まず n が 2 の累乗であることを確認し、その後、右シフト演算子 >>= を使って n を繰り返し半分にしながら指数部分をカウントします。最後に、その指数が x の指数（log₂ x）で割り切れるかどうかを判定することで、n が x の冪乗であるかどうかが分かります。