比特位计数
📌 定义
给定一个非负整数 n，对于每个数字 i（0 ≤ i ≤ n），计算其二进制表示中 1 的个数，并返回一个长度为 n+1 的数组。
示例:
输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 → 000 → 0个1
1 → 001 → 1个1
2 → 010 → 1个1
3 → 011 → 2个1
4 → 100 → 1个1
5 → 101 → 2个1
核心思路
使用动态规划结合位运算，利用已计算的结果避免重复计算。
关键观察：
i & (i - 1)可以将 i 的最右边的 1 变为 0bits[i] = bits[i & (i - 1)] + 1
或者：
i >> 1将 i 右移一位bits[i] = bits[i >> 1] + (i & 1)
示例: n = 5
方法1: i & (i - 1)
bits[0] = 0 (base case)
bits[1] = bits[1 & 0] + 1 = bits[0] + 1 = 1
bits[2] = bits[2 & 1] + 1 = bits[0] + 1 = 1
bits[3] = bits[3 & 2] + 1 = bits[2] + 1 = 2
bits[4] = bits[4 & 3] + 1 = bits[0] + 1 = 1
bits[5] = bits[5 & 4] + 1 = bits[4] + 1 = 2
结果: [0, 1, 1, 2, 1, 2]
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力法 | O(n log n) | O(1) | 每个数字遍历其二进制位 |
| DP + i&(i-1) | O(n) | O(n) | 利用已计算结果 |
| DP + i>>1 | O(n) | O(n) | 右移动态规划 |
| 查表法 | O(n) | O(256) | 预计算8位表 |
Go 代码
Go 实现
package main
import "fmt"
// 方法1: i & (i - 1)
func countBits(n int) []int {
bits := make([]int, n+1)
for i := 1; i <= n; i++ {
bits[i] = bits[i&(i-1)] + 1
}
return bits
}
// 方法2: 右移
func countBitsShift(n int) []int {
bits := make([]int, n+1)
for i := 1; i <= n; i++ {
bits[i] = bits[i>>1] + (i & 1)
}
return bits
}
// 方法3: 最高有效位
func countBitsMSB(n int) []int {
bits := make([]int, n+1)
highBit := 0
for i := 1; i <= n; i++ {
if i&(i-1) == 0 {
highBit = i
}
bits[i] = bits[i-highBit] + 1
}
return bits
}
// 方法4: 查表法
func countBitsTable(n int) []int {
// 预计算0-255的比特数
table := make([]int, 256)
for i := 0; i < 256; i++ {
table[i] = table[i>>1] + (i & 1)
}
bits := make([]int, n+1)
for i := 0; i <= n; i++ {
// 将32位整数拆分成4个8位
bits[i] = table[i&0xFF] +
table[(i>>8)&0xFF] +
table[(i>>16)&0xFF] +
table[(i>>24)&0xFF]
}
return bits
}
func main() {
n := 5
result := countBits(n)
fmt.Printf("n = %d, 结果: %v\n", n, result)
}思路展开
方法1详解：i & (i - 1)
i & (i - 1) 的作用：去掉 i 最右边的1
示例:
i = 5 (101)
i - 1 = 4 (100)
i & (i - 1) = 101 & 100 = 100 (4)
i = 6 (110)
i - 1 = 5 (101)
i & (i - 1) = 110 & 101 = 100 (4)
递推关系:
bits[i] = bits[i & (i - 1)] + 1
↑ ↑
去掉一个1后的结果 被去掉的那个1
计算过程（n=5）:
i=0: bits[0] = 0 (初始)
i=1: bits[1] = bits[0] + 1 = 1
i=2: bits[2] = bits[0] + 1 = 1 (2&1=0)
i=3: bits[3] = bits[2] + 1 = 2 (3&2=2)
i=4: bits[4] = bits[0] + 1 = 1 (4&3=0)
i=5: bits[5] = bits[4] + 1 = 2 (5&4=4)
方法2详解：右移
观察规律:
i >> 1 是 i 除以2的整数部分
i & 1 是 i 的最低位（0或1）
递推关系:
bits[i] = bits[i >> 1] + (i & 1)
↑ ↑
i除以2的比特数 i的最低位
示例:
i = 5 (101)
i >> 1 = 2 (10)
i & 1 = 1
bits[5] = bits[2] + 1 = 1 + 1 = 2
计算过程（n=5）:
i=0: bits[0] = 0
i=1: bits[1] = bits[0] + 1 = 1 (1>>1=0, 1&1=1)
i=2: bits[2] = bits[1] + 0 = 1 (2>>1=1, 2&1=0)
i=3: bits[3] = bits[1] + 1 = 2 (3>>1=1, 3&1=1)
i=4: bits[4] = bits[2] + 0 = 1 (4>>1=2, 4&1=0)
i=5: bits[5] = bits[2] + 1 = 2 (5>>1=2, 5&1=1)
方法3详解：最高有效位
观察规律:
2^k 到 2^(k+1) - 1 的数字可以分解为:
数字 i = 2^k + j (其中 0 ≤ j < 2^k)
bits[i] = 1 + bits[j]
示例（n=7）:
范围 [0, 1]: 最高位 = 1
bits[1] = 1
范围 [2, 3]: 最高位 = 2
bits[2] = bits[0] + 1 = 1
bits[3] = bits[1] + 1 = 2
范围 [4, 7]: 最高位 = 4
bits[4] = bits[0] + 1 = 1
bits[5] = bits[1] + 1 = 2
bits[6] = bits[2] + 1 = 2
bits[7] = bits[3] + 1 = 3
经典题目
LeetCode 问题
扩展问题
- 统计二进制字符串中1的个数
- 二进制中连续1的最大个数
⚖️ 优缺点
优点
- ✅ 时间高效：O(n) 线性时间
- ✅ 空间合理：O(n) 用于存储结果
- ✅ 避免重复计算：动态规划思想
- ✅ 多种实现：可根据场景选择
缺点
- ❌ 需要额外空间：存储所有结果
- ❌ 不适合稀疏查询：如果只查询少数几个数，暴力法更好
🎨 应用场景
💡 优化技巧
💡 三种方法对比
| 方法 | 递推公式 | 优点 | 缺点 |
|---|---|---|---|
| i&(i-1) | bits[i] = bits[i&(i-1)] + 1 | 直观易懂 | 需要理解位操作 |
| 右移 | bits[i] = bits[i>>1] + (i&1) | 简洁高效 | 不太直观 |
| 最高位 | bits[i] = bits[i-highBit] + 1 | 规律性强 | 需要维护highBit |