LeetCode 191 Number of 1 Bits：漢明重量 (位運算技巧)

問題描述

輸入無符號 32 位整數，返回其二進制表示中 1 的個數（漢明重量）。

方法一：逐位檢查

迴圈 32 次，(n >> i) & 1 或 n & (1u << i) 累加。

方法二：Brian Kernighan 算法（推薦）

n & (n-1) 會清除最低位的 1。重複直到 n == 0，迴圈次數即為 1 的個數。

int hammingWeight(uint32_t n) {
    int cnt = 0;
    while (n) {
        n &= n - 1;
        ++cnt;
    }
    return cnt;
}

複雜度分析

• 方法一：固定 32 次迴圈，O(1)。
• 方法二：迴圈次數 = 1 的個數，最好 O(1)，最壞 O(32)，平均更快。

總結

位運算經典技巧：n & (n-1) 清除最低位 1。此題為漢明重量計算，廣泛應用於錯誤校正、資訊檢索、密碼學等領域。C++20 提供 std::popcount 內建函數。