位運算技巧：快速判斷 2 的冪次與計算 32 位整數中 1 的個數

核心結論

對於無符號整數 x：

• 判斷是否為 2 的冪次：(x & (x - 1)) == 0 且 x != 0。
• 計算二進制中 1 的個數 (Hamming Weight)：反覆執行 x &= (x - 1)，每次消除最低位的 1，循環次數即為 1 的個數。

原理圖解

為什麼 x & (x-1) 能消除最低位 1？

x       = xxxx 1 0000  (最低位 1 後面全 0)
x - 1   = xxxx 0 1111  (借位：最低位 1 變 0，後面全變 1)
x & (x-1)= xxxx 0 0000  (最低位 1 被清零，高位不變)

• 若 x 只有 **一個 1**（即 2 的冪次），則 x & (x-1) == 0。
• 若 x 有 **多個 1**，結果非零，且最低位 1 被清除。

代碼實現

1. 判斷 2 的冪次（巨集/函數）

#define IS_POWER_OF_TWO(x)  ((x) != 0 && ((x) & ((x) - 1)) == 0)

// 或函數版
int isPowerOfTwo(unsigned int x) {
    return x && !(x & (x - 1));
}

// 測試
int main() {
    unsigned int m = 512;  // 2^9
    printf("%d\n", isPowerOfTwo(m));  // 1 (真)
    m = 513;
    printf("%d\n", isPowerOfTwo(m));  // 0 (假)
    return 0;
}

2. 計算 1 的個數 (Brian Kernighan 算法)

int countOnes(unsigned int x) {
    int count = 0;
    while (x) {
        x &= (x - 1);  // 清除最低位 1
        count++;
    }
    return count;
}

// 時間複雜度：O(k)，k 為 1 的個數，最壞 O(32) = O(1)

對比：其他常見計數方法

C++20 / GCC/Clang 內建函數

// 編譯器內建，通常優化為單條指令 (popcnt)
int cnt = __builtin_popcount(x);        // unsigned int
int cnt = __builtin_popcountll(x);      // unsigned long long

// C++20 標準庫
#include 
int cnt = std::popcount(x);

應用場景

• **位圖/集合操作**：快速判斷集合大小、檢查單一元素。
• **記憶體分配器**：Buddy System 判斷塊大小是否為 2 的冪次。
• **網路協議**：校驗和、掩碼長度計算。
• **圖形學**：Morton Code (Z-order)、稀疏集合遍歷。
• **面試必考**：LeetCode 191 "Number of 1 Bits"、231 "Power of Two"。

擴展：隔離/提取最低位 1

x & -x        // 只保留最低位 1 (利用二進制補碼特性)
x | (x - 1)   // 最低位 1 及其右側全置 1

結合 x & (x-1) 可構建更多位操作技巧（如求下一個排列組合）。

1. 上一篇文章： 最大公約數與最小公倍數：輾轉相除法、輾轉相減法 C 語言實現
2. 下一篇文章： STL set 容器深度解析：自定義類型比較規則與去重陷阱

關於C

C語言實現帶頭節點單鏈表：創建、增刪查、歸併排序完整代碼

單鏈表是數據結構教學與工程實踐的基石。本文提供一個模塊化、可

C 語言判斷五位數回文數：數學分解法與邊界檢查

問題定義 輸入一個五位整數（10000~99999），判斷是

C語言柔性數組（結構體尾部零長度數組）實現變長結構體

C99 標準引入**柔性數組成員** (Flexible A

C語言實現推箱子小遊戲完整源碼解析

基於 8×8 字符界面的推箱子第一關，含移動、推箱、勝負判定