leetcode--338--比特位计数

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

示例 1:

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

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

链接：https://leetcode-cn.com/problems/counting-bits

思路：
1、第 i 个数中 1 的个数等价于 i>>1 数中1的个数加上 i 末尾1的个数

Python代码：

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        ret = []
        ret.append(0)

        for i in range(1, num+1):
            item = ret[i>>1] + (i&1)
            ret.append(item)
        return ret

C++代码：

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret;
        ret.push_back(0);

        for (int i=1; i<=num; i++){
            int item = ret[i>>1] + (i&1);
            ret.push_back(item);
        }
        return ret;
    }
};