C言語で2の累乗かどうかを判定する方法（ビット演算の活用）

ある整数 n が与えられたとき、その数が2の累乗（べき乗）であるかどうかを判定する問題を考えてみましょう。例えば、n = 16 の場合は true を返し、n = 12 の場合は false を返します。

ビット演算を使った判定方法

この問題は、論理演算（ビット演算）を使うことで効率的に解くことができます。2の累乗となる数を2進数で表すと、最上位ビット（MSB）だけが1で、それ以外のビットはすべて0になります。

ここで注目すべきは、「n AND (n − 1)」という計算です。n が2の累乗であれば、この演算結果は必ず0になります。

具体例として n = 16 を見てみましょう。16 は2進数で「10000」、n − 1 = 15 は「01111」と表されます。これらのAND演算を取ると次のようになります。

10000 AND 01111 = 00000 = 0

結果が0になったため、16は2の累乗であると判定できます。これは、2の累乗から1を引くと、立っていたビットが0になり、それより下位のビットがすべて1になるという性質を利用したテクニックです。

C言語での実装例

以下に実際のC言語のコードを示します。

#include <stdio.h>
#include <stdbool.h>

bool isPowerOfTwo(int n){
    return (n > 0 && !(n & (n - 1)));
}

int main() {
    printf("%s\n", isPowerOfTwo(16) ? "true" : "false");
    printf("%s\n", isPowerOfTwo(12) ? "true" : "false");
    printf("%s\n", isPowerOfTwo(1) ? "true" : "false");
    printf("%s\n", isPowerOfTwo(32) ? "true" : "false");
    return 0;
}

入力

16
12
1
32

出力

true
false
true
true

コードのポイント

• n > 0 のチェック： 0や負の数は2の累乗ではないため、事前に除外しています。
• n & (n - 1)： ビットごとのAND演算により、n が2の累乗の場合のみ結果が0になります。
• 計算量： ループや再帰を使わずO(1)で動作するため、非常に高速な判定方法です。

なお、bool 型を使用する場合は stdbool.h のインクルードが必要です。math.h はこの実装では不要ですが、元のコードでは定義マクロ MAX などとともに含まれていました。