Article / 文章
LeetCode 第191题：位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
题目描述
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
难度
简单
题目链接
示例
示例 1:
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。示例 2:
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。示例 3:
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。提示
- 输入必须是长度为 32 的 二进制串。
进阶
- 如果多次调用这个函数，你将如何优化你的算法？
解题思路
方法一：循环检查每一位
这是最直观的方法，我们可以通过将输入数字右移，然后检查最低位是否为1来计算位1的个数。
关键点：
- 循环32次（对应32位无符号整数的位数）
- 每次循环，检查最低位是否为1
- 将数字右移一位
时间复杂度：O(1)，因为我们只需要遍历固定的32位 空间复杂度：O(1)，只需要常数额外空间
方法二：位操作技巧
这个方法利用 n & (n-1) 可以消除 n 中最低位的 1 的特性来计算位1的个数。
关键点：
- 当 n != 0 时，重复执行 n = n & (n-1)
- 每次执行这个操作会消除 n 中最低位的 1
- 记录操作的次数，即为位1的个数
时间复杂度：O(k)，其中 k 是输入数字中 1 的个数 空间复杂度：O(1)，只需要常数额外空间
方法三：查表法（分治思想）
这个方法将32位数字分成8个4位的块，然后使用预先计算好的查找表来快速得到每个块中1的个数。
关键点：
- 预先计算0到15（对应4位二进制）中每个数字的位1个数
- 将32位数字分成8个4位的块
- 使用查表法快速计算每个块中1的个数
- 将所有块中1的个数相加得到结果
时间复杂度：O(1)，因为我们只需要进行固定次数的操作 空间复杂度：O(1)，查找表的大小是固定的（16个条目）
代码实现
C# 实现
方法一：循环检查每一位
public class Solution {
public int HammingWeight(uint n) {
int count = 0;
// 循环检查每一位
for (int i = 0; i < 32; i++) {
if ((n & 1) == 1) {
count++;
}
n >>= 1;
}
return count;
}
}方法二：位操作技巧
public class Solution {
public int HammingWeight(uint n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // 消除最低位的1
count++;
}
return count;
}
}方法三：查表法
public class Solution {
// 预计算0到15中每个数字的位1个数
private readonly int[] bitCounts = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
public int HammingWeight(uint n) {
int count = 0;
// 将32位分成8个4位的块
for (int i = 0; i < 8; i++) {
count += bitCounts[n & 0xF]; // 计算当前4位中1的个数
n >>= 4; // 右移4位，处理下一个块
}
return count;
}
}Python 实现
方法一：循环检查每一位
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
# 循环检查每一位
for i in range(32):
if n & 1:
count += 1
n >>= 1
return count方法二：位操作技巧
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n:
n &= (n - 1) # 消除最低位的1
count += 1
return count方法三：查表法
class Solution:
def __init__(self):
# 预计算0到15中每个数字的位1个数
self.bit_counts = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]
def hammingWeight(self, n: int) -> int:
count = 0
# 将32位分成8个4位的块
for i in range(8):
count += self.bit_counts[n & 0xF] # 计算当前4位中1的个数
n >>= 4 # 右移4位，处理下一个块
return countC++ 实现
方法一：循环检查每一位
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
// 循环检查每一位
for (int i = 0; i < 32; i++) {
if (n & 1) {
count++;
}
n >>= 1;
}
return count;
}
};方法二：位操作技巧
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
n &= (n - 1); // 消除最低位的1
count++;
}
return count;
}
};方法三：查表法
class Solution {
private:
// 预计算0到15中每个数字的位1个数
const int bitCounts[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
public:
int hammingWeight(uint32_t n) {
int count = 0;
// 将32位分成8个4位的块
for (int i = 0; i < 8; i++) {
count += bitCounts[n & 0xF]; // 计算当前4位中1的个数
n >>= 4; // 右移4位，处理下一个块
}
return count;
}
};性能分析
各语言实现的性能对比：
| 实现语言 | 方法 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|---|
| C# | 方法一 | 24 ms | 25.1 MB | 直观简单 |
| C# | 方法二 | 20 ms | 25.2 MB | 性能优秀，尤其当1的个数较少时 |
| C# | 方法三 | 24 ms | 25.4 MB | 性能稳定，适合多次调用 |
| Python | 方法一 | 40 ms | 14.9 MB | 直观易懂 |
| Python | 方法二 | 36 ms | 14.8 MB | 比方法一更快 |
| Python | 方法三 | 32 ms | 15.1 MB | 性能稳定 |
| C++ | 方法一 | 4 ms | 5.9 MB | 简单实现 |
| C++ | 方法二 | 0 ms | 5.8 MB | 性能最优 |
| C++ | 方法三 | 0 ms | 6.0 MB | 查表法带来的稳定性 |
补充说明
代码亮点
- 方法一简单直观，容易理解和实现
- 方法二利用位运算技巧
n & (n-1)高效消除最低位的1 - 方法三使用查表法优化，特别适合于多次调用的场景
n & (n-1) 的原理
n & (n-1) 操作可以消除 n 中最低位的 1。这是因为：
- n-1 会将 n 中最低位的 1 变为 0，并将这个位之后的所有 0 变为 1
- 将 n 与 n-1 做按位与操作，会保留除了最低位 1 及其之后的位之外的所有位，因此可以消除最低位的 1
例如：
- n = 10110100 (180)
- n-1 = 10110011 (179)
- n & (n-1) = 10110000 (176)
可以看到，最低位的 1（第3位）被消除了。
常见错误
- 没有考虑到无符号整数和有符号整数的区别，导致右移操作结果错误
- 循环次数错误，没有正确处理32位整数
- 在方法二中，如果n为0时没有正确处理
- 在查表法中，没有正确分割32位整数