LeetCode 191 位1的個數：Brian Kernighan 算法 n&(n-1) 消除最低位1

問題描述

編寫一個函數，輸入一個無符號整數，返回其二進制表示中 '1' 的個數（漢明重量）。例如 11 (二進制 1011) 返回 3。

解法一：逐位檢查 (O(32))

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; ++i) {
        if ((n & (1 << i)) != 0) count++;
    }
    return count;
}

解法二：Brian Kernighan 算法 —— 消除最低位 1 (O(1的個數))

核心性質

n & (n - 1) 會將 n 的二進制表示中**最低位的 1 變為 0**

例如：n = 101100，n-1 = 101011，n & (n-1) = 101000（最低位 1 消失）。

算法邏輯

循環執行 n = n & (n - 1) 並計數，直到 n == 0。循環次數恰好等於 1 的個數。

完整代碼

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1); // 消除最低位 1
        count++;
    }
    return count;
}

複雜度分析

• 時間：O(k)，k 為 1 的個數。最壞 O(32)，平均遠小於 32。
• 空間：O(1)。

硬件指令優化（補充）

現代 CPU 提供 POPCNT 指令，C++ 可用 __builtin_popcount(n) (GCC/Clang) 或 std::popcount (C++20) 直接調用，單指令完成，極致快速。

總結

Brian Kernighan 算法是位運算經典技巧，利用 n & (n-1) 消除最低位 1，僅遍歷 1 的位數。不僅解決漢明重量，還是「判斷 2 的冪次、遍歷子集」等問題的基石。