LeetCode 經典位運算：Number of 1 Bits (漢明重量) 兩種高效解法

題目描述

編寫一個函數，輸入一個無符號整數，返回其二進制表示中「1」的個數（即漢明重量）。例如 32 位整數 11（二進制 00000000000000000000000000001011）應返回 3。

解法一：逐位檢查法

利用位與運算 n & 1 檢查最低位是否為 1，然後右移 n >>= 1，循環直到 n 為 0。時間複雜度 O(log n)，即二進制位數。

// Runtime: 10 ms
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            count += n & 0x1;
            n >>= 1;
        }
        return count;
    }
};

解法二：Brian Kernighan 算法 (n & (n-1))

巧妙利用 n & (n-1) 可將 n 中最低位的 1 清零。每次操作減少一個 1，循環次數等於 1 的個數，極其高效。

// Runtime: 11 ms
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            n &= (n - 1);
            ++count;
        }
        return count;
    }
};

核心原理對比

推薦使用第二種方法，尤其在 1 的個數較少時性能優勢明顯。這也是位運算技巧的經典應用。