0191. Number of 1 Bits
======================
题目信息
--------
:题号: 0191. 位 1 的个数
:难度: Easy
:主题: 位运算、汉明重量、Brian Kernighan 算法
:原题: `LeetCode 0191 `_
:重点: 从固定 32 位逐位检查,推导 n & (n-1) 每轮精确删除一个最低置位
题目重述
--------
给定一个 32 位无符号整数 ``n``,返回其二进制位模式中值为 1 的位数,也称汉明重量。
答案范围为 ``0..32``;即使最高位为 1,也按无符号 32 位模式统计。
自建示例
--------
.. code-block:: text
输入:n = 11,二进制为 00000000000000000000000000001011
输出:3
.. code-block:: text
输入:n = 2147483648,二进制只有最高位为 1
输出:1
.. code-block:: text
输入:n = 4294967295,32 位全为 1
输出:32
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
int fixedWidthScan(std::uint32_t n) {
int count = 0;
for (int bit = 0; bit < 32; ++bit) {
count += static_cast(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`` 以上不需要借位,保持不变。
例如:
.. code-block:: text
n = 1011000
n - 1 = 1010111
两者按位与 = 1010000
低位新出现的 1 与 ``n`` 原有的 0 相与后仍为 0;位置 ``p`` 因 ``n-1`` 为 0 被清除;
更高位两数相同而完整保留。因此 ``n & (n-1)`` **恰好清除最低一个 1**,不会影响其他置位。
循环状态与工作压缩
~~~~~~~~~~~~~~~~~~
``clearLowestSetBit`` 维护两个状态:``n`` 是尚未清除的置位集合,``count`` 是已经清除的
置位数。每轮执行一次 ``n &= n-1``,剩余置位数精确减一,同时计数加一。
循环不变量可以写成:
.. code-block:: text
count + n 中剩余的 1 数量 = 原输入中的 1 数量
当 ``n`` 变为 0,剩余数量为 0,所以 ``count`` 就是原汉明重量。若原输入有 ``w`` 个 1,
循环恰好执行 ``w`` 次;零输入一轮也不执行,直接得到 0。
与逐位扫描相比,新方案删除的工作是“跨过两个置位之间的所有零”。例如只有最高位为 1
时,固定扫描需要 32 轮,Kernighan 方法一次按位与就归零。
具体走读
~~~~~~~~
对 ``n = 11``,低位写作 ``1011``:
.. code-block:: text
轮次 更新 剩余位模式 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``,因为它直接按答案相关的置位数量工作。