【位运算】比特位计数

比特位计数

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：
0 <= n <= 105
进阶：
很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

方法一：枚举二进制为1的位

对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
对于给定的 n，计算从 0 到 n 的每个整数的「一比特数」的时间都不会超过 O(logn)，因此总时间复杂度为 O(nlogn)。

class Solution {public int[] countBits(int n) {int[] bits=new int[n+1];for(int i=0;i<=n;i++){int ones=0;int x=i;while(x>0){x&=(x-1);ones++;}bits[i]=ones;}return bits;}
}

复杂度分析
时间复杂度：O(nlogn)。需要对从 0 到 n 的每个整数使用计算「一比特数」，对于每个整数计算「一比特数」的时间都不会超过 O(logn)。
空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

方法二：动态规划——最低设置位

定义正整数 x 的「最低设置位」为 x 的二进制表示中的最低的 1 所在位。例如，10 的二进制表示是 1010 (2) ，其最低设置位为 2，对应的二进制表示是 10 (2) 。
令 y=x & (x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然 0≤y<x，bits[x]=bits[y]+1。因此对任意正整数 x，都有 bits[x]=bits[x & (x−1)]+1。
遍历从 1 到 n 的每个正整数 i，计算 bits 的值。最终得到的数组 bits 即为答案。
代码

class Solution {public int[] countBits(int n) {int[] bits = new int[n + 1];for (int i = 1; i <= n; i++) {bits[i] = bits[i & (i - 1)] + 1;}return bits;}
}

复杂度分析
时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。