动态规划之数字n二进制位中1的个数

• 题目描述
• 题解

一个非负的整数n，请统计n的二进制表示中1的个数。

示例 1：

非负整数：3
输出结果：2

示例 2：

非负整数：10
输出结果：2

class Solution {
public:
    
    vector countBits(int num) {
        // write your code here
        vector dp(num + 1);
        for (int i = 0; i < num + 1; i++) {
            dp[i] = 0;
        }        

        for (int i = 1; i <= num; i++)  {
            dp[i] = dp[i >> 1] + (i & 1);
        }

        return dp[num];
    }
};