题目描述

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

解法一：利用i & (i - 1)

对一个整数i，每次用i & (i - 1)将整数i的最右边的1变成0，循环计算直到i等于0，即可计算出整数i的二进制形式中1的个数。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1, 0);      //初始化长度为n+1的0元素数组

        for (int i = 0; i <= n; ++ i)
        {
            int j = i;
            while (j != 0)
            {
                j = j & (j - 1);
                res[i] ++ ;
            }
        }

        return res;
    }
};

因为i & (i - 1)可以将整数i的最右边的1变成0，也就是说，整数i的二进制形式中1的个数比i & (i - 1)的二进制形式中1的个数多1。代码可改进如下：

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1, 0);

        for (int i = 1; i <= n; ++ i)
        {
            res[i] = res[i & (i - 1)] + 1;
        }

        return res;
    }
};

解法二：右移

如果i是偶数，那么i的二进制形式中1的个数为i / 2中1的个数，如果i是奇数，那么i的二进制形式中1的个数为i / 2的个数加1。
两种情况可举例如下：

• 3的二进制表示为11，6为110，7为111；
• 可以由3的二进制中1的个数推演出6与7的二进制中1的个数；
• 6的二进制表示中1个数为(6 / 2)即3的二进制表示中1的个数加上(6 % 2)即0等于2个，7的二进制表示中1个数为(7 / 2)即3的二进制表示中1的个数加上(7 % 2)即1等于3个。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1, 0);

        for (int i = 1; i <= n; ++ i)
        {
            //此处用(i & 1)代替了(i % 2)，因为位运算比除法运算和求余运算更高效
            res[i] = res[i >> 1] + (i & 1); 
        }

        return res;
    }
};