Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints:
0 <= n <= 105
Follow up:
It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
思路一: 辗转相除法，统计 1 的 bit 总数
public int[] countBits(int n) {
int[] result = new int[n + 1];
for (int i = 0; i <= n; i++) {
int count = 0;
int temp = i;
while (temp > 0) {
if ((temp & 1) == 1) count++;
temp >>= 1;
}
result[i] = count;
}
return result;
}
思路二：动态规划，需要计算的数字完全分类，只可能出现下面两种情况
- 奇数
- 偶数
奇数只会比它小的偶数多一位 1 bit, 偶数和比它小一半的数字 1 bit 位一样
例如 1 比 0 多一位 bit，6 和 3 的 bit 位数量一样。思路非常巧妙
public int[] countBits(int n) {
int[] result = new int[n + 1];
result[0] = 0;
result[1] = 1;
for (int i = 2; i <= n; i++) {
if ((i & 1) == 1) {
result[i] = result[i - 1] + 1;
} else {
result[i] = result[i >> 1];
}
}
return result;
}