java源码Integer.bitCount算法解析,分析原理(统计二进制bit位)

算法:统计整数的二进制表达式中的bit位为1的位数(汉明重量)

普通算法

public int bitCount(int num) {
    int count = 0;
    do {
        if ((num & 1) == 1) {
            count++;
        }
        num>>=1;
    } while (num > 0);
    return count;
}

应该是最先想到的算法了,从最低位开始,一位一位地统计是否为1,时间复杂度为O(n),n为总bit数。

优化算法

public int countBit2(int num) {
    int count = 0;
    while (num > 0) {
        num = num & (num - 1);
        count++;
    }
    return count;
}

这个算法乍看很懵逼,但是仔细琢磨一下也能发现原理:n-1后,n的最低位的1被消除了,然后与n位与,n变为最低位1置为0后的新整数,如:

0b101100  减一  0b101011 最低位的1消除,0b101100 & 0b101011 = 0b101000

如此循环多少次就有多少个1,时间复杂度也是O(n),但是这个n表示bit位为1的个数,总体是要比上一个优一点的。
当我们以为这已经是最优的算法了,事实却并非如此

Integer.bitCount

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

最后,其实java的Integer类已经提供了一个方法来统计bit位(无符号右移,可以统计负数的),乍看之下,WTF?
原理:想象一下,当一列的1摆在我们人脑的面前,我们会怎么数?一个一个数,第一个的算法的原理。或者两个两个地数?本方法就是如此实现的。如下图:

二进制                       十进制
 1  0   1  1   1  1   1  1   1  1     10 11 11 11 11
  01     10     10     10     10       1 2  2  2  2
          \     /       \     /           \/    \/
  01       0100           0100         1   4    4
                \       /                   \  /
  01               1000                1      8
      \          /                       \   /
          1001                             9
          
              767的二进制中的1的位数计算过程

每两位bit为一组,分别统计有几个1,然后把结果存到这两个bit位上,如:11有2个1,结果为1010替代11的存储到原位置。然后进行加法计算,把所有的结果加起来。加的过程中呢又可以两两相加,减少计算流程。

两个bit计算1的数量:0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1,这样就清楚了。

算法实现如下:

  • 首先整数i抹除左一位:i & 0x55555555,然后错位相加。(i >>> 1) & 0x55555555表示:左位移到右边,再把左位抹除,这样就可以计算两个bit位上1的个数了:0b1011=>0b0001 + 0b0101 = 0b0110左两位有1个1,右两位有2个1。
  • 这时i中存储了每两位的统计结果,可以进行两两相加,最后求和。

过程:

0x55555555  ‭0b01010101010101010101010101010101‬
0x33333333  ‭0b00110011001100110011001100110011‬
0x0f0f0f0f  ‭0b00001111000011110000111100001111‬
0x00ff00ff  0b00000000111111110000000011111111
0x0000ffff  ‭0b00000000000000001111111111111111‬
0x3f        ‭0b00111111‬

0b11 11 11 11 11    (i & 0x55555555) + ((i >>> 1) & 0x55555555)  = 0b0101010101‬ + 0b0101010101 = 0b1010101010
0b10 10 10 10 10    (i & 0x33333333) + ((i >>> 2) & 0x33333333) = 0b1000100010 + 0b00100010 = 0b1001000100
0b10 01 00 01 00    (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f) = 0b1000000100 + 0b0100 = 0b1000001000
0b10 00 00 10 00    (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff) = 0b1000 + 0b10 = 0b1010
0b00 00 00 10 10    (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff) = 0b1010 + 0 = 0b1010
dec           10

算法原型:

public static int bitCount(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);
    return i;
}

时间复杂度O(1),可以,很ok了!但是写文章都要润色下的,别说算法了,然后优化过后的就是Integer中的实现了。
优化:

  • 第一步:两个bit计算1的数量:0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b00 + 0b01 = 0b01 = 1。研究发现:2=0b11-0b11=0b10-0b1,可以减少一次位于计算:i = i - ((i >>> 1) & 0x55555555)
  • 第二步:暂时没有好的优化方法
  • 第三步:实际是计算每个byte中的1的数量,最多8(0b1000)个,占4bit,可以最后进行位与运算消位,减少一次&运算:i = (i + (i >>> 4)) & 0x0f0f0f0f
  • 第四,五步:同上理由,可以最后消位。但是由于int最多32(0b100000)个1,所以这两步可以不消位,最后一步把不需要的bit位抹除就可以了:i & 0x3f

感悟:大道至简,看似复杂的算法,其实现原理却是我们大脑的简单思维逻辑

7    0b111
i = 7 - ((7>>>1) & 0x55555555) = 6 = 0b110
i = (6 & 0x33333333) + ((6 >>> 2) & 0x33333333) = 2 + 1 = 3 = 0b11
i = (3 + (i >>> 4)) & 0x0f0f0f0f = 3 & 0x0f0f0f0f = 3 = 0b11
i = 3 + (3 >>> 8) = 3 = 0b11
i = 3 + (3 >>> 16) = 3 = 0b11
i = 3 & 0x3f = 3

相关推荐