Rumah > Java > javaTutorial > java源码Integer.bitCount算法原型和过程解析(附代码)

java源码Integer.bitCount算法原型和过程解析(附代码)

php是最好的语言
Lepaskan: 2018-07-27 09:56:41
asal
4141 orang telah melayarinya

算法:统计整数的二进制表达式中的bit位为1的位数(汉明重量),普通算法:应该是最先想到的算法了,从最低位开始,一位一位地统计是否为1,时间复杂度为O(n),n为总bit数。优化算法:这个算法乍看很懵逼,但是仔细琢磨一下也能发现原理:n-1后,n的最低位的1被消除了,然后与n位与,n变为最低位1置为0后的新整数。

普通算法

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

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

优化算法

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

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

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

如此循环多少次就有多少个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;
}
Salin selepas log masuk

最后,其实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的位数计算过程
Salin selepas log masuk

每两位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
Salin selepas log masuk

算法原型:

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;
}
Salin selepas log masuk

时间复杂度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
Salin selepas log masuk

相关文章:

详解Java Reference源码分析代码

java 源码分析Arrays.asList方法详解

相关视频:

全面解析Java注解

Atas ialah kandungan terperinci java源码Integer.bitCount算法原型和过程解析(附代码). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan