比特位计数

给定一个非负整数 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）来执行此操作。
  解题思路：
  其实这些天LeetCode做下来，有很多题都是数学上的题。这些题是可以直接暴力循环来做，但要时间复杂度低，就要从数学上去想办法，找到类似通解的公式。这道题就是找规律。我们先把0-15的二进制码写出来：

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110 #把14右移一位，前面补零，也就是14//2=7，它就和7一样了。
1111 #把15右移一位，前面补零，它也和7一样了，但是我们右移删了1个1，所以要加回来

那么得到的规律就是，对于偶数，它和它的一半的数的1是相等的。对于奇数，它的1的个数比它的一半的1的个数多1。所以，代码如下：

 def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        res = [0]
        for i in range(1,num+1):
            res.append(res[i>>1]+(i%2))
        return res