题目

题解

100000 -> 1
100001 -> 2

100 -> 1
101 -> 2

可见这是个循环 ， 并且以开头为1的二进制整数开始

通过逐位相与得出1000这样的数bithight ;

之后就是 典型的一维动态规划 bits[i] = bits[i - bithight] + 1; 下一位等于上一位的处理之后的结果

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        int bithight = 0;
        for (int i = 1; i <= n; i++)
        {
            if ((i&(i - 1)) == 0) {
                bithight = i;
            }
            bits[i] = bits[i - bithight] + 1;
        }
        return bits;
    }
};