为什么连Java Integer的代码都这么难看懂?

1Integer 怎么这么复杂?

Integer 类在理论上, 应该是最简单的一种类,他就是int的包装.一个private final int value;就应该足以代表Integer的核心了.

但是打开java.lang.Integer实现, 为什么会这么复杂.. 有 1800 多行? 看起来一脸懵,这都写的啥??

这是因为, Integer 除了是一个包装类, 他同时还提供了String和int之间的相互转换,以及其他实用方法. 他还是个utility,就是熟悉的util.

作为一个工具类的Integer,代码量早已多过了作为包装类的Integer.而这些工具属性的方法, 往往很多都是穿越了整个计算机历史的人类文明结晶. 看不懂是非常正常的.

我今天差不多花了一下午时间,查找了一个算法相关的资料, 初步看了一点java.lang.Integer上的一个 6 行的小方法. 现在来尝试解释一下这方法究竟在干啥.

2Integer.bitCount(int i)

今天看的方法叫bitCount. 功能是, 计算一个int的二进制补码格式表示里,有多少个 1.

如果我自己写的话,不考虑性能, 最顺手的写法可能是这样:

Integer.toBinaryString(i)
.chars().filter(x -> x == '1')
.count();

考虑一点性能, 可能用位运算,这么写:

int n = 0;
for (int j = 0; j < 32; j++) {
    if((i &1)==1){
        n++;
      }
    i = i >>> 1;
}

写完拿标准库对了下答案. 直接懵了, 这啥??标准库里确定不是乱码?

标准库代码如下

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;
    }

我丝毫不怀疑标准库代码的实现是对的. 只是在想为什么这么写能起作用, 这里面的数字都哪里来的.

3探寻bitCount迷踪

唯一的线索, 是这行注释// HD, Figure 5-2

看起来, 这是某本书或者文章的5章第二幅插图. 但是, 这是什么书呢?

一通搜索和查询以后, 我发现, 答案就是在谜面上.

类的开头写了:《Hacker's Delight》. 这个就是HD.

4《Hacker’s Delight》

这是什么书? 能出现在JDK注释里的书, 可都不是一般东西.

然后, 我去豆瓣一看..发现这是一本2002年的作品.这书名咋翻译啊. 能让黑客高兴?

接着, 发现这书2004年出过中文版了. 名字叫:《高效程序的奥秘》

看来, 开发者是看过这书了. 那这幅5-2图是啥?

5HD 5-2

老K找到了这本书. 发现,5-2其实就是这个公式.

int pop(unsigned x) {
 x = x - ((x >> 1) & 0x55555555);
 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 x = (x + (x >> 4)) & 0x0F0F0F0F;
 x = x + (x >> 8);
 x = x + (x >> 16);
 return x & 0x0000003F;
}

在java里, 无符号右移是>>>, 就多了这么一个改动. 基本算是照搬了这个算法. 这个函数有个学名,叫population count.

中国人其实挺熟悉这个的.去年刚刚搞了第七次. 俗称人口普查.

6`population count`

这个函数的来源是哪里呢, 也不是这本书. 5-1部分写了, 这个统计1的功能,最老起源于1960年的IBM.

The IBM Stretch computer (ca. 1960) had a means of counting the number of 1-bits in a word as well as the number of leading 0’s. It produced these two quantities as a by-product of all logical operations! The former function is sometimes called population count (e.g., on Stretch and the SPARCv9).

7HD 5-1

想理解实现算法, 其实最快的方法不是看5-2,而是去看5-1. 这个看起来很神奇的算法, 其实是基于分治思想的.

好奇这个算法的,可以去看原书了. 下面就是我自己尝试的解释了.

88bit版本

这里我使用一个8bit的版本来做解释.

假如说, 现在我们有8个bit待统计

可以按照2个一组, 分为4组,每一组单独计算有多少个1.

很明显, 每组最多有2个1. 最大也就可以统计出2,最小是0.

二进制的2, 2个bit就可以表示出来, 应该是这样的:

对于统计bit这件事来说, 进行这个转换,并不会丢失数量信息.10就是2, 这里有4个组,每组都记为10即可.

如果继续进行按照4个bit一分组的方式, 那么可以得到这么个结果.

那么这里继续下去,组越分越大. 左右各两个4, 那么只要合起来,就可以得到最终的统计结果.

完整流程

9公式时间

有了口头的描述, 那么公式呢? 怎么实现?

当然还是位运算.分别取出一组内左边bit和右边bit加起来即可.

掩码

取出每组低位bit的方法,当然是把高位遮掉, 低位则是把高位遮掉.这个遮盖bit的东西, 叫 掩码(mask)

保留低位, 掩码用的数字应该是0b10101010,十六进制的表示是,0xaa.
保留高位, 掩码用的数字应该是0b01010101,十六进制的表示是,0x55.

2个bit分一组,求法应该是:

n&0xaa>>>1 + n&0x55

但是, 这里有个小问题, 用了两个掩码会吃内存, 一般会选择先右移只使用一个0x55来操作. 这个写法等价于

n>>>1&0x55+n&0x55

同理可推得, 4个bit一组的求法是:

n>>>2&0x33+n&0x33

8个bit一组的求法是

n>>>4&0x0f+n&0x0f

累计起来, 8bit的算法是这样的.

n = (n >>> 1 & 0x55) + (n & 0x55);
n = (n >>> 2 & 0x33) + (n & 0x33);
n = (n >>> 4 & 0x0f) + (n & 0x0f);

对应的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);