338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

  • 0 <= n <= 105

进阶：

  • 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
  • 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

根据二进制特性，前面的位数和 i/2 一致，最后新增的一位是 i%2

1
2
3
4
5
6
7
8
9
10
11
func countBits(n int) []int {
	if n == 0 {
		retirn []int{0}
	}
	ans := []int{0, 1}
	for i:=2; i<=n; i++ {
		t1, t2 := i/2, i%2
		ans = append(ans, ans[t1] + t2)
	}
	return ans
}

Brian Kernighan 算法

Brian Kernighan 算法的原理是：对于任意整数 xxx，令 x=x & (x−1)x=x&(x-1)x=x & (x−1)，该运算将 xxx 的二进制表示的最后一个 111 变成 000。因此，对 xxx 重复该操作，直到 xxx 变成 000，则操作次数即为 xxx 的「一比特数」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func onesCount(x int) (ones int) { 
	for ; x > 0; x &= x - 1 { 
		ones++ 
	} 
	return 
} 

func countBits(n int) []int { 
	// 0-n 共 n+1 个数
	bits := make([]int, n+1) 
	for i := range bits { 
		bits[i] = onesCount(i) 
	} 
	return bits 
}