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``,因为它直接按答案相关的置位数量工作。