C語言位運算經典技巧：統計 1 的個數與判斷 2 的冪次

位運算神技：`x & (x-1)` 消除最低位 1，構建 O(1) 平均/最壞 O(k) 算法

位運算是 C 語言贴近硬件的核心優勢。本文解析兩個經典面試/工程高頻算法：**統計整數二進制中 1 的個數 (Hamming Weight)** 與 **判斷是否為 2 的冪次**，核心均利用 `x & (x-1)` 這一「消除最低位 1」的神奇特性。

核心特性：`x & (x-1)` 將 x 二進制中最右側的 1 變為 0

x       = 10011100001111 (9999)
x - 1   = 10011100001110
x & (x-1) = 10011100001110  ← 最低位 1 (第0位) 變 0

再執行一次：
x       = 10011100001110
x - 1   = 10011100001101
x & (x-1) = 10011100001100  ← 原第1位 1 變 0
...
循環 8 次後 x 變 0 → 共 8 個 1

原理：減 1 會將最低位 1 變 0，並將其右側所有 0 變 1。與原數 `&` 運算，最低位 1 變 0，右側全 0，高位不變。

算法一：統計 1 的個數 (Brian Kernighan 算法)

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

/* 測試 */
count_ones(9999) → 8  // 10011100001111 有 8 個 1
count_ones(0) → 0
count_ones(-1) → 32 (32位系統，全 1)

複雜度：O(k)，k 為 1 的個數。**最壞 O(32/64) = O(1)**。比遍歷 32 位 (O(32)) 更快，尤其稀疏 1 時極其高效。

算法二：判斷 2 的冪次 (Power of Two)

數學特徵：2 的冪次二進制**有且僅有最高位為 1，其餘全 0**。

2^0 = 1     = 0001
2^1 = 2     = 0010
2^2 = 4     = 0100
2^3 = 8     = 1000
...
x = 2^n → x & (x-1) = 0  (最高位 1 被消除，其餘本來就 0)
x ≠ 2^n → x & (x-1) ≠ 0 (至少剩一個 1)

實現代碼

int is_power_of_two(int x) {
    // 必須 x > 0 排除 0 和負數 (負數最高位 1，但非 2 的冪)
    return (x > 0) && ((x & (x - 1)) == 0);
}

/* 運算符優先級陷阱 */
if (x & (x-1) == 0)  // ❌ 錯誤：== 優先級高於 &，解析為 x & ((x-1)==0)
if ((x & (x-1)) == 0) // ✅ 正確：顯式括號

測試用例

is_power_of_two(8)   → 1 (1000)
is_power_of_two(7)   → 0 (0111)
is_power_of_two(0)   → 0 (特殊處理)
is_power_of_two(-16) → 0 (負數非 2 的冪)
is_power_of_two(1)   → 1 (2^0)

擴展應用場景

現代優化：內建函數 / 硬件指令

GCC/Clang/MSVC 提供編譯器內建函數，直接映射硬件指令 (`POPCNT` / `LZCNT` / `TZCNT`)，**極致性能**：

// GCC/Clang
int count = __builtin_popcount(x);        // 32位
int count = __builtin_popcountll(x);      // 64位

// MSVC (intrin.h)
#include <intrin.h>
int count = __popcnt(x);                  // 需 CPU 支持 POPCNT

// C++20 標準庫
#include <bit>
int count = std::popcount(x);             // 類型安全、跨平台

**工程建議**：優先使用 `std::popcount` / `__builtin_popcount`；手寫 `x&(x-1)` 僅用於教學、面試、或極度受限環境 (無標準庫、古老編譯器)。

總結

1. `x & (x-1)` 消除最低位 1 是位運算領域的「核武器」，衍生出統計 1、判斷 2 的冪、隔離最低位 1 等經典算法。
2. 統計 1 的個數：循環消除 1 計數，複雜度與 1 的個數成正比。
3. 判斷 2 的冪：`x > 0 && (x & (x-1)) == 0`，注意優先級陷阱與邊界 0。
4. 生產代碼優先用編譯器內建/標準庫，手寫版本作為理解底層原理的教具。

1. 上一篇文章： C語言 swap 交換函數五種寫法深度對比：值傳遞 vs 指針 vs 數組退化
2. 下一篇文章： TSDK.H：C語言通用開發工具包頭文件詳解 (字符串、文件、隨機數、時間、端序)

關於C語言

C# 開發 WPF/Silverlight 動畫與遊戲系列教程（六）完美移動（二）—— 遺留問題與解決方向

三大待解決問題 停止狀態切換：主角抵達目的地後應切換為

C 語言條件語句詳解：if、if-else、switch 三大控制結構

C 語言條件語句詳解：if、if-else、switch 三

C# 擴展方法進階技巧：改良 ScottGu In 擴展方法 (上)

ScottGu 原版 In 擴展需顯式建立陣列：1.In(n

C# 設計模式：行為模式 - 責任鏈模式 (4) - 實作細節與鏈結構變體

核心說明 責任鏈模式不負責建立鏈結構，鏈的組裝由系統其他部