计算二进制数有几个1

by: dick 林敏悦 2019-12-16

保护私人版权，尊重他人版权。转载请注明出处并附带页面链接

JDK源码中有个方法计算一个int数有多少个bit位，充分利用了位运算提高效率。

大体思路：先按2位分组，计算2位分组的个数存放在2位上，再按4位分组，计算4位分组的个数存放在4位上，反复直到按16位分组即可。

code如下：

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）i = i - ((i >>> 1) & 0x55555555)

这行代码较其他行代码有点特别，不太好理解，是利用了二进制数的规律。

例如1111111111111111111111111111111（即int的最大值，0x7fffffff），右移1位得到0111111111111111111111111111111，和0x55555555相与得到10101010101010101010101010101，与原数相减得到1101010101010101010101010101010，对1101010101010101010101010101010进行分组得到

1 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10

10二进制代表2，表示这个分组有2个1（刚好一减就是，数字真的是很奇妙）。

（2）i = (i & 0x33333333) + ((i >>> 2) & 0x33333333)

i&0x33333333 ，因为3是0011，所以是取上一行代码的后一个分组，目的是与((i >>> 2) & 0x33333333)的结果相加把1的个数存放在后一个分组。例如继续上一步的计算结果，得到

11 | 0100 | 0100 | 0100 | 0100 | 0100 | 0100 | 0100

可以看出是每4位为一个分组，并且将4位上1的个数进行计算并存储。

（3）i = (i + (i >>> 4)) & 0x0f0f0f0f

这行代码含义同上。需要注意的是一个是分别拆开&运算后相加，一个是相加后直接进行&运算，因为16进制是每4个2进制位为1位，所以4位以上的可以直接先进行相加，而4位以下的这样操作会造成运算错误。继续上一步的计算结果得到

111 | 00001000 | 00001000 | 00001000

（4）i = i + (i >>> 8)

因为0x0f0f0f0f已经取了4位，再翻一次就是取8位，就是&0xffffffff，可以省略不写。继续上一步的计算结果得到

111 | 00001111 | 00010000 | 00010000

（5）i = i + (i >>> 16)

同上，而且没得再翻。继续上一步的计算结果得到

111 | 00001111 | 00010111 | 00011111

（6） i & 0x3f

因为int最多32位，1位为符号位，所以最多是31位，则& 0x3f（111111）即可。