题目：
给定一个非负整数 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
说明 :
0 <= n <= 105
代码：
package jianzhioffer;
import java.util.Arrays;
public class offer_03 {
public static void main(String[] args) {
System.out.println(Arrays.toString(countBits(3)));
}
public static int[] countBits(int n) {
int[] array = new int[n+1];
for (int i = 0; i <= n; i++) {
array[i] = (i % 2 ==0) ? array[i >> 1] : array[i - 1] + 1;
}
return array;
}
}
解题思路：
此题，我们可以将所有的数分为奇数和偶数来处理：
? ? ? ? 如果当前num为奇数，则二进制中1的个数为前一个数二进制1的个数+1。 当前数为奇数，代表前一个数为偶数，所以前一个数的二进制最后一位一定是0，当前的数就是在它原来的基础上加了个1。例如，5(101)，上一个数为4(100), 5 = 4 + 1, 加上的1就是加到了二进制中的最后一位。
? ? ? ? 如果当前num为偶数，则二进制中1的个数为 num/2 的二进制中1的个数。 这一灵感来源于位运算。例如 (1)0001 左移一位后变为 2(0010)，2(0010)左移一位后变为4(0100)，他们1的个数都是不变的，只是位置在变化。
参考链接：
前n个数二进制中1的个数
|