给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
示例 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
两种方法，一种就是对每一个数字进行处理，另一种就是使用动态规划
public int[] countBits(int n){
// 大小为n+1是因为还有0
int[] res = new int[n+1];
for(int i = 0;i < n+1;i++){
res[i] = getOne(i);
}
return res;
}
public int getOne(int n){
int res = 0;
while(n != 0){
// 这一步是可以将二进制中最后一个1转化为0
n = n&(n-1);
res ++;
}
return res;
}
代码解析：我们想要知道一个二进制数中1的个数，我们除了对每一位的数字进行判断以外，我们还可以使用Brian Kernighan 算法，这个算法当n&（n）-1的时候，得到的结果是将n最低位的1转化为0
例如：
n = 3;
n的二进制表示：11
n-1的二进制表示：10
n&（n-1） = 10
10相较11，最右边的1变成了0
如果再次转化
10&01 = 00
public int[] countBits(int n){
// 大小为n+1是因为还有0
int[] res = new int[n+1];
res[] = 0;
for(int i = 1;i < n+1;i++){
if(i%2 == 0){
res[i] = res[i>>1];
}else{
res[i] = res[i-1] + 1;
}
}
return res;
}
代码解析：通过对二级制数的分析，我们可以发现，奇数中二进制数种1的个数为当前奇数前一个偶数中个数+1（因为和偶数只是最低位多了一个1），偶数中个数和将当前偶数右移一位的偶数是一样的（因为多的一位是最低为，一定为0）
Brian Kernighan 算法：n&（n-1） = n将最右边的1转化为0得到的结果
二进制中1的个数的规律：奇数等于前一个偶数数目加一，偶数和当前偶数右移一位相同。
Original: https://www.cnblogs.com/foldn/p/16025580.html
Author: foldn
Title: 前n个数字种的二进制数中的1的个数
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/579738/
转载文章受原作者版权保护。转载请注明原作者出处！