給定一個正整數
n，回傳其二進位表示中1的個數（又稱 Hamming Weight）。
Example:
Input: n = 11 (binary: 1011) Output: 3
Intuition
TIP
核心思路：n & (n - 1) 每次消除最低位的 1，消幾次就有幾個 1。
- 最直覺的方式是逐位檢查每個 bit 是否為 1
- Brian Kernighan 演算法：n & (n - 1) 會把 n 最低位的 1 變成 0，重複執行直到 n 為 0
- 後者的迴圈次數等於 1 的個數，而非固定 32 次
Approaches
1. Bit-by-Bit Check — O(32) / O(1)
- Idea: 用遮罩逐一檢查每個 bit 是否為 1，共檢查 32 次
- Time:
O(32)=O(1)- 固定 32 個 bit - Space:
O(1)
class Solution {
fun hammingWeight(n: Int): Int {
var count = 0
var num = n
for (i in 0 until 32) {
if (num and 1 == 1) {
count++
}
num = num ushr 1
}
return count
}
}⭐ 2. Brian Kernighan's Algorithm — O(k) / O(1)
- Idea: 每次執行 n & (n - 1) 消除最低位的 1，計算消除次數
- Time:
O(k)- k 是 1 的個數，最壞 O(32) - Space:
O(1)
class Solution {
fun hammingWeight(n: Int): Int {
var count = 0
var num = n
while (num != 0) {
num = num and (num - 1)
count++
}
return count
}
}Note: Integer.bitCount built-in
Kotlin/Java 內建的 Integer.bitCount 使用了高效的平行位元計數技巧：
class Solution {
fun hammingWeight(n: Int): Int {
return Integer.bitCount(n)
}
}面試中建議先講 Brian Kernighan 演算法展現理解，再提及內建函數作為實務解法。
🔑 Takeaways
- Pattern: n & (n - 1) 消除最低位的 1 是位元操作的核心技巧
- Key trick: 此技巧可延伸判斷 n 是否為 2 的冪次（n & (n - 1) == 0）