Java源码 Integer.bitCount实现过程

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;

}

第一眼看这个代码，完全看不懂。
搜查资料之后才懂：
原来是先两个两个一组，求二进制1的个数，并且用两位二进制存储在原处，然后四个四个一组，求二进制位1的个数，再把它存储以4位二进制到原处。以此类推直到计算完成。不得不感叹这个算法设计的精妙之处。

Google了一番，没有查到为什么这个设计。知其然，不知其所以然。

于是，我决定模拟一下发明者的想法，为什么要这么算，怎么想到的，进行求解过程的分析：

想到面试题 5升和3升的杯子取 4升水这种问题了，这种题不就是利用加减法来回计算吗？利用已知的来求解未知的。

我们平时数数是不是喜欢一对一对的数啊？
先观察存储的情况：

src	store	remark
00	00	这两位没有，那就用0存储
01	01	这两位只有一个1，就用1存储
10	01	这两位也只有一个1,也用1存储
11	10	这两位有两个1，用10存储

那么就一对一对的数，已知 src列求出 store列？
列式计算：

设 λ = i - x
00 = 00 - 00;
01 = 01 - 00;
01 = 10 - 01;
10 = 11 - 01;

那么 x 又如何通过i得到呢？

我们手无寸铁，对CPU来说也只有加法和移位的手段。假如发明者列出这种算式，敏感的他一下子
很容易看出来：
x=i>>>1
就这么简单
那么得到：
λ = i - (i>>>1)

那么i不止两位怎么处理？如果这个是最后的两位，那么移位之后后面一位二进制可以抹掉
而前面的移位会影响后面的最高位，那么把移出去的那一位消除：
i>>>1 & 01；
即为：01010101 01010101 01010101 01010101
λ = i - (i>>>1 & 0x55555555)

问题解决。
那么计算了两位的如何计算4位的二进制位呢？
枚举第一步计算完成的所有的情况：

src	target	remark	ref
0000	0000	= 0000 & 0011
0001	0001	= 0001 & 0011	01 = 01 & 11
0010	0010	= 0010 & 0011	10 = 10 & 11

0100	0001	= 01 + 00
0101	0010	= 01 + 01
0110	0011	= 01 + 10

1000	0010	= 10 + 00
1001	0011	= 10 + 01
1010	0100	= 10 + 10

后面两组可以参照第一组的结果，那么可以推算
四位中低两位 bb = aabb & 0011，主要要计算与高两位的和：
已知可以用1100& aabb =aa00得到左边的值，但是多了两个00，那么要计算aa + bb：
可以 aabb>>>2 = 00aa(bb)只看这两位，移位多出去的被00消除，不影响后面的计算。
即:
λ =( i & 0x0011) + (i>>>2 & 0x0011)
也就是:
λ =( i & 0x33333333) + (i>>>2 & 0x33333333)

同理求8位里面的两边4位之和：
λ =( i + i>>>4) & 0x0F0F0F0F

求16位的两边之和：
λ = i + (i >>> 8);
由于二等分是8位，而8位一共有4份。
A B C D

(C>>>8) + D D处8位的结果最大为 0001 0000不会进位到C。
(B>>>8) + C C处8位的结果最大为 0001 0000不会进位到B。
(A>>>8) + B B处8位的结果最大为 0001 0000不会进位到B。
A + 0 A处最大结果为 0000 1000

得到
A A+B B+C C+D
最后是求32位全部的内容也就是求(A+B)+(C+D)
A A+B B+C C+D
+
0 0 A A+B

也就是
λ= i + (i >>> 16)
A A+B A+B+C A+B+C+D
A+B+C+D最大也就32个：
0000 0000 0000 0000 0000 0000 0010 0000
0000 0000 0000 0000 0000 0000 0011 1111 = 0x3F
之所以要return i&0x3F，就是把前面抹干净。

巴特西

Java源码 Integer.bitCount实现过程

最新文章

热门文章