Leetcode-338:比特位计数

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

示例 1:

输入: 2
输出: [0,1,1]
示例 2:

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

思路：

首先是一个数减1，对应二进制的变化就是最右的一个1变为0，而这个1右边的所有0变为1，即相当于包括最后一个1在内的右边所有位取反，例如12（1100）减1，得到11（1011），然后再与变化前的数12（1100）进行与&运算，得到8（1000），可以看出经过这样一个运算之后这个数的1的个数减少了一个，所以可以利用这个原理，得到res[i]=res[i&(i-1)]+1

class Solution {
    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;
    }
}