首页 > itarticle > counting bits

counting bits

admin 11月 13, 2020 0

思路

正常想法是对每个数都进行计算。

for (int i = 0; i <= num; i++) {
            int count = 0;
            int value = i;
            while (value) {
                count += value % 2;
                value >>= 1;
            }
            vec[i] = count;
        }

显然时间复杂度：O(n*sizeof(i))
但是转换思路，一个数的1的个数可以表示为最后一位是否为1以及其他位的1的个数。

class  {
public:
    vector<int> countBits(int num) {
        vector<int> vec(num + 1, 0);
        for (int i = 1; i <= num; i++) {
            vec[i] = vec[i>>1] + i%2;
            cout << vec[i] << " " << vec[i >> 1] << endl;
        }
        return vec;
    }
};