LeetCode 剑指 Offer 15. 二进制中1的个数
题目描述
题意分析
统计输入的 32 位二进制表示中有多少个 1。Java 用有符号
int保存这 32 位，Go 使用uint32；最高位是否被解释为符号位，不影响它是否应被计数。
解法：Brian Kernighan 位运算
核心思路
[!blue]
对非零的
n，找到它最低的一位 1，这一位右侧必然全是 0。执行n - 1时，需要从这个 1 借位：它变成 0，右侧所有 0 变成 1，更高位保持不变。再计算
n & (n - 1)，更高位原样保留，最低的 1 因为与 0 相与而被清除，右侧各位则因为原先是 0 仍然为 0。因此，这一步恰好删掉一个 1，不改变其余的 1。每清除一次就将
count加一，始终保持“已清除的个数加上剩余 1 的个数”等于原答案。位串归零时已经没有遗漏，count就是结果；每轮至少减少一个 1，最多执行 32 次。Java 的减法和按位与都作用于固定的 32 位补码，即使输入为负数，这个清除规则仍成立。因此循环条件必须是
n != 0，不能要求n > 0。输入为 0 时不进入循环，直接得到 0。
解题步骤
- 计数从零开始。
- 位串非零时清除最低的一并计数。
- 位串归零后返回。
代码实现
public class Solution {
public int hammingWeight(int n) {
int count = 0;
// 按位串判非零，不能用正负判断是否仍有一
while (n != 0) {
// 每轮恰好清除最低的一，计数加一即可
n &= n - 1;
count++;
}
return count;
}
}
func hammingWeight(num uint32) int {
count := 0
// 按位串判非零，不能用正负判断是否仍有一
for num != 0 {
// 每轮恰好清除最低的一，计数加一即可
num &= num - 1
count++
}
return count
}
复杂度分析
- 时间复杂度：$O(b+1)$，其中 $b$ 为 1 的数量，循环恰好执行 $b$ 次；固定 32 位输入下最坏为 $O(1)$。
- 空间复杂度：$O(1)$，一个计数器。
关键点总结
[!green]
- 处理的是位串，符号解释不改变应统计的位。
- 每轮清除一个一，不是简单右移一位。
易错点总结
[!yellow]
- 循环条件大于零会漏掉 Java 最高位为一的输入。
- 先取绝对值改变原位串，统计对象已不同。
- 把最低一的位置当作本次应增加的数量，会多算。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 338. 比特位计数 | 简单 | 对0到n批量求位数时，可利用更小数的计数结果复用状态，而不是逐个重新统计。 |
| 461. 汉明距离 | 简单 | 先异或得到不同位，再调用位计数即得到汉明距离。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！