题目大意：
比特位计数
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2 输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2] 进阶:
- 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
- 要求算法的空间复杂度为O(n)。
- 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=338
解题思路分析：
这是一道动态规划的题目。首先我们应该掌握一个知识点，即如何求出一个数字的二进制表现下1的个数。这需要先将十进制转为二进制，转化的方式是求当前十进制数字与2的余数，该余数即是二进制数的最低位，然后将该十进制数除以2，继续求它与2的余数，这一次求出的余数是二进制数的次低位，重复上述过程，直到十进制数变为0为止。我们统计出所有值为1的位数即可。
掌握了上述方法，本题实际上已经有了答案。我们从0循环至num，分别计算出当前数字的二进制表现下1的个数即可。不过这种解法效率相对较低，换一个思路去思考，其实我们只需要知道当前数字num二进制表现下最低位是否为1即可，接下来，根据上文讲到的方法，我们需要将当前数字除以2（num/2）之后再继续使用它与2进行求余操作。对于num/2，它一定小于num，另外由于我们是从0循环至当前数字num的，也就是说，num/2这个数字我们之前一定已经计算过它的结果，因此我们这里不必再去做重复计算，直接利用之前的计算结果即可。
res[num] = num%2 + res[num/2] ; // 最低位是否为1 加上 自身一半的数字中1的个数
以上即是动态规划的推导公式，而本题的返回结果正是动态规划使用到的dp数组。如果你想将代码写的更酷炫一些，num/2这里「除以2」操作可以使用「>>1」(右移一位)来替代，即：
res[num] = num%2 + res[num>>1] ;
实现代码：
public int[] countBits(int num) {
int[] res=new int[num+1]; // 返回结果兼DP数组
// 从1开始循环每个数字。（数字0中1的个数是0）
for(int i=1;i<=num;i++){
// 最低位是否为1 加上 自身一半的数字中1的个数
res[i]= i%2+res[i/2];
}
return res;
} 本题解法执行时间为1ms。
Runtime: 1 ms, faster than 99.80% of Java online submissions for Counting Bits.
Memory Usage: 43.5 MB, less than 5.88% of Java online submissions for Counting Bits.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-338-counting-bits-解题思路分析/