LeetCode 191. 位1的个数
题目描述
题意分析
统计给定整数的二进制表示中有多少个位为
1，返回这个数量，也称为汉明重量。不是统计十进制数位，也不需要保留这些1原来的位置。下面按照 32 位整数处理。Java 使用
int保存位模式，Go 使用uint32；要数的是全部 32 位中的1，不应让 Java 的正负号改变计数方式。
解法：不断消去最低位 1
核心思路
[!blue]
对非零整数，定位它最右侧的
1。这一位右侧全为零，减去一时必须向这个1借位：它由一变成零，右侧的零全部变成一，更高的位不变。再计算
n & (n - 1)：更高位保持原样；这个最低位1与零相与后被清除；更低位原本就是零，与任何位相与仍为零。因此这次运算恰好消去一个1，其他1不受影响。每清除一次就将计数加一。处理若干轮后，“已经清除的数量 + 当前剩余的
1的数量”始终等于原答案；当n变成零时没有剩余，计数器就是结果。这样循环次数只取决于1的数量，无需逐个检查为零的位。条件使用
n != 0，而不是n > 0。Java 的最高位为一时会把位模式解释成负数，但这些位仍然需要计数；补码减法和按位与同样能逐次清除它们。
解题步骤
- 初始化
count = 0。- 当
n != 0时，用n &= n - 1清除最低位的一个1。- 每清除一次，将
count加一，继续处理剩余位。n变为零后返回count；输入本身为零时自然返回零。
代码实现
class Solution {
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
// 每次只清掉最低的一位一，循环次数就是置位数量。
n &= n - 1;
count++;
}
return count;
}
}
func hammingWeight(n uint32) int {
count := 0
for n != 0 {
// 每次只清掉最低的一位一，循环次数就是置位数量。
n &= n - 1
count++
}
return count
}
复杂度分析
- 时间复杂度：$O(k)$，其中 $k$ 是二进制中
1的数量，每轮恰好清除一个。对于固定 32 位整数，最多循环 32 次，也可以记为 $O(1)$。- 空间复杂度：$O(1)$，只保存计数器并更新整数本身。
关键点总结
[!green]
- 减一改变最低位
1及其右侧位，按位与则只消去这个1。- 每轮恰好删除一个待计数对象，所以循环次数直接等于答案。
- 按位计数处理的是位模式，有符号类型的最高位也必须统计。
易错点总结
[!yellow]
- 使用
n > 0会直接跳过最高位为一的 Java 位模式，应判断是否为零。- 只计算
n - 1而没有按位与，并不保证只减少一个1，甚至可能增加低位的一。n & -n会提取最低位的一，不能替代本题所需的“清除”操作。- 如果选择逐位检查的写法，必须覆盖全部 32 位；本方法无需手动维护位下标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 338. 比特位计数 | 简单 | 对0到n批量求位数时，可利用更小数的计数结果复用状态，而不是逐个重新统计。 |
| 461. 汉明距离 | 简单 | 先异或得到不同位，再调用位计数即得到汉明距离。 |
| 137. 只出现一次的数字 II | 中等 | 按位统计重复模式并重建答案；本题统计一个整数的置位数，该题各位计数对三取模。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！