题目：
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
解答：
解法一（直接转化）：
使用java中自带的Integer.toBinaryString方法，将int型的整数转化为二进制形式的字符串，之后通过将字符串中的“1”替换为空字符串“”，字符串替换前后的长度差就是该整数中包含1的个数。
class Solution {
public int[] countBits(int n) {
int[] result = new int[n + 1];
for (int i = 0;i <= n; i ++) {
String binary = Integer.toBinaryString(i);
result[i] = (binary.length() - binary.replace("1", "").length());
}
return result;
}
}
解法二（简单使用Brian Kernighan算法）：
Brian Kernighan 算法的原理是：对于任意整数 i，令，该运算将 i 的二进制表示的最后一个 1 变成 0 。借助Brian Kernighan算法，可以对于二进制中 1 的数量进行快速计算。
class Solution {
public int[] countBits(int n) {
int[] result = new int[n + 1];
for (int i = 0;i <= n; i ++) {
int j = i;
while (j != 0) {
j &= j - 1;
result[i] ++;
}
}
return result;
}
}
解法三（深入使用Brian Kernighan算法）：
将
的二进制形式最右边的 1 变成 0 ，也就是说，整数
的二进制形式中1的个数比
的二进制形式中 1 的个数多 1 。于是根据此规律可以有解法三。
- 解法二对于Brian Kernighan 算法的应用比较简单，如果一个整数有
位，那么他的二进制形式中可能有
个 1 。而解法二中while循环对每个整数将执行
。
- 解法三不管整数
的二进制形式中有多少个1，其只根据
的时间就能得出整数
。
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;
}
}
解法四（奇偶性判断）：
如果正整数是偶数，那么
相当于将
左移一位的结果，因此偶数
和
在二进制中 1 的个数是相同的。如果
是奇数，那么
相当于将
左移一位之后再将右边设为 1 的结果，因此奇数
中 1 的个数比
中多 1。
class Solution {
public int[] countBits(int n) {
int[] result = new int[n + 1];
for (int i = 1;i <= n; i ++) {
result[i] = result[i >> 1] + (i & 1);
}
return result;
}
}
