每日一题：比特位个数

赞

题目338：比特位计数


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

示例1：

输入: 2输出: [0,1,1]
示例2：
输入: 5输出: [0,1,1,2,1,2]
进阶:

  • 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？

  • 要求算法的空间复杂度为O(n)。

  • 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

分析

做此题首先需要知道如何计算一个数的比特位的个数。可以通过(x & x-1)每次消除数字二进制表示形式的最后一个1，代码如下：

int count(int num) {    int n = 0;    while (num != 0) {        ++n;        num = (num & num-1);    }    return n;}
根据上面计算二进制1个数的代码分析，我们可以用dp[i]表示数字i的比特位个数，知道dp[i]和dp[i & i-1]相差1个比特位个数，所以就有dp[i]=dp[i & i-1]+1直接看代码：

代码

方法1：

class Solution {public:    int count(int num) {        int n = 0;        while (num != 0) {            ++n;            num = (num & num-1);        }        return n;    }
    vector<int> countBits(int num) {        vector<int> dp(num+1, 0);        for (int i = 0; i <= num; ++i) {            dp[i] = count(i);        }        return dp;    }};
方法2：
class Solution {public:    vector<int> countBits(int num) {        vector<int> dp(num+1, 0);        for (int i = 1; i <= num; ++i) {            dp[i] = dp[i & (i-1)] + 1;        }        return dp;    }};