给你一个整数 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 <= 10^5
进阶：
- 很容易就能实现时间复杂度为
O(n log n)的解决方案，你可以在线性时间复杂度O(n)内用一趟扫描解决此问题吗？ - 你能不使用任何内置函数解决此问题吗？（如，C++ 中的
__builtin_popcount）
这道题需要计算从 0 0 0 到 n n n 的每个整数的二进制表示中的 1 1 1 的数目。
部分编程语言有相应的内置函数用于计算给定的整数的二进制表示中的 1 1 1 的数目，例如 Java 的 Integer.bitCount ，C++ 的 __builtin_popcount 。下列各种方法均为不使用内置函数的解法。
为了表述简洁，下文用「一比特数」表示二进制表示中的 1 1 1 的数目。
解法1 B r i a n K e r n i g h a n Brian Kernighan BrianKernighan 算法
最直观的做法是对从 0 0 0 到 n n n 的每个整数直接计算「一比特数」。每个int型的数都可以用 32 32 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 1 1 的数目。
利用 Brian Kernighan 算法，可以在一定程度上进一步提升计算速度。该算法的原理是：对于任意整数 x x x ，令 x = x & ( x − 1 ) x=x~\&~(x-1) x=x & (x−1) ，该运算将 x x x 的二进制表示的最后一个 1 1 1 变成 0 0 0 。因此，对 x x x 重复该操作，直到 x x x 变成 0 0 0 ，则操作次数即为 x x x 的「一比特数」。
对于给定的 n n n，计算从 0 0 0 到 n n n 的每个整数的「一比特数」的时间都不会超过 O ( log n ) O(\log n) O(logn) ，因此总时间复杂度为 O ( n log n ) O(n \log n) O(nlogn) 。
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 0; i <= n; i++) bits[i] = countOnes(i);
return bits;
}
public int countOnes(int x) {
int ones = 0;
while (x > 0) {
x &= (x - 1);
ones++;
}
return ones;
}
}
复杂度分析:
- 时间复杂度： O ( n log n ) O(n \log n) O(nlogn) 。需要对从 0 0 0 到 n n n 的每个整数使用计算「一比特数」，对于每个整数计算「一比特数」的时间都不会超过 O ( log n ) O(\log n) O(logn) 。
- 空间复杂度： O ( 1 ) O(1) O(1) 。除了返回的数组以外，空间复杂度为常数。
解法2 动态规划——最高有效位
方法一需要对每个整数使用 O ( log n ) O(\log n) O(logn) 的时间计算「一比特数」。可以换一个思路，。令 bits [ i ] \textit{bits}[i] bits[i] 表示 i i i 的「一比特数」，则上述关系可以表示成： bits [ i ] = bits [ j ] + 1 \textit{bits}[i]= \textit{bits}[j]+1 bits[i]=bits[j]+1 。
对于正整数 x x x ，如果可以知道最大的正整数 y y y ，使得 y ≤ x y \le x y≤x 且 y y y 是 2 2 2 的整数次幂，则 y y y 的二进制表示中只有最高位是 1 1 1 ，其余都是 0 0 0，此时称 y y y 为 x x x 的「最高有效位」。令 z = x − y z=x-y z=x−y ，显然 0 ≤ z < x 0 \le z<x 0≤z<x ，则 bits [ x ] = bits [ z ] + 1 \textit{bits}[x]=\textit{bits}[z]+1 bits[x]=bits[z]+1 。
显然， 0 0 0 的「一比特数」为 0 0 0 。使用 highBit \textit{highBit} highBit 表示当前的最高有效位，遍历从 1 1 1 到 n n n 的每个正整数 i i i，进行如下操作。
- 如果 i & ( i − 1 ) = 0 i~\&~(i-1)=0 i & (i−1)=0 ，则令 highBit = i \textit{highBit}=i highBit=i ，更新当前的最高有效位。
- i i i 比 i − highBit i-\textit{highBit} i−highBit 的「一比特数」多 1 1 1 ，由于是从小到大遍历每个整数，因此遍历到 i i i 时， i − highBit i-\textit{highBit} i−highBit 的「一比特数」已知，令 bits [ i ] = bits [ i − highBit ] + 1 \textit{bits}[i]=\textit{bits}[i-\textit{highBit}]+1 bits[i]=bits[i−highBit]+1 。
- 最终得到的数组 bits \textit{bits} bits 即为答案。
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
int highBit = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) highBit = i;
bits[i] = bits[i - highBit] + 1;
}
return bits;
}
}
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n) 。对于每个整数，只需要 O ( 1 ) O(1) O(1) 的时间计算「一比特数」。
- 空间复杂度： O ( 1 ) O(1) O(1) 。除了返回的数组以外，空间复杂度为常数。
解法3 动态规划——最低有效位
方法二需要实时维护最高有效位，。如果再换一个思路，可以使用「最低有效位」计算「一比特数」。
对于正整数 x x x ，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉，得到的数是 ⌊ x 2 ⌋ \lfloor \frac{x}{2} \rfloor ⌊2x⌋ 。如果 bits [ ⌊ x 2 ⌋ ] \textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big] bits[⌊2x⌋] 的值已知，则可以得到 bits [ x ] \textit{bits}[x] bits[x] 的值：
- 如果 x x x 是偶数，则 bits [ x ] = bits [ ⌊ x 2 ⌋ ] \textit{bits}[x]=\textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big] bits[x]=bits[⌊2x⌋]
- 如果 x x x 是奇数，则 bits [ x ] = bits [ ⌊ x 2 ⌋ ] + 1 \textit{bits}[x]=\textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big]+1 bits[x]=bits[⌊2x⌋]+1
上述两种情况可以合并成： bits [ x ] \textit{bits}[x] bits[x] 的值等于 bits [ ⌊ x 2 ⌋ ] \textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big] bits[⌊2x⌋] 的值加上 x x x 除以 2 2 2 的余数。
由于 ⌊ x 2 ⌋ \lfloor \frac{x}{2} \rfloor ⌊2x⌋ 可以通过 x > > 1 x >> 1 x>>1 得到， x x x 除以 2 2 2 的余数可以通过 x & 1 x~\&~1 x & 1 得到，因此有： bits [ x ] = bits [ x > > 1 ] + ( x & 1 ) \textit{bits}[x]=\textit{bits}[x>>1]+(x~\&~1) bits[x]=bits[x>>1]+(x & 1)
遍历从 1 1 1 到 n n n 的每个正整数 i i i ，计算 bits \textit{bits} bits 的值。最终得到的数组 bits \textit{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 >> 1] + (i & 1);
return bits;
}
}
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n) 。对于每个整数，只需要 O ( 1 ) O(1) O(1) 的时间计算「一比特数」。
- 空间复杂度： O ( 1 ) O(1) O(1) 。除了返回的数组以外，空间复杂度为常数。
解法4 动态规划——最低设置位
定义正整数 x x x 的「最低设置位」为 x x x 的二进制表示中的最低的 1 1 1 所在位。例如， 10 10 10 的二进制表示是 101 0 ( 2 ) 1010_{(2)} 1010(2) ，其最低设置位为 2 2 2 ，对应的二进制表示是 1 0 ( 2 ) 10_{(2)} 10(2) 。
令 y = x & ( x − 1 ) y=x~\&~(x-1) y=x & (x−1) ，则 y y y 为将 x x x 的最低设置位从 1 1 1 变成 0 0 0 之后的数，显然 0 ≤ y < x 0 \le y<x 0≤y<x ， bits [ x ] = bits [ y ] + 1 \textit{bits}[x]=\textit{bits}[y]+1 bits[x]=bits[y]+1 。因此对任意正整数 x x x ，都有 bits [ x ] = bits [ x & ( x − 1 ) ] + 1 \textit{bits}[x]=\textit{bits}[x~\&~(x-1)]+1 bits[x]=bits[x & (x−1)]+1 。
遍历从 1 1 1 到 n n n 的每个正整数 i i i，计算 bits \textit{bits} bits 的值。最终得到的数组 bits \textit{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(n) O(n) 。对于每个整数，只需要 O ( 1 ) O(1) O(1) 的时间计算「一比特数」。
- 空间复杂度： O ( 1 ) O(1) O(1) 。除了返回的数组以外，空间复杂度为常数。