C 語言位運算技巧：判斷 2 的 n 次方

C 語言位運算技巧：判斷 2 的 n 次方

2 的 n 次方在二進制中有且僅有一個 1（如 2=10₂, 4=100₂, 8=1000₂）。利用 n & (n-1) 清除最低位 1 的特性，可 O(1) 判斷。

實作程式碼

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

bool isPowerOfTwo(int n) {
    if (n <= 0) return false; // 0、負數不是
    return (n & (n - 1)) == 0;
}

int main() {
    printf("%d -> %s\n", 2,  isPowerOfTwo(2)  ? "是" : "否");  // 是
    printf("%d -> %s\n", 3,  isPowerOfTwo(3)  ? "是" : "否");  // 否
    printf("%d -> %s\n", 4,  isPowerOfTwo(4)  ? "是" : "否");  // 是
    printf("%d -> %s\n", 16, isPowerOfTwo(16) ? "是" : "否");  // 是
    printf("%d -> %s\n", 0,  isPowerOfTwo(0)  ? "是" : "否");  // 否
    printf("%d -> %s\n", -8, isPowerOfTwo(-8) ? "是" : "否");  // 否
    return 0;
}

原理圖解

n      = 8  = 0000 1000
n - 1  = 7  = 0000 0111
n & (n-1) = 0  → 僅一個 1，是 2 的 n 次方

n      = 6  = 0000 0110
n - 1  = 5  = 0000 0101
n & (n-1) = 4 ≠ 0 → 多個 1，不是

邊界情況處理

• n ≤ 0：直接返回 false（0 不是，負數補碼有多個 1）。
• n = 1：1 & 0 == 0 → true（2⁰=1）。
• 大數：對 32/64 位整數均有效。

應用場景

• 記憶體對齊檢查（如分配器要求 size 為 2 的冪）。
• 位圖操作、快速取模（x % n == x & (n-1) 當 n 為 2 的冪）。
• 演算法優化（如 FFT 長度、環形緩衝區大小）。