[数据结构与算法]【力扣】[热题HOT100] 338.比特位计算

1、题目

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

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

2、思路分析

1）暴力求解法
遍历每一个从0 到 n 的每一个数字，算出每个数字1的个数，将其存储在数组中，且返回。

class Solution {
public:
    int OneCount(int i)
    {
        int one = 0;
        while(i > 0)
        {
            i &= (i - 1);
            one++;
        }
        return one;
    }

    vector<int> countBits(int n) {
        vector<int> ret(n + 1);
        for(int i = 1; i <= n; ++i)
        {
            ret[i] = OneCount(i);
        }
        return ret;
    }
};

2）动态规划
如果正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y & (y-1)=0。
0 的「一比特数」为 0。使用 highBit 表示当前的最高有效位，遍历从 1 到 n 的每个正整数 i，进行如下操作。

如果 i & (i-1)=0，则令 ihighBit=i，更新当前的最高有效位。

i 比 i- highBit 的「一比特数」多 1，由于是从小到大遍历每个整数，因此遍历到 i 时，i?highBit 的「一比特数」已知，令 bits[i]=bits[i?highBit]+1。

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