LeetCode 191. 位1的个数

约 4 分钟
文章信息 13 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 20-50 字节跳动 美团 快手 腾讯 百度 旷视 虾皮 面试经典 150 题
标签
位运算 分治
目录

题目描述

✅ 191. 位1的个数

题意分析

给定一个 32 位的整数，把它按无符号数解释成二进制串，返回其中值为 1 的二进制位的个数，也就是通常说的汉明重量。

需要留意「无符号」这三个字。输入在 Java 里是 int，在 Go 的旧签名里是 uint32，但题目关心的始终是那 32 个比特本身，而不是它们被当作有符号数时代表的正负。这意味着最高位如果是 1，它同样要被计入答案，不能因为整数看起来是负数就少数一位。

约束信号有两个。第一，位宽固定为 32，所以答案的取值范围是 0 到 32，输出规模极小；第二，没有给出任何关于 1 的分布规律，输入可以是任意比特模式。这两点合起来暗示：能做到与 1 的个数成正比而不是与位宽成正比的算法是有价值的。

边界情形：输入全 0 时答案是 0，循环体一次都不该进入；输入全 1（无符号的 4294967295，在 Java 里就是 -1）时答案是 32，这是最容易暴露符号处理错误的用例；输入只有最高位是 1（无符号的 2147483648，Java 里是 Integer.MIN_VALUE）时答案是 1，任何依赖「大于 0」的循环条件都会在这里翻车。

解法：不断消去最低位 1

核心思路

逐位右移可以固定检查 32 位，但 Java 的有符号右移容易在最高位为 1 时出错。更直接的做法是每轮消去一个已经存在的 1：

n - 1 会把 n 最低位的 1 变成 0，并把它右侧的所有 0 变成 1；再与原数按位与，右侧这些位全部归零，因此 n & (n - 1) 恰好删除最低位的一个 1。

例如 n = 1011000，n - 1 = 1010111，两者按位与得到 1010000。

循环不变量是：count 加上当前 n 中 1 的数量，始终等于原数中 1 的数量。每轮 n 少一个 1、count 加一；当 n == 0 时，count 就是答案。这个过程只关心二进制位，不受 Java int 正负号影响。

解题步骤

  1. 初始化计数器 count = 0。
  2. 当 n != 0 时，执行 n &= n - 1 删除最低位的 1，随后令 count++。
  3. n 变为 0 后返回 count。

以 11 的二进制 1011 为例：

  • 1011 & 1010 = 1010，计数为 1；
  • 1010 & 1001 = 1000，计数为 2；
  • 1000 & 0111 = 0000，计数为 3。

循环恰好执行三次，所以答案为 3。

代码实现

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)$。

关键点总结

  • n & (n - 1) 删除最低位的 1，循环次数直接等于答案。
  • Java 中循环条件必须是 n != 0，不能用 n > 0，因为最高位为 1 时 n 是负数。
  • 若采用右移方案，Java 必须使用无符号右移 >>>；本解法没有符号扩展问题。
  • 相关技巧：n & -n 可以取出最低位的 1。

易错点总结

  • 写成 while (n > 0)：n = -1 时会直接返回 0，正确答案是 32。
  • 使用 n >>= 1 直到零：负数右移会在高位补 1，可能永不结束；应使用 >>>。
  • 每轮忘记 count++：虽然最终能清零 n，但答案始终为 0。
  • 固定只检查 31 位：会漏掉最高位；例如 Integer.MIN_VALUE 的答案应为 1。
  • 把 Go 参数写成有符号整数再依赖右移：应按题目位模式使用 uint32。

相似题目

题目 难度 考察点
338. 比特位计数 简单 要求 $0$ 到 $n$ 的全部答案，用 dp[i] = dp[i & (i-1)] + 1 线性递推
461. 汉明距离 简单 先异或求出差异位，再套用本题的消位计数
477. 汉明距离总和 中等 不能两两枚举，需按位统计 0 和 1 的个数后相乘
1356. 根据数字二进制下 1 的数目排序 简单 把汉明重量当作自定义比较器的主键，重量相同时退回数值排序
LCR 003. 比特位计数 简单 与 338 同题，另可用 dp[i] = dp[i >> 1] + (i & 1) 的奇偶递推
剑指 Offer 15. 二进制中1的个数 简单 与本题同解，剑指版本更强调 Java 有符号数下的循环条件陷阱
面试题 05.06. 整数转换 简单 求把 A 变成 B 需翻转几位，等价于 A ^ B 的汉明重量