LeetCode - 338. Counting Bits

解题代码:

classSolution {

public:

    vector<int> countBits(int num) {

        vector<int> result(num+1);

        result[0]=0;

        for(int i=1;i<=num;i++){

            int j=i^(i-1);

            if(j==1){

                result[i]=result[i-1]+1;

            }

            else if(j==2){

                result[i]=result[i-1];

            }

            else{

               result[i]=result[i-1]+2-log(j+1)/log(2);

            }

        }

        return result;

    }

};

解题思路:

题目要求输出0到n每个数字二进制中1的个数。一方面，题目不让用__builtin_popcount之类的函数，另一方面，传统的方法是对每个数除以二求余数以确定有多少个1，这样在时间复杂度上会比较高。因此我对数字进行观察研究，试图找到其中的规律。不难发现，0的“1”有0个，对于第m位，当它与m-1作异或运算后，若得到1，则m的“1”个数会比m-1多1个；若得到2，则m的“1”个数与m-1相同；若得到其他的结果，设为a，a必然等于2^k-1，k位某常数，而m的“个数”会比m-1少k-2个，即少log₂(a+1)-2个。