Description
給定一個正整數
n，回傳其二進位表示中1的個數（又稱 Hamming Weight）。
Example:
Input: n = 11 (binary: 1011) Output: 3
Intuition#
核心思路：n & (n - 1) 每次消除最低位的 1，消幾次就有幾個 1。
- 最直覺的方式是逐位檢查每個 bit 是否為 1
- Brian Kernighan 演算法：n & (n - 1) 會把 n 最低位的 1 變成 0，重複執行直到 n 為 0
- 後者的迴圈次數等於 1 的個數，而非固定 32 次
Approaches#
1: 逐位檢查#
- 概念: 用遮罩逐一檢查每個 bit 是否為 1，共檢查 32 次
- 時間複雜度:
O(32)=O(1)- 固定 32 個 bit - 空間複雜度:
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 演算法#
- 概念: 每次執行 n & (n - 1) 消除最低位的 1，計算消除次數
- 時間複雜度:
O(k)- k 是 1 的個數，最壞 O(32) - 空間複雜度:
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
}
}補充：Integer.bitCount 內建函數
Kotlin/Java 內建的 Integer.bitCount 使用了高效的平行位元計數技巧：
class Solution {
fun hammingWeight(n: Int): Int {
return Integer.bitCount(n)
}
}面試中建議先講 Brian Kernighan 演算法展現理解，再提及內建函數作為實務解法。
🔑 Takeaways#
- Pattern: n & (n - 1) 消除最低位的 1 是位元操作的核心技巧
- 關鍵技巧: 此技巧可延伸判斷 n 是否為 2 的冪次（n & (n - 1) == 0）