AlgoPressAppearance
题目描述
https://leetcode.cn/problems/counting-bits
给你一个整数 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 ）
思路：常规解法
使用右移统计数字个数
参考代码
csharp
public class Solution {
public int[] CountBits(int n) {
int[] result = new int[n+1];
for(int i=0; i<=n;i++){
int sum = 0;
int num = i;
while(num > 0){
sum += num & 1;
num = num >> 1;
}
result[i] = sum;
}
return result;
}
}
进阶思路：高位法
因为只能O(n)循环，所以后面的数字需要从前面的结果中得出来。 每个数字的二进制表示都可以拆分为最高位的1和后面的数字，所以他的1的个数，就是 后面输的1的比特数+1。 比如： 13 = 1101 的比特数是3， 他就是 1 + (101的比特数) ， 而101的比特数就是2，即： result[13] = result[5] + 1 那么如何得到当前数字的高位数呢，我们再循环i的时候，用 i 和 i-1 做逻辑与运算，当发现是 0 的时候，说明找到了高位。 如 1000 & 0111 ，只有一种情况，即最高位是1后面都是0的时候，减去1，第一位是0，后面的位数都是1，此时相与位0。
参考代码
csharp
public class Solution {
public int[] CountBits(int n) {
int[] result = new int[n+1];
int highBit = 0;
for(int i=1; i<=n;i++){
if( (i & (i-1)) == 0 ){
highBit = i;
}
result[i] = result[i-highBit] + 1;
}
return result;
}
}
进阶思路：奇偶法
任何数字要么是奇数，要么是偶数 当一个数字是奇数是，他的最后一位一定是1，他的比特数其实就是他前面的一个偶数的比特数 + 1 当一个数字是偶数是，他的最后一位一定是0，他的比特位数其实就是将他右移一位的比特数。 所以这样我们可以利用后面的比特数不停的从前面的结果中得出来
参考代码
csharp
public class Solution{
public int[] CountBits(int n){
int[] result = new int[n+1];
for(int i=1; i<=n; i++){
if(i % 2 == 1){
result[i] = result[i-1]+1;
}
else{
result[i] = result[i/2];
}
}
return result;
}
}
//上面 result[i-1] 其实是和 result[i/2] 相等的，因为最后一个数字是0, 所以等式可以简化为
result[i] = result[i/2] + i % 2;
进阶思路：最低设置位
任何一个数 i 与 i-1 想与之后，他的有效比特位的个数会减1，利用这个特性我们可以使用前面已经得到的结果+1
参考代码
csharp
public class Solution{
public int[] CountBits(int n){
int[] result = new int[n+1];
for(int i=1; i<=n; i++){
result[i] = result[i&(i-1)]+1;
}
return result;
}
}