java源碼Integer.bitCount算法解析，分析原理（統(tǒng)計(jì)二進(jìn)制bit位）

Caizhenhao 發(fā)布于2019-08-19 10:48 / 2992人閱讀

摘要：算法統(tǒng)計(jì)整數(shù)的二進(jìn)制表達(dá)式中的位為的位數(shù)漢明重量普通算法應(yīng)該是最先想到的算法了，從最低位開始，一位一位地統(tǒng)計(jì)是否為，時(shí)間復(fù)雜度為，為總數(shù)。這時(shí)中存儲(chǔ)了每?jī)晌坏慕y(tǒng)計(jì)結(jié)果，可以進(jìn)行兩兩相加，最后求和。

算法：統(tǒng)計(jì)整數(shù)的二進(jìn)制表達(dá)式中的bit位為1的位數(shù)（漢明重量）

普通算法

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

應(yīng)該是最先想到的算法了，從最低位開始，一位一位地統(tǒng)計(jì)是否為1，時(shí)間復(fù)雜度為O(n)，n為總bit數(shù)。

優(yōu)化算法

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

這個(gè)算法乍看很懵逼，但是仔細(xì)琢磨一下也能發(fā)現(xiàn)原理：n-1后，n的最低位的1被消除了，然后與n位與，n變?yōu)樽畹臀?置為0后的新整數(shù)，如：

0b101100  減一  0b101011 最低位的1消除，0b101100 & 0b101011 = 0b101000

如此循環(huán)多少次就有多少個(gè)1，時(shí)間復(fù)雜度也是O(n)，但是這個(gè)n表示bit位為1的個(gè)數(shù)，總體是要比上一個(gè)優(yōu)一點(diǎn)的。
當(dāng)我們以為這已經(jīng)是最優(yōu)的算法了，事實(shí)卻并非如此

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

最后,其實(shí)java的Integer類已經(jīng)提供了一個(gè)方法來統(tǒng)計(jì)bit位（無符號(hào)右移，可以統(tǒng)計(jì)負(fù)數(shù)的），乍看之下，WTF?
原理：想象一下，當(dāng)一列的1擺在我們?nèi)四X的面前，我們會(huì)怎么數(shù)？一個(gè)一個(gè)數(shù)，第一個(gè)的算法的原理?；蛘邇蓚€(gè)兩個(gè)地?cái)?shù)？本方法就是如此實(shí)現(xiàn)的。如下圖：

             二進(jìn)制                       十進(jìn)制
 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的二進(jìn)制中的1的位數(shù)計(jì)算過程

每?jī)晌籦it為一組，分別統(tǒng)計(jì)有幾個(gè)1，然后把結(jié)果存到這兩個(gè)bit位上，如：11有2個(gè)1，結(jié)果為10，10替代11的存儲(chǔ)到原位置。然后進(jìn)行加法計(jì)算，把所有的結(jié)果加起來。加的過程中呢又可以兩兩相加，減少計(jì)算流程。

兩個(gè)bit計(jì)算1的數(shù)量：0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1，這樣就清楚了。

算法實(shí)現(xiàn)如下：

首先整數(shù)i抹除左一位：i & 0x55555555，然后錯(cuò)位相加。(i >>> 1) & 0x55555555表示：左位移到右邊，再把左位抹除，這樣就可以計(jì)算兩個(gè)bit位上1的個(gè)數(shù)了：0b1011=>0b0001 + 0b0101 = 0b0110左兩位有1個(gè)1，右兩位有2個(gè)1。

這時(shí)i中存儲(chǔ)了每?jī)晌坏慕y(tǒng)計(jì)結(jié)果，可以進(jìn)行兩兩相加，最后求和。

過程：

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

時(shí)間復(fù)雜度O(1),可以，很ok了！但是寫文章都要潤(rùn)色下的，別說算法了，然后優(yōu)化過后的就是Integer中的實(shí)現(xiàn)了。
優(yōu)化：

第一步：兩個(gè)bit計(jì)算1的數(shù)量：0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b00 + 0b01 = 0b01 = 1。研究發(fā)現(xiàn)：2=0b11-0b1，1=0b10-0b1,可以減少一次位于計(jì)算：i = i - ((i >>> 1) & 0x55555555)

第二步：暫時(shí)沒有好的優(yōu)化方法

第三步：實(shí)際是計(jì)算每個(gè)byte中的1的數(shù)量，最多8（0b1000）個(gè)，占4bit，可以最后進(jìn)行位與運(yùn)算消位，減少一次&運(yùn)算：i = (i + (i >>> 4)) & 0x0f0f0f0f

第四,五步：同上理由，可以最后消位。但是由于int最多32（0b100000）個(gè)1，所以這兩步可以不消位，最后一步把不需要的bit位抹除就可以了：i & 0x3f

感悟：大道至簡(jiǎn)，看似復(fù)雜的算法，其實(shí)現(xiàn)原理卻是我們大腦的簡(jiǎn)單思維邏輯

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