LeetCode 剑指 Offer 15. 二进制中1的个数

约 5 分钟
文章信息 11 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 微软 美团 虾皮 携程 剑指 Offer 剑指 Offer（第 2 版）
标签
位运算
目录

题目描述

✅ 剑指 Offer 15. 二进制中1的个数

image-20241107205002011

题意分析

给一个 32 位的无符号整数，统计它的二进制表示中有多少位是 1，也就是汉明重量。输入是一个固定宽度的位串，输出是一个 0 到 32 之间的整数。

「无符号」这三个字是整道题真正的考点所在，而不是统计本身。Go 的函数签名直接给的是 uint32，语义没有歧义；Java 没有无符号整型，判题传进来的是 int，同一串二进制位在 Java 里会被解释成负数——比如 11111111111111111111111111111101 作为无符号数是 4294967293，作为 int 是 -3。题目要数的是「位」，与这个解释无关，所以实现必须做到对位的处理不受符号影响。

位宽固定为 32 是另一个信号：任何逐位处理的循环都被天然限制在 32 轮以内，与输入大小无关，所以复杂度是常数级的，讨论「更快的算法」只能在常数上做文章（比如把循环轮数从 32 降到 1 的个数）。

边界要盯住三处：输入为 0 时答案是 0，循环一次都不该进；输入为 -1（32 位全 1）时答案是 32，这是最容易在符号扩展上出问题的用例；输入为 Integer.MIN_VALUE（只有最高位是 1）时答案是 1，它同时是「最高位为 1」和「其余位全 0」的组合，最能暴露右移方式的错误。

解法：Brian Kernighan 位运算

核心思路

不必逐位右移。Brian Kernighan 算法利用一个更直接的性质：x & (x - 1) 会清除 x 二进制表示中最低位的 1。

原因可以从最低位的 1 观察。若

\[x = \text{prefix}\ 1\ 00\ldots00\]

那么减一后，这个最低位的 1 变成 0，它右侧的 0 全变成 1：

\[x - 1 = \text{prefix}\ 0\ 11\ldots11\]

两者按位与后，前缀不变，最低位的 1 及其右侧全部归零，恰好少一个 1。不断执行 x &= x - 1，执行多少次就清除了多少个 1；当 x 变成 0 时，计数就是答案。

循环不变量是：count 等于已经清除的 1 的数量，x 保留原位串中尚未清除的 1。 每轮只清除一个 1，因此不变量成立；循环结束时没有剩余的 1，count 即为汉明重量。

Java 的参数虽然是有符号 int，但位运算面对的仍是固定 32 位补码，正负只影响数值解释，不改变位串。Java 的 int 减法按 32 位回绕，所以该恒等式对负数同样成立。例如 -1 的补码是 32 个 1，每轮清除一个，最终正好执行 32 次；Integer.MIN_VALUE 只有最高位是 1，n - 1 回绕为 Integer.MAX_VALUE，两者按位与直接得到 0。Go 参数是 uint32，语义更加直接。

解题步骤

  1. 初始化计数器 count = 0。
  2. 当 n != 0 时，用 n &= n - 1 清除当前最低位的 1。
  3. 每成功清除一次就令 count++。
  4. n 归零后返回 count。

以 n = 12 为例，二进制变化如下：

  • 1100 & 1011 = 1000，清除最低位的 1，count = 1；
  • 1000 & 0111 = 0000，再清除一个 1，count = 2。

因而 12 的二进制中有 2 个 1。输入为 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(k)$，其中 k 是二进制位中 1 的个数；每轮恰好清除一个 1。对固定 32 位整数，k 至多为 32，因此最坏情况也可记为 $O(1)$。
  • 空间复杂度：$O(1)$，只使用一个计数器并原地更新参数。

关键点总结

  • n & (n - 1) 的作用必须会推导：减一让最低位的 1 变 0，并把它右侧的 0 变 1，再按位与就只清掉这个 1。
  • 循环次数由 1 的数量决定，而不是由最高位的位置决定；位串稀疏时比逐位右移更省循环。
  • Java 的负数使用 32 位补码，位运算和减法回绕都在同一固定宽度内完成，所以公式不区分正负。
  • 对固定 32 位输入，最坏只循环 32 次；写成 $O(k)$ 能体现算法特性，补充最坏为 $O(1)$ 才完整。
  • 工程代码可直接使用 Integer.bitCount 或 bits.OnesCount32，但面试手写时应展示清除最低位 1 的原理。

易错点总结

  • 循环条件写成 n > 0：Java 中最高位为 1 的位串会被解释成负数，循环一次也不执行；必须判断 n != 0。
  • 担心负数而先取绝对值：绝对值会改变原始位串，而且 Math.abs(Integer.MIN_VALUE) 仍是负数，语义和结果都错误。
  • 忘记最低位清除的是 1 而不是一位：n &= n - 1 可能跨过多个末尾 0，但每轮只减少一个 1，所以计数仍只加一。
  • 省略括号后照搬到不同语言：位运算与减法的优先级并不值得死记，讲解时统一写 n & (n - 1)；代码用复合赋值 n &= n - 1 最清晰。
  • 在 n == 0 时仍计算 n - 1：Go 的无符号数会下溢为全 1；把清除操作放在 n != 0 的循环内即可避免。

相似题目

题目 难度 考察点
191. 位1的个数 简单 与本题同题，可用来对照 n & (n-1) 与逐位右移两种写法的循环次数差异
338. 比特位计数 简单 要一次性求出 0 到 n 每个数的结果，靠 DP 复用 i >> 1 的答案而非独立统计
461. 汉明距离 简单 先异或得到差异位串再统计 1 的个数，本题是它的后半步
477. 汉明距离总和 中等 两两求距离会超时，改为按位统计每一位上 0 与 1 的数量再相乘
231. 2 的幂 简单 等价于判断 1 的个数是否恰好为 1，一行 n & (n-1) 即可
201. 数字范围按位与 中等 求区间内所有数按位与的结果，本质是找公共前缀，考察对位的整体推理
371. 两整数之和 中等 用异或与进位模拟加法，是位运算里最能体现「用位替代算术」的题
LCR 003. 比特位计数 简单 与 338 同题，可直接套用递推写法
面试题 05.06. 整数转换 简单 与 461 同题但输入含负数，正好复现本题在 Java 有符号右移上的坑