LCR003.比特位计数

链接：LCR003.比特位计数
难度：Easy
标签：位运算、动态规划
简介：给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

题解 1 - cpp

• 编辑时间：2021-12-23
• 执行用时：8ms
• 内存消耗：8.4MB
• 编程语言：cpp
• 解法介绍：当遇到 2 的指数幂后，从 0 开始重新遍历。

class Solution {
   public:
    vector<int> countBits(int n) {
        vector<int> ans;
        ans.push_back(0);
        if (n == 0) return ans;
        ans.push_back(1);
        if (n == 1) return ans;
        for (int num = 2, i = 0; num <= n; num++, i++) {
            if ((num & (num - 1)) == 0) i = 0;
            ans.push_back(ans[i] + 1);
        }
        return ans;
    }
};