1. 概述
在本教程中，我们将讨论统计整数中置位比特数（即二进制表示中为1的位数）的问题。首先，我们会明确问题定义并举例说明。随后，我们将探讨三种不同的解决方法：
- 朴素方法（Naive Approach）
- 跳跃法（Jumping on Ones Approach）
- 汉明权重法（Hamming Weight Approach）
每种方法都有其独特的时间复杂度和适用场景，最终我们会对它们进行比较和总结。
2. 问题定义
给定一个整数 X，我们需要统计其二进制表示中值为 1 的比特位数量。
例如：
输入 X = 9，其二进制表示为 1001，其中有两个 1，因此输出应为 2。
3. 朴素方法（Naive Approach）
✅ 思路
逐个检查整数的每一位二进制位，若该位为 1，则计数器加一。具体做法是：
- 通过
X & 1获取最低位； - 若为
1则计数器加一； - 然后将
X右移一位（等价于除以2）； - 直到
X == 0。
🧠 代码实现
public static int countSetBits(int X) {
int answer = 0;
while (X > 0) {
if ((X & 1) == 1) {
answer++;
}
X /= 2;
}
return answer;
}
⚙️ 时间复杂度
- **O(log₂(X))**，其中
X是输入整数。因为我们要遍历每一位二进制位。
4. 跳跃法（Jumping on Ones Approach）
✅ 思路
每次只关注最后一个为 1 的比特位，将其清零，直到整数变为 0。这种方法跳过了所有为 0 的位，只处理 1。
- 通过
X & -X获取最后一位为1的比特； - 将其从
X中减去； - 每次操作都增加计数器；
- 直到
X == 0。
🧠 代码实现
public static int countSetBits(int X) {
int answer = 0;
while (X > 0) {
int lastBit = X & -X;
X -= lastBit;
answer++;
}
return answer;
}
⚙️ 时间复杂度
- **O(N)**，其中
N是二进制中为1的位数。 - 最优情况为 **O(1)**（如
X = 1），最差仍为 **O(log₂(X))**。
✅ 优点：跳过无用的
0，在1较少时效率更高。
5. 汉明权重法（Hamming Weight Approach）
✅ 思路
这是一种位操作优化算法，利用掩码（mask）分块统计。它通过将整数划分为多个块，逐步合并计算每个块中 1 的数量，最终得到总和。
具体步骤如下：
- 将每 1 位作为一个块，统计相邻两位的
1数量； - 合并成每 2 位一个块；
- 再合并成每 4 位一个块；
- 依此类推，直到合并成一个 32 位的大块。
🧠 代码实现
public static int countSetBits(int X) {
X = (X & 0x55555555) + ((X >> 1) & 0x55555555); // 1-bit blocks
X = (X & 0x33333333) + ((X >> 2) & 0x33333333); // 2-bit blocks
X = (X & 0x0F0F0F0F) + ((X >> 4) & 0x0F0F0F0F); // 4-bit blocks
X = (X & 0x00FF00FF) + ((X >> 8) & 0x00FF00FF); // 8-bit blocks
X = (X & 0x0000FFFF) + ((X >> 16) & 0x0000FFFF); // 16-bit blocks
return X;
}
⚙️ 时间复杂度
- **O(1)**，因为操作次数是固定的，与输入大小无关。
✅ 优点：速度极快，适合对性能要求高的场景。
6. 总结
我们探讨了三种统计整数中置位比特数的方法：
| 方法 | 时间复杂度 | 特点 |
|---|---|---|
| 朴素方法 | O(log₂(X)) | 实现简单，适合初学者 |
| 跳跃法 | O(N) | 只处理 1，适合稀疏比特 |
| 汉明权重法 | O(1) | 高效，适合高性能场景 |
在实际开发中，推荐使用 汉明权重法 或 JDK 内置的 Integer.bitCount() 方法，它们都是底层优化过的高效实现。
✅ 小贴士：Java 中
Integer.bitCount(x)实现的就是汉明权重算法，可以直接使用，无需自己实现。