给定一个十进制，统计其二进制表示中1的个数。
- 解法一：
public int NumberOf1(int n) {
int flag = 1, count = 0;
while(flag != 0) {
if((n & flag) != 0) {
count ++;
}
flag = flag << 1;
}
return count;
}
使用一个辅助变量，初始值是1，也就是2的0次方，不断左移，并且与n进行与操作，这样就可以判断n从右往左各bit位上是否为1。进而得到问题的解。
- 解法二：
public int NumberOf1(int n) {
int count = 0;
while(n != 0) {
count ++;
n = n & (n - 1);
}
return count;
}
这种解法应用了一种巧妙的思路:n与n-1进行与操作，会消除n二进制中最右边的一位1。我们可以简单的思考一下，假如n的二进制中最后一位是1，那么减去1之后，最后一位变成了0，其他位不变，满足上面的结论；如果最后一位是0，那么减去1后，就相当于从右往左数，第一位非0也就是1的位置开始，所有位按位取反，此时再与n做与操作，也是正好把从右往左的第一位1消除掉。结论得到证明。
- 解法三：
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
第三种解法就是jdk里面给出的大神级实现了(Integer类里的静态方法)。开始以为应该会用解法二的解法就ok了。但是这里给出了一种看似更为"复杂"的方法。让我们来看一下。
这种方式总体的思路有点类似于分治-合并的思路。两两一组统计组内1的个数(分治)，然后量量一组合并求和，直到全部求和完毕，得到整个二进制串中1的个数。让我们来逐行看一下源码。我们用666这个十进制作为例子，debug一下这个方法的每一行。666对应的二进制为:
0000 0000 0000 0000 0000 0010 1001 1010
第一行:这一行应该是这个方法中最关键也是最难以理解的一行，两两一组，求组内1的个数。直接看的话，这个减操作还是很迷的。我们先来看一下每两位一组，原值与二进制中1的个数的真值表。（这个地方的思路，是百度了下jdk这个源码的讲解，看了某位大神的博客后，回来自己debug的。知识产权值得保护，下次再看到这的时候，补充下想法的来源。）
| 原值 | 1的个数(二进制) | 操作过程 |
|---|---|---|
| 00 | 00 | 00 - 00 = 00 |
| 01 | 01 | 01 - 00 = 01 |
| 10 | 01 | 10 - 01 = 01 |
| 11 | 10 | 11 - 01 = 10 |
由于是每两位一组，因此真值表中原值只有4个值。对应的1的个数在第二列。下面就是见证奇迹的时刻了。我们发现，第二列的值，是第一列的值作为被减数，第一列右移一位的值作为减数求差的结果，也就是 i - i>>>1。有了这个公式，再来看第一行的操作，就比较好理解了。0x55555555对应的二进制为 0101 0101 0101 0101。i右移一位，再与一下0x55555555的话，就相当于是右移之后，再把组内的 第一个数字给消除掉，即构造我们上面公式的减数。举个例子，如果原数是1111，右移一位的话是0111，分成两组为(01)(11)，与一下0x55555555，得到我们期望的减数(01)(01)。至此，减数被减数都有了，第一行执行完毕，得到的二进制串就是每两位中1的个数。ps:这一步一共分成了16组(32/2)。
step1:右移一位
0000 0000 0000 0000 0000 0001 0100 1101
step2:与一下0x55555555
0000 0000 0000 0000 0000 0001 0100 0101
step3:用被减数(666)减一下上面的结果
0000 0000 0000 0000 0000 0001 0101 0101
第二行:从这一行开始，就是求和了。第二行是相邻两组合并。如果我们给分组编号，1-16组，那么+号前面的是保留组号2、4、6、8...16的分组。+号后面的操作是将1、3、5、7...15的分组，首先移动到2、4、6、8...16组的位置上，然后将其他位置清0，这样就跟+号左边的对齐了，然后做加法。
step1: 保留2、4、6...
0000 0000 0000 0000 0000 0001 0001 0001
step2:右移两位,保留2、4、6、8..
0000 0000 0000 0000 0000 0000 0001 0001
step3:求和
0000 0000 0000 0000 0000 0001 0010 0010
第三行:每四个一组求和。
step1: i + i>>>4
0000 0000 0000 0000 0000 0001 0011 0100
step2: &0x0f0f0f0f
0000 0000 0000 0000 0000 0001 0000 0100
第四行:每8个一组求和。
0000 0000 0000 0000 0000 0000 0000 0101
第五行:每16个一组求和
0000 0000 0000 0000 0000 0000 0000 0101
第六行: 获取最后结果。因为int是4字节，32bit，最多也就32个1，所以最终结果最大值为32(2^5),即为 0010 0000，所以取6位即可，0x3f就是这么来的。
00 0101（二进制） = 5（十进制）
- 总结
该方法总共5次无符号位移操作，5次与操作，4次加法操作，一次减法操作，总共15次计算。解法二的话，最坏场景的操作数是: 32*(1次加法+ 一次减法 + 一次与操作) = 96次操作。虽说都是常数级的操作，但是应该jdk的实现复杂效率更高一些。后面考虑怎么证明一下该方法的效率比方法二高。
网友评论