题目描述
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

示例1

输入: 5
输出: [0,1,1,2,1,2]

题解

方法一:直接计算
这应该是我们最先想到的方法,即计算每一个数的二进制1的个数。
这种方法的时间复杂度为 *O(k × m)*,空间复杂度为 *O(1)*(返回结果不计入空间复杂度)。

方法二:动态规划
我们假设 0 ≤ j < i,那么我们是否可以通过已知 j 的二进制1的个数去求 i 的,这也是动态规划的思想,那么我们要通过求 dp 的表达式去构思代码。
我们知道 n&(n-1) 会将 n 二进制最右边的1置0,所以可以通过这一点来构思 dp 方程。即 dp[x]=dp[x&(x-1)]+1

C#代码

public int[] CountBits(int num) {
int[] dp=new int[num+1];
for(int i=1;i<num+1;++i)
{
dp[i]=dp[i&(i-1)]+1;
}
return dp;
}

时间复杂度:O(n)
空间复杂度:O(1) (返回结果不计入空间复杂度)

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/counting-bits

位运算常用技巧
获取最右边的1:x & (-1)
最右边1置0:x & (x-1)
判断奇偶:(a&1) == 1