Number of 1 Bits

解題說明

題目描述：計算一個無號 32 位元整數的二進位表示中有幾個 '1'（漢明重量）。

解題思路：Brian Kernighan 演算法：n & (n-1) 會消除 n 最右邊的 1 位元。反覆執行此操作並計數，直到 n 為 0。每次操作消除一個 1 位元，因此迴圈次數等於 1 的個數，比逐位檢查更高效。

時間複雜度：O(k)，k 為 1 的個數（最多 32）— 比逐位掃描更快。

空間複雜度：O(1) — 只用一個計數器。

1. Set count = 0
2. While n != 0:
   a. n = n AND (n - 1)  // clears rightmost set bit
   b. count++
3. Return count

逐位移位 O(32)：用 n & 1 檢查各位，再 n >>= 1 — 總是 32 次迭代。

內建 __builtin_popcount(n)：現代硬體的單一 CPU 指令 — 競賽代碼中理想。

查找表：預計算 8 或 16 位元區塊的 popcount，再組合 — 快速但需額外空間。