终于看懂了 java的 Integer.bitCount() 方法源码，超详细分析

柔情只为你懂 2023-02-16 04:12 36阅读 0赞

### 问题来源 ###

剑指Offer的一道题目：计算二进制表达里 1 的个数，题解在我的博客里：  
[剑指Offer 15题详解][Offer 15]  
但是发现 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;
    }

简单来说，源码非常非常巧妙的利用了 位运算的性质，大概我这辈子也想不到吧。

我们从最后的落脚点出发，或许更能理解这种思路：

return i & 0x3f;

0x3f 十六进制转为二进制是：

这时候我们想一下这行代码，对于 0x3f 来说，它和**变量 i** 做 **与** 运算，得到的最大结果也就是 0x3f 本身，也就是**二进制 111111** ，对应 **十进制是 63**。

这是什么意思呢？

对于 **输入 n** ，即使这个数字的二进制表达**占满了 32 位比特** 且全都是 1，那么这条语句的功能，数 1 的个数，结果最多也就是 32 ，对应二进制表达是 **100 000**，长度为 6 位。

所以这一点上，这种方法的计算过程保证了有效位足够，另一方面保证，最终返回的是 **前面计算结果的最后六位的值**，去掉了高位上面的干扰。

而这整个代码也都是基于这种思想的，逐渐**缩小有效位的范围**

我们先总结一下代码中的十六进制数：

接着一行一行来看代码。

#### 第一行代码 ####

i = i - ((i >>> 1) & 0x55555555);

我直接告诉你，它完成的功能叫做，**每两位**进行一次统计，统计 **1 的个数**，**并把结果放在对应的原来位置上**。

1.  i >>> 1 是将 i 无符号右移一位
2.  0x55555555 是 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
3.  右移后 和 0x55555555 进行按位与操作
4.  再用 i 减去 “3” 的结果

###### 上面的 “1” ######

想一想：对于一个 32 位的数 i ，右移一位之后，**第 2、4、6、……、32位的数字**，分别跑到了**第 1、3、5、……、31位**上，也就**对应到了** 0x55555555 的 **所有 1** 的位置。

###### 上面的 “2” 和 “3” ######

i 在右移之后和 0x55555555 进行 与 操作，就会得到原来 i 的第 2、4、6、……、32 位上的所有真实的值；**同时，第 1、3、5、……、31位上的值都和 0 进行与操作之后变成了0。**（到这里还看不出这么做的意义，别着急，看下一步）

###### 上面的 “3” ######

重点来了，接着用 i - （2 和 3 的结果）会发生什么事？

一个二进制两位的数字，可能的形式有：00,01,10,11.  
右移之后分别和 01 进行与运算，得到： 00,00,01,01.  
用原来的数减去右移后的，就能够得到： 00,01,01,10.

观察一下结果可以发现：**每两位的数值** 就表示了以前这两位上 **有 1 的个数**

（这里可以回头想一想，先和0x55555555 进行 与 操作是非常必要的，因为如果仅仅右移，第 3 位如果有 1，右移之后会占用第二位，会影响统计结果，因此必须把这些位都通过和 0 的与操作清零。）

#### 第二行代码 ####

i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

第二行和第一行的本质思路是一样的，进一步扩大范围，统计原始 i **每 4 位上 1 的个数**。

1.  0x33333333 是 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11
2.  i 和 0x33333333 进行按位与操作
3.  i 右移两位，再和 0x33333333 进行按位与操作
4.  将 “ 2 ” 和 “ 3 ” 的结果相加

###### 上面的 “1” 和 “2” ######

和 0x33333333 进行 与 操作，就会得到第一行代码运行之后 的第 1 2、5 6、9 10、……、29 30 位上的所有真实的值；**同时，第 3 4、7 8、11 12、……、31 32位上的值都和 00 与之后变成了00。**

###### 上面的 “3” ######

和只有 两位 的二进制数的减法性质不同，所以这里不能再使用减法。  
那么丢掉的那一半位置的数字还是需要找回来的。怎么办呢

i 右移两位，第 3 4、7 8、11 12、……、 31 32 位上的值跑到了 第 1 2、5 6、9 10、……、 29 30位上。此时再做了一边和 “2” 一样的事情，这就得到了第一行代码运行之后的第 3 4、7 8、11 12、……、 31 32 位上的真实的值。

###### 上面的 “4” ######

简单相加，功能完成。（直接相加不用考虑进位吗？答案是不用，原来的数字 每四位上面 1 的个数最多是 4 个，对应成二进制是 100 ，只会占用 3 个二进制位。）

可以回头想想。源数字 i 的 **每四位上面 1 的个数**，已经被统计出来了，替换在了对应的位置上。

#### 第三行代码 ####

i = (i + (i >>> 4)) & 0x0f0f0f0f;

这一步，要开始统计 原始数字 i **每 8 位上面 1 的个数**。我们可以看到代码的方式又变了。  
（和第二行写法不一样，但其实第三行可以写成和第二行一样的格式；第二行却不能写成第三行这样的形式，大家可以想想为什么）

1.  将 i 右移四位，再与 i 相加
2.  0x0f0f0f0f 的二进制表达是 0000 1111 0000 1111 0000 1111 0000 1111
3.  将第一步的结果 和 0x0f0f0f0f 进行与操作

###### 上面的 “1” ######

对其相加个数的时候，显然要以低位为准，所以第 5 6 7 8 、13 14 15 16、20 21 23 24、29 30 31 32 位的数字，挪到了 1 2 3 4 、 9 10 11 12、17 18 19 20 、25 26 27 28 位上，对应相加。

这里的加和，最多不会超过 8 ，对应二进制是 1000，（因为源数字 i 每 8 位上面 1 个数不会超过 8）所以直接加也不会产生错误。

###### 上面的 “2” 和“3” ######

和 0x0f0f0f0f 进行 **与** 操作，就会得到源数字 i **每 8 位上面 1 的个数**，存储在了第 1 2 3 4 、 9 10 11 12、17 18 19 20 、25 26 27 28位上。而第 5 6 7 8 、13 14 15 16、20 21 23 24、29 30 31 32 位一定是 0.

#### 第四行和第五行代码 ####

i = i + (i >>> 8);
    i = i + (i >>> 16);

这两行，完成的是一个功能，也就是把源数字 i 每 16 位上面 1 的个数，存储在了 1~16位上。（此时没有做第17~32位的清零）

当然，如果按照前几步的思路，你当然可以把这两行代码替换成：

i = i + (i >>> 8) & ‭FF00FF‬;

这行是我想的，但经过验证可以达到一样的效果，因为 ‭FF00FF‬ 的二进制表达是：  
‭0000 0000 1111 1111 0000 0000 1111 1111‬

不过显然原作者的做法更巧妙，毕竟直接右移16位就能达到效果。

#### 第六行代码 ####

return i & 0x3f;

回到最开始我们对这一步的分析，源数字 i 作为32位二进制数字，1 的个数就最多 32 而已。

那么代码的意义显而意见。  
最终就会返回 原始输入 i 的二进制形式上 **1 的个数**。

总结一下，如果这道题交给我们来做，即使是位运算，按位与 和 用了 n&(n-1) 这两种方法，最差的情况下都是要运行 32 次位运算的，但是底层源码的方法，却是恒定只进行 6 次计算。不得不说真实优秀。