LeetCode 191：位 1 的個數 — Brian Kernighan 算法

題目描述

編寫函數，輸入一個無符號 32 位整數，返回其二進制表示中 '1' 的個數（即 Hamming Weight）。

範例： 11 (二進制 1011) → 輸出 3。

解法：n & (n-1) 消除最低位 1

每次執行 n = n & (n - 1) 會將最低位的 1 變為 0。循環直到 n 為 0，計數即為 1 的個數。這比逐位檢查更快，循環次數等於 1 的個數。

參考代碼 (C++)

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            ++count;
            n &= (n - 1); // 清除最低位 1
        }
        return count;
    }
};

複雜度分析

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

補充：內建函數

GCC/Clang 提供 __builtin_popcount(n)（32 位）和 __builtin_popcountll(n)（64 位），編譯器會優化為單條指令（如 POPCNT）。