LeetCode如何輸出某個整數二進制中1的個數

# LeetCode如何輸出某個整數二進制中1的個數

在編程面試和算法競賽中，計算一個整數的二進制表示中1的個數（也稱為"漢明重量"或"popcount"）是經典問題。本文將深入探討該問題的多種解法，分析其時間復雜度，并提供LeetCode相關題目的實戰代碼示例。

## 問題定義

給定一個32位有符號/無符號整數，統計其二進制表示中`1`的個數。例如：
- 輸入：`11`（二進制 `1011`）
- 輸出：`3`

## 方法一：逐位檢查法

### 基本思路
通過循環右移數字并檢查最低位是否為1。

```python
def hammingWeight(n: int) -> int:
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

復雜度分析

• 時間復雜度：O(k)，k為數字的二進制位數（固定32位時為O(1)）
• 空間復雜度：O(1)

注意事項

• 對于負數，右移操作會補符號位（算術右移），可能導致無限循環
• 解決方案：改用無符號右移（Python需特殊處理）

方法二：Brian Kernighan算法

優化原理

利用 n & (n-1) 可以消除最右邊的1的特性。

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

復雜度分析

• 時間復雜度：O(m)，m為1的個數
• 空間復雜度：O(1)

優勢

• 最佳情況下只需執行1次（n=0時）
• 最壞情況仍為O(32)

方法三：查表法

預計算思想

預先計算0-255所有數字的1的個數，然后分段查詢。

# 預先生成8位查表
table = [0] * 256
for i in range(256):
    table[i] = (i & 1) + table[i >> 1]

def hammingWeight(n):
    return (table[n & 0xff] + 
            table[(n >> 8) & 0xff] + 
            table[(n >> 16) & 0xff] + 
            table[n >> 24])

復雜度分析

• 時間復雜度：O(1)
• 空間復雜度：O(256)

適用場景

• 需要大量重復計算時
• 嵌入式系統等對性能要求極高的場景

方法四：分治法（SWAR算法）

并行計算技巧

通過位運算并行計算多個位的1的個數。

def hammingWeight(n):
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555)
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F)
    n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF)
    n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF)
    return n

復雜度分析

• 時間復雜度：O(1) 僅需5次運算
• 空間復雜度：O(1)

性能對比

LeetCode實戰

題目191. 位1的個數

直接應用上述方法：

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

相關題目

1. 338. 比特位計數 - 計算0到n每個數字的1的個數
2. 461. 漢明距離 - 兩個數字二進制位不同的位置數目
3. 477. 漢明距離總和 - 數組中所有數對的漢明距離之和

語言特性實現

Python內置方法

n.bit_count()  # Python 3.10+
bin(n).count('1')

Java實現

public int hammingWeight(int n) {
    return Integer.bitCount(n); // 內部使用SWAR算法
}

總結

1. 面試推薦使用Brian Kernighan算法
2. 工程實踐可直接使用語言內置方法
3. 特殊場景考慮查表法或SWAR算法
4. 注意處理負數時的邊界情況

掌握二進制位操作技巧對優化算法性能具有重要意義，這類思想還可應用于布隆過濾器、位圖等數據結構實現。 “`

注：本文實際約1100字，包含代碼示例、復雜度分析和不同場景的解決方案選擇建議。Markdown格式便于直接發布到技術博客平臺。