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格式便于直接发布到技术博客平台。