Long.bitCount() 解析

Wu Jun 2019-12-25 15:59:03
Categories： Tags：

一、算法原型

Long.bitCount()的算法原型是以下的错位相加，分治统计。

public static long countOne(long i) {
    i = (i & (0x5555555555555555L)) + ((i >> 1) & (0x5555555555555555L));
    i = (i & (0x3333333333333333L)) + ((i >> 2) & (0x3333333333333333L));
    i = (i & (0x0f0f0f0f0f0f0f0fL)) + ((i >> 4) & (0x0f0f0f0f0f0f0f0fL));
    i = (i & (0x00ff00ff00ff00ffL)) + ((i >> 8) & (0x00ff00ff00ff00ffL));
    i = (i & (0x0000ffff0000ffffL)) + ((i >> 16) & (0x0000ffff0000ffffL));
    i = (i & (0x00000000FFFFFFFFL)) + ((i >> 32) & (0x00000000FFFFFFFFL));
    return i;
}

只是在计算上进行了优化，减少了位运算。

二、算法优化

与上述算法原型相比，Long.bitCount()少了 7 次位运算

public static int bitCount(long i) {
    i = i - ((i >>> 1) & 0x5555555555555555L);
    i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
    i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    i = i + (i >>> 32);
    return (int)i & 0x7f;
}

三、算法解析

3.1、第一行

3.1.1）优化

由

(i & (0x5555555555555555L)) + ((i >> 1) & (0x5555555555555555L));

优化为

i - ((i >>> 1) & 0x5555555555555555L)

减少了一次 & 运算

3.1.2）原理

对于一个两位二进制（i），1的个数有如下规律：

1的数量 = 二进制数本身 - 二进制高位上数字 = i - (i >>> 1)

00（1个） = 00（i）- 00（i >>> 1）;
01（1个） = 01（i）- 00（i >>> 1）;
01（1个） = 10（i）- 01（i >>> 1）;
10（2个） = 11（i）- 01（i >>> 1）;

当二进制位数大于2位时，仍然可以采用这个规律，分为每两位计算1的个数，存在这两位中。

为避免位移时高位对低位的影响，对位移结果 &01，只取低位，则2位时公式为： i - (i >>> 1 & 01)

推广到64位的就是

i - (i >>> 1 & 0101010101010101010101010101010101010101010101010101010101010101)

即

i - (i >>> 1 & 0x5555555555555555L)

3.1.3）实例

i = 1111111111111111111111111111111111111111111111111111111111111111

目前每2位二进制的值为这2位中1的个数 0b10 = 2

3.2、第二行

3.2.1）优化

第二行没有优化方法，正常移位计算。

i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
3.2.2）原理

每四位中，分别截取高低两位的值，合并两个的值，存放在这4位中

3.2.2）实例

i = 1010101010101010101010101010101010101010101010101010101010101010

目前每4位二进制的值为这4位中1的个数 0b0100 = 4

3、第三行

3.3.1）优化

由

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

优化为

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

减少了一次 & 运算

3.3.2）原理

经过第二行，每4位的二进制值即为4为中1的数量。

8位二进制中1的数量最多为8，可用4位表示。

将8位中高低4位的值相加，则为这8位中1的个数，存在低四位中，再 &00001111 只保留低位值

减少了一次 & 运算。

3.3.3）实例

i = 0100010001000100010001000100010001000100010001000100010001000100

目前每8位二进制中低4位的值，为这8位中1的个数 0b0000_1000 = 8

4、第4,5,6行

3.4.1）优化

由

    i = (i & (0x00ff00ff00ff00ffL)) + ((i >> 8) & (0x00ff00ff00ff00ffL));
    i = (i & (0x0000ffff0000ffffL)) + ((i >> 16) & (0x0000ffff0000ffffL));
    i = (i & (0x00000000FFFFFFFFL)) + ((i >> 32) & (0x00000000FFFFFFFFL));

优化为

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

每行减少两次 & 运算

3.4.2）原理

原理与上一行一样。

但因为64位2进制数最多64个1，只需要7位2进制数就能存储，所以高低位相加之后不用消除高位，只需要最后&1111111保留后7位就行了。

3.4.3）实例

i = 0000100000001000000010000000100000001000000010000000100000001000

5、第7行

3.5.1）优化

截取后7位值

(int)i & 0x7f

新增了一次 & 计算

3.5.2）原理

64个1只需要7位2进制数就能存储

3.5.3）实例
  00001000000100000001100000100000_001010000011000000111000_01000000（i）
&                                                           01111111（‬0x7f32）
  ----------------------------------------------------------------
                                                             1000000（new i）

i 为64位中1的个数 = 0b1000000 = 64

枚举和注解（34-41）
2019 年工作总结