LeetCode 338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

提示：

0 <= n <= 105

进阶：

很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

解法一：动态规划，如3的比特位为1的位数等于将3右移一位（即1）的比特位为1的位数加上3&1：

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

此算法时间复杂度为O（n），空间复杂度为O（1）。

解法二：每个数字都计算一遍位数：

class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for (int i = 1; i <= n; ++i) {int ibak = i;while (ibak) {ans[i] += ibak & 1;ibak >>= 1;}} return ans;}
};

此算法时间复杂度为O（nlgn），空间复杂度为O（1）。

解法三：使用库函数：

class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for (int i = 1; i <= n; ++i) {ans[i] = __builtin_popcount(i);} return ans;}
};

此算法时间复杂度为O（nlgn），空间复杂度为O（1）。__builtin_popcount函数的时间复杂度为O（lgn）。

解法四：利用x&(x-1)的结果是x的最低的比特位从1变成0：

class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for (int i = 1; i <= n; ++i) {int ibak = i;while (ibak) {ibak = ibak & (ibak - 1);ans[i] += 1;}} return ans;}
};

此算法时间复杂度为O（nlgn），空间复杂度为O（1）。

解法五：动态规划，最高位一定为1，x的比特位为1的计数等于去掉最高位后的数字的比特位为1的计数加上最高位的1：

class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);int highestBit = 0;for (int i = 1; i <= n; ++i) {// 当i是2的幂时，更新最高位if ((i & (i - 1)) == 0) {highestBit = i;}ans[i] = ans[i - highestBit] + 1;} return ans;}
};

此算法时间复杂度为O（n），空间复杂度为O（1）。

解法六：动态规划，x的比特位为1的计数等于把x的最低位的1改为0后的数的比特位为1的计数加上最低位的1：

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

此算法时间复杂度为O（n），空间复杂度为O（1）。