bitCount(int i) 函数，实现统计一个数的二进制位有多少个 1 。如 5 的二进制为 101，返回 2。
Jdk1.8 源码如下。初看一脸懵逼，再看还是一脸懵逼，分析 2 小时后，轰然开朗，遂有此文。
public static int bitCount(int i) {// HD, Figure 5-2i = 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;}
基础知识
& 与操作：a & b， a 和 b 都为 1 结果为 1，否则结果为 0。可以用来取固定区间的值，比如 1001 1100，取前 4 位 1001 1100 & 1111 0000 = 1001，取后四位 1001 1100 & 0000 1111 = 1100。“>>>” 和 "<<< "：无符号右移和无符号左移。(涉及到负数如何表示，不在此文范畴)代码中的十六进制数的二进制表示如下从结果入手
int 占 4 个字节，从左往右用 C1，C2，C3，C4 表示这 4个 字节。入参 i 用 C1，C2，C3，C4 表示，i 经过一系列运算后，用 D1，D2，D3，D4 表示。
由返回值i & 0x3f可知，参与运算的只有 D4 并且 D4 的后六位就是结果值。为什么只 D4 的后六位就是结果呢？ 答案在最后两行代码
i = i + (i >>> 8);// 第一行i = i + (i >>> 16);// 第二行
最后两行代码的逻辑如下图：一个字节 8 个 bit 位，右移 8 位就是移除最后一个字节，同理右移 16 位就是移除最后两个字节。这 2 行代码执行完后，D4 的值其实是 D1 + D2 + D3 + D4，所以只取 D4 参与运算并返回就行。
分治思想
时间线回到最后两行代码之前，D1，D2，D3，D4 代表着什么？为什么相加就是结果呢？结论：D1 表示 C1 里面有多少个 1 。同理 D2、D3、D4 表示 C2、C3、C4 分别有多少个 1 。所以 D1 + D2 + D3 + D4 能作为结果返回。那么 C1 如何转到 D1 呢？，这就是前三行代码做的事i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);i = (i + (i >>> 4)) & 0x0f0f0f0f;
假设 C1 是 10110011。不妨换个角度看待 C1 每一位 bit 的意义：每一位 bit 表示这个 bit 位有多少个 1。看起来好像是废话，bit 位是 1 表示这一位有一个 1，bit 位是 0 表示这一位有零个 1 。第一行代码执行后，这种思想变得有意义了。用两位是表示这两位有多少个 1， 比如前两位 10 可以用 01 表示这两位有多少个 1，三四位 11 可以用 10 表示这两位有多少个 1，以此类推。第一行代码执行后 C1’ = 01 10 00 10，表示一二位有一个 1，三四位有两个 1，五六位有零个 1 ，七八位有两个 1。第二行代码执行后 C1’’ = 0011 0010，表示前四位有三个 1，后四位有两个 1。第三行代码执行后 D1 = 00000101，十进制是 5，可以直接作为子结果和 D2、D3、D4 相加并返回了。
执行流程如下：
前三行代码理解
最后两行代码前面已经分析过。前三行代码的效果我们也已经知道了，但是如何达到上述效果还是一脸懵逼，换一个等价写法方便理解，当然源码的效率要高。源码：i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);i = (i + (i >>> 4)) & 0x0f0f0f0f;等价写法：i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
依然以 C1 = 10110011 为例，每一个 bit 代表一个区间，对应之前的废话：bit 位是 1 代表这一位有一个 1，bit 位是 0 代表这一位有零个 1。区间 1 至 8，方便描述把奇数位置叫「奇数区间」，偶数位置叫「偶数区间」。第一行代码的加号前求得偶数区间的 1，加号后求得奇数区间的 1，相加等于合并了相邻的「奇偶区间」，把C1的区间缩小为 4 个。同理第二行代码把区间缩小为 2 个，第三行代码把区间缩小为 1 个。基于此，完成 C1 到 D1。整个过程其实就是一个逆序的分治～
最后，上述流程可以在纸上画一遍，一目了然。
