Integer.bitCount解析后篇

前几天, 写了篇《为什么连Integer的源码都这么难读懂》。提到了Integer核心源码其实并不复杂，但是Integer同时兼任了一个工具类的职责。1800行代码里有大量都是工具方法。并且试图解析了下bitCount这个函数的历史渊源和推演.

结果不太令我自己满意，今天重新写一遍。

IBM1960年在硬件级别提供了硬件支持可以计算出一个字 里有多少个1的方法, 俗称population count. 没有这种原生时候能力时候, 人们会采用自己的算法来实现这个人口普查功能.

通过引入分治法, 思路很明显,

一个求32bit的运算, 可以拆成2个求16bit运算的和.
一个求16bit的运算, 可以拆成2个求8bit运算的和
一个求8bit的运算, 可以拆成2个求4bit运算的和
一个求4bit的运算, 可以拆成2个求2bit运算的和
一个求2bit的运算,可以拆成2个求1bit运算的和

这个复杂度明显是的.

有了思路, 实现起来也不复杂.

取出低位
取出高位右移这步等价于, 右移取出低位
相加

人们推导出了一种通过如下公式来获取32bit长度下结果:

x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >>> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >>> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >>>16) & 0x0000FFFF);

这几个掩码看着很奇怪, 我把他们画成小黑块放到上图上, 就明显了.

黑色部分的值会全都被丢掉. 如果把另一半用红色来表示的话, 这个图是这样的.

这些格子, 黑色用0,红色用1表示, 可以得到:

01010101010101010101010101010101 对应的就是0x55555555
00110011001100110011001100110011对应0x33333333
00001111000011110000111100001111对应0x0F0F0F0F
00000000111111110000000011111111对应0x00FF00FF
00000000000000001111111111111111对应0x0000FFFF

好了, 到了这一步,能理解掩码是哪来儿的了. 但是这个式子, 离日常使用的还有一些差距.

下面来谈, 这个公式, 怎么实际简化成日常使用的版本

x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >>> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >>> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >>>16) & 0x0000FFFF);  

  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句简化

前半部分x & 0x55555555记为a,事实上, 是数x的低位部分
后半部分(x >>> 1) & 0x55555555记为b, 事实上是数x的高位右移1位.(相当于除以2)

2b+a 高位+低位,其实就是数x本身.有了这个式子x=a+2b以后, 再来看第1句的原句:

(x & 0x55555555) + ((x >>> 1) & 0x55555555);

可以改写为 a +b = a+2b-b=x-b,就得到了, x = x - ((x >>> 1) & 0x55555555);这个写法.

第2句没法简化,第3句是把掩码操作抽出来, 节省了一次&操作.

第4,5句我们要求的是一个32bit数字里1的数量. 这个数量,最大不会超过所能表达的范围. 6个bit就够了. 在这两步里, 分组都已经达到了8,16大小,超过了6. 高位不会存在有效值. 最后一步,使用 i&0x3f, 0x3f对应的二进制是0b000000000000000111111只保留了最后6位数字,前面的一口气去掉,节省了3次&操作.

最终得到的就是今天看到的公式了.

写完我上网搜了下别人怎么介绍这个公式的. 感觉写的比我好多了, 真尴尬. 顺便在这里推荐一下.