Counting Bits

这道题是BIT DP里面最常见的了，之前用的思路是序列型DP那样没多一个bit位就把上一bit位的值直接赋过来再算另外一半，但是如果直接用bit位操作的话这题可以直接达到O(n)的时间复杂度且逻辑很简单，这里稍微解释一下，任何一个数num和num/2的1个数差别最多为1，举例说明，5的2进制为101，5除以2为10即2，这时可以看到5和2的区别就是5的最低位多了一个1，通过这个观察可以得出状态方程

dp[i] = dp[i >> 2] + i % 2

有了上面的状态方程代码几乎就已经完成了，下面是代码

class Solution:
    # @param {int} num a non negative integer number
    # @return {int[]} an array represent the number of 1's in their binary
    def countBits(self, num):
        # Write your code here
        dp = [0] * (num + 1)

        for i in xrange(1, num + 1):
            dp[i] = dp[i >> 1] + i % 2
        return dp