C語言位運算技巧：判斷整數是否為 2 的 n 次方

經典位運算面試題：O(1) 判斷 2 的冪次

判斷一個整數是否為 2 的冪次 (1, 2, 4, 8, 16...)，核心技巧：n & (n - 1) == 0（前提 n > 0）。

核心邏輯

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

bool isPowerOfTwo(int n) {
    // 必須大於 0，且二進制只有一個 1
    return n > 0 && (n & (n - 1)) == 0;
}

int main() {
    int test[] = {0, 1, 2, 3, 4, 5, 8, 16, 31, 32, 64, 100, -2, -8};
    int n = sizeof(test) / sizeof(test[0]);
    
    for (int i = 0; i < n; i++) {
        printf("%4d : %s\n", test[i], isPowerOfTwo(test[i]) ? "是 2 的冪次" : "否");
    }
    return 0;
}

原理圖解

2 的冪次二進制特徵：只有最高位為 1，其餘全 0
8  = 00001000
7  = 00000111  (8-1)
8&7 = 00000000  → 結果為 0

非 2 的冪次：
6  = 00000110
5  = 00000101  (6-1)
6&5 = 00000100  → 結果非 0

特殊情況：
0  = 00000000  → 0&(-1)=0 但 0 不是 2 的冪次，需額外判斷 n>0
負數：最高位為 1，減 1 後不會只剩單一 1，自動被排除

變體與延伸

1. 找出小於等於 n 的最大 2 的冪次

int highestPowerOfTwo(int n) {
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n - (n >> 1);
    // 將最高位 1 以下全變 1，再取中間值
}

2. 找出大於 n 的最小 2 的冪次

int nextPowerOfTwo(int n) {
    if (n <= 1) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

3. 計算 log2 (整數版)

int ilog2(int n) {
    int log = 0;
    while (n >>= 1) log++;
    return log;
}
// 或用內建：__builtin_clz / 31 - __builtin_clz(n)

硬體指令與編譯器內建

常見錯誤

• 忘記檢查 n > 0，導致 0 被誤判為 true
• 對有號整數右移假設邏輯位移（負數算術位移會填 1）
• 使用 log2() 浮點運算再比較，精度問題導致誤判

應用場景

• 記憶體對齊：分配器常將大小調整為 2 的冪次
• 位圖/位集合：索引計算、快速模運算 x & (size-1)
• 資料結構：Segment Tree、Fenwick Tree 節點數
• 網路：子網路掩碼、CIDR 區塊大小
• 圖形學：材質尺寸、Mipmap 層級