Long.bitCount() 解析

Wu Jun 2019-07-04 19:53:16
01 数据结构与算法

一、算法原型

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