求0~n每个数字二进制对应的1的数量

算法之美
1

给定一个数字n，求0~那中每个数字对应的二进制中包含1的数量

样例：

输入： 10
输出：[0 1 1 2 1 2 2 3 1 2 2]

解法一 ：

时间复杂度： o(nlog(n))

num &(num-1) 可以把num二进制数最右边的1变成0(不明白的小伙伴可参考这题)，我们可以通过多次进行上述式子将num变化成0，运行的次数就是num二进制的1 的数量。

func GetOne(n int)[]int{
	ans := make([]int, n+1)
	for i := 0; i < n+1; i++ {
		ans[i]=countOne(i)
	}
	return ans
}
func countOne(n int) int {
	OneNum:=0
	for n >0{
		OneNum ++
		n  = n & (n-1)
	}
	return OneNum
}

解法二 ：

时间复杂度： o(n)

我们可以考虑使用动态规划来降低复杂度，我们设f(X) 为x的二进制中1的数量。我们可以很容易得到以下转化方程：

f(n) = 1+f(n-m) (m为小于n的最大2的幂次方)

例如：

  • n=5(101) ,m=4(100) ，f(5) = 1+f(5-4) = 1+f(1) = 2
  • n=7(111) ,m=4(100) ，f(7) = 1+f(7-4) = 1+f(3) = 1+1+f(1) = 3
  • n=20(10100) ,m=16 (10000) ,f(20) = 1+f(20-16) = 1+f(4) = 1+1+f(0)=2
  • …

而m的值我们可以在遍历的过程中推进，根据以上转移方程我们可以写出以下代码

func GetOne(n int)[]int{
	if n ==0{
		return []int{0}
	}
	var dp = make([]int, n+1)
	dp[0],dp[1]=0,1
	bit:=1
	for i := 2; i < n+1; i++ {
		if i >=(bit<<1){
			bit <<= 1
		}
		dp[i]=1+dp[i-bit]
	}
	return dp
}

以上两种解法空间复杂度均为 o(1) （结果数组不算在内）

2

简练讲，两个解法都是计数加一
解一是最右边 1 清零，对单个数字，且 1 个数较少时比较高效
解二是最左边 1 清零，对连续数字，用动态规划解法，分摊了计算量

另外求单个数字的二进制的 1 个数，可参考 C++ 的内置函数 __builtin_popcount()，有查表法、二分法 ，效率更高

3

是的，可以这么理解，用解一的思路也是可以做成动态规划的。