0191. Number of 1 Bits¶
题目信息¶
- 题号:
位 1 的个数
- 难度:
Easy
- 主题:
位运算、汉明重量、Brian Kernighan 算法
- 原题:
- 重点:
从固定 32 位逐位检查,推导 n & (n-1) 每轮精确删除一个最低置位
题目重述¶
给定一个 32 位无符号整数 n,返回其二进制位模式中值为 1 的位数,也称汉明重量。
答案范围为 0..32;即使最高位为 1,也按无符号 32 位模式统计。
自建示例¶
输入:n = 11,二进制为 00000000000000000000000000001011
输出:3
输入:n = 2147483648,二进制只有最高位为 1
输出:1
输入:n = 4294967295,32 位全为 1
输出:32
C++ 实现¶
#include <cstdint>
class Solution {
private:
int fixedWidthScan(std::uint32_t n) {
int count = 0;
for (int bit = 0; bit < 32; ++bit) {
count += static_cast<int>(n & 1U);
n >>= 1U;
}
return count;
}
int clearLowestSetBit(std::uint32_t n) {
int count = 0;
while (n != 0U) {
n &= n - 1U;
++count;
}
return count;
}
public:
int hammingWeight(std::uint32_t n) {
return clearLowestSetBit(n);
}
};
题解¶
固定宽度扫描是直觉基线¶
fixedWidthScan 每轮读取最低位 n & 1,把它加进计数,再将输入逻辑右移。固定执行
32 轮后,所有位置恰好检查一次,时间为 O(32)、空间为 O(1)。
这已经满足题目,但对于置位稀疏的输入,大部分轮次只是在确认某个位置为零。目标只关心 1 有多少个,不关心它们分别在哪些位置;若能一次删除一个确定的 1,就可以跳过其间任意数量 的零位。
减一如何暴露最低置位¶
设非零 n 的最低一个 1 位于位置 p。由于它是最低置位,p 以下全是 0。对
n 减一时,借位会产生固定变化:
位置
p从 1 变为 0;p以下的所有 0 变为 1;p以上不需要借位,保持不变。
例如:
n = 1011000
n - 1 = 1010111
两者按位与 = 1010000
低位新出现的 1 与 n 原有的 0 相与后仍为 0;位置 p 因 n-1 为 0 被清除;
更高位两数相同而完整保留。因此 n & (n-1) 恰好清除最低一个 1,不会影响其他置位。
循环状态与工作压缩¶
clearLowestSetBit 维护两个状态:n 是尚未清除的置位集合,count 是已经清除的
置位数。每轮执行一次 n &= n-1,剩余置位数精确减一,同时计数加一。
循环不变量可以写成:
count + n 中剩余的 1 数量 = 原输入中的 1 数量
当 n 变为 0,剩余数量为 0,所以 count 就是原汉明重量。若原输入有 w 个 1,
循环恰好执行 w 次;零输入一轮也不执行,直接得到 0。
与逐位扫描相比,新方案删除的工作是“跨过两个置位之间的所有零”。例如只有最高位为 1 时,固定扫描需要 32 轮,Kernighan 方法一次按位与就归零。
具体走读¶
对 n = 11,低位写作 1011:
轮次 更新 剩余位模式 count
1 1011 & 1010 1010 1
2 1010 & 1001 1000 2
3 1000 & 0111 0000 3
三轮分别删除原来的三个 1,零位从未单独进入循环。
为什么本题可以在 n 为 0 时停止¶
颠倒 32 位时,未处理的高位零仍决定已有位最终要左移到哪里,所以不能因输入变零提前结束; 本题只统计 1,剩余高位全为零时,它们对计数贡献必为零,提前停止完全安全。终止条件来自 目标是否依赖零位位置,而不是机械复用另一道位题的循环形式。
无符号类型与边界¶
std::uint32_t 保证输入是固定 32 位无符号模式。表达式 n - 1 只在 n != 0
时执行,不会依赖零下溢;最高位为 1 时也只是一个普通置位,按位与一次即可清除。返回计数
最大为 32,int 足够保存。
方案选择与复杂度¶
固定扫描时间为 O(32),Kernighan 方法时间为 O(w),其中 w 是置位数且
0 <= w <= 32;在固定题目位宽下两者都可视为 O(1)。两者额外空间均为 O(1),
主解选择 clearLowestSetBit,因为它直接按答案相关的置位数量工作。