首頁  >  文章  >  Java  >  java原始碼Integer.bitCount演算法原型與流程解析(附程式碼)

java原始碼Integer.bitCount演算法原型與流程解析(附程式碼)

php是最好的语言
php是最好的语言原創
2018-07-27 09:56:413974瀏覽

演算法:統計整數的二進位表達式中的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;
}

應該是最先想到的演算法了,從最低位元開始,一位一位地統計是否為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

相關文章:


Java Reference原始碼分析程式碼

java 原始碼分析Arrays.asList方法詳解

相關影片:

全面解析Java註解

以上是java原始碼Integer.bitCount演算法原型與流程解析(附程式碼)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn