Number of 1 Bits (位元 1 的個數) 🟢 Easy¶

📌 LeetCode #191 — 題目連結 | NeetCode 解說

1. 🧐 Problem Dissection (釐清問題)¶

這是一個非常經典的位運算問題，也叫 Hamming Weight。給定一個無符號整數 n，請計算它的二進制表示中有多少個 1。

Input: n = 00000000000000000000000000001011 (11)
Output: 3
Input: n = 11111111111111111111111111111101
Output: 31

2. 🐢 Brute Force Approach (暴力解)¶

循環 32 次，每次檢查最低位是否為 1 (n & 1)，然後右移一位 (n >>= 1)。

Time: \(O(32) = O(1)\)。

Algorithm:

int res = 0;
while (n) {
    res += n & 1;
    n >>= 1;
}
return res;

3. 💡 The "Aha!" Moment (優化)¶

Brian Kernighan's Algorithm: 這是一個稍微更快的算法，它的循環次數等於 1 的個數，而不是固定的 32 次。核心操作是 n = n & (n - 1)。這個操作會 消除 n 的二進制表示中最低位的那個 1。

Example: n = 10100 (20)
n - 1 = 10011 (19)
n & (n - 1) = 10100 & 10011 = 10000 (eliminate lowest 1)
Next: 10000 & 01111 = 00000 (eliminate lowest 1)
Total 2 ops.

🎬 Visualization (演算法視覺化)¶

⤢ 全螢幕開啟視覺化

4. 💻 Implementation (程式碼)¶

Approach: Brian Kernighan's Algorithm¶

#include <cstdint>

using namespace std;

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

Python Reference¶

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            n &= (n - 1)
            res += 1
        return res

5. 📝 Detailed Code Comments (詳細註解)¶

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        // 只要 n 不為 0，就表示還有 1 存在
        while (n != 0) {
            // Brian Kernighan's algorithm
            // n & (n - 1) 的作用是將 n 的二進制中最右邊的 1 變成 0
            // 例如：1100 -> 1000
            n = n & (n - 1);

            // 每消除一個 1，計數器加 1
            count++;
        }
        return count;
    }
};

6. 📊 Rigorous Complexity Analysis (複雜度分析)¶

Time Complexity: \(O(k)\), where \(k\) is the number of set bits.
- In worst case \(k=32\), so \(O(1)\).
Space Complexity: \(O(1)\).

7. 💼 Interview Tips (面試技巧)¶

🎯 Follow-up 問題¶

面試官可能會問的延伸問題：

你會如何處理更大的輸入？
有沒有更好的空間複雜度？

🚩 常見錯誤 (Red Flags)¶

避免這些會讓面試官扣分的錯誤：

⚠️ 沒有考慮邊界條件
⚠️ 未討論複雜度

✨ 加分項 (Bonus Points)¶

這些會讓你脫穎而出：

💎 主動討論 trade-offs
💎 提供多種解法比較