一道简单算法题扩展

最近刷了一道算法题，大意是：

计算一个整数数字的二进制表示法中1的个数，比如数字3，二进制是011,则1的个数是2。

如果没刷过该题目的同学，也可以自己想一想，有没有思路呢？

后面我想了下，大致思路就是循环判断该数字最低位是否是1即可，然后无符号右移1位，再判断最低位是否是1，直至该数字变为0。判断最低位是否是1，只要用数字n&1即可。

有了思路，代码实现很简单：

public static int bitCount(int number) {
        int count = 0;
        while (number != 0) {
            if((number & 1) == 1) {
                ++count;
            }
            number >>>= 1;
        }
        return count;
}

嗯，确实比较简单，基础的位运算而已，如果到这里就结束，肯定就“Too Naive”。因为我想起来在Java的Integer类中，有现成的方法可以用，只是做些算法题的时候，肯定还是要用自己的思路来实现。既然是Java的实现，那就拿出来看看，也可以做到取长补短，学习“大佬”的实现思路，代码贴出如下：

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;
}

乍一看，What the F*#k。再一看还是没有思路，不过还是有些规律看的出来，0x55555555，0x33333333，0x0f0f0f0f都比较特殊，用二进制表示：

// 0x55555555
0101 0101 0101 0101 0101 0101 0101 0101
// 0x33333333
0011 0011 0011 0011 0011 0011 0011 0011
// 0x 0f0f0f0f0f
0000 1111 0000 1111 0000 1111 0000 1111

那么先看第一步： i = i – ((i >>> 1) & 0x55555555); 无符号右移一位，然后“与”上0x55555555;

//假设初始的数字二进制表示为（总共32位）：
N31 N30 N29 N28 N27 N26......N4 N3 N2 N1 N0 
// 右移一位之后，高位补0，所以就变成了：
0 N31 N30 N29 N28 N27 N26......N4 N3 N2 N1
// 再经过和0x55555555“与”运算之后，则相当于保留了所有的奇数位。其余的位都置为了0
0 N31 0 N29 0 N27 0 N25......0 N5 0 N3 0 N1

这里注意下，经过上面两步运算过后，再用原来的数，减掉变换后的值，会出现什么效果呢？

  N31 N30 N29 N28 N27......N5 N4 N3 N2 N1 N0
-  0  N31  0  N29  0 ......0  N5 0  N3 0  N1
_____________________________________________
                                          ？

好像有些规律，仔细想想，刚好把32位，可以分成每两位一组做减法，就拿最低2位举例子：

  N1 N0
- 0  N1
————————
​

上面又分4种情况来说明:

N0	N1	Result
1	1	10
1	0	01
0	1	01
0	0	00

从这个表中仔细发现，“Result”就代表着这两位中1的个数。

所以以此类推其它的位，每两位的1的个数，就存储在这两位中，因此经过代码第一步运行之后，i就保存着1的个数的结果（虽然是每两位的结果来存储的）。

OK，到这里算是比较明朗了，接下来再看第二步：i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

// 还是假设第一步执行后的结果，如下所示
N31 N30 N29 N28 N27......N5 N4 N3 N2 N1 N0
​
// i"与" 0x33333333之后，就变成了
Result1: 
0  0 N29 N28 0 0 N25 N24......N5 N4 0 0 N1 N0
​
//i右移两位，再于0x33333333，就变成了
Result2: 
0  0 N31 N30 0 0 N27 N26......N7 N6 0 0 N3 N2
​
// 最后用Result1 和 Result2 相加
  0  0 N29 N28 0 0 N25 N24......N5 N4 0 0 N1 N0
+ 0  0 N31 N30 0 0 N27 N26......N7 N6 0 0 N3 N2
————————————————————————————————————————————————
​

所以那经过第二步运行之后，结果有什么规律呢？所以想一下，其实很明显了，就是第一步的结果i，每4位相加，再结合我们第一步的分析，所以就是每两位1的个数，变成了每4位1的个数。

到这里总算豁然开朗，我们已经猜测到了作者的思路：就是把1的个数结果存储在位本身上。Nice~

再看第三步： i = (i + (i >>> 4)) & 0x0f0f0f0f;

// 同样假设第二步执行后的结果，如下所示
N31 N30 N29 N28 N27......N5 N4 N3 N2 N1 N0
​
// i 右移4位，再“与”上 0x0f0f0f0f
0 0 0 0 N31 N30 N29 N28 0 0 0 0 N23 N22 N21 N20......0 0 0 N7 N6 N5 N4
​
// 两个结果相加
  N31 N30 N29 N28 N27 N26 N25 N24 N23 N22......N7 N6 N5 N4 N3 N2 N1 N0
+ 0   0   0   0   N31 N30 N29 N28 0   0  ......0  0  0  0  N7 N6 N5 N4
—————————————————————————————————————————————————————————————————————————

那么这里其实也是同理，就是每4位1的个数累加，变成了每8位1的个数，存储在8位二进制上，由于4位二进制最大可以表示15，足够表示8位二进制上1的个数的总数，所以高四位就没有像第二步和第一步那样变成0方式处理。这样可以节约两个步骤。小细节上确实到位。

到这里，其实后面的两步就差不多了，感兴趣可以自己推演一下。

最后一步由于32位的1的个数，只需要6位来存储，所以最后结果 “&0x3f” 来消除高位的脏数据，最终就完成了。

一个简单的位运算，从思路转变成代码实现，却能高效的实现，不佩服都不行！我相信作者也是经过了反复推敲，才最终展现给我们看到的代码样子。就像阅读作者Doug Lea的Concurrent包下的源码，简洁干练，没有废话。

这也提醒我们，对于自己写过的代码，要经常回过头review，重构，优化。中间必定会有大量的思考，我相信，这些思考最终会变成技术的积累。但比较遗憾的一点是，现实中，我们大多都被KPI，被项目的快速进度所逼迫，没有时间去好好的揣摩自己的代码。