java源碼Integer.bitCount算法解析，分析原理（統計二進制bit位）

Caizhenhao 發布于2019-08-19 10:48 / 2976人閱讀

摘要：算法統計整數的二進制表達式中的位為的位數漢明重量普通算法應該是最先想到的算法了，從最低位開始，一位一位地統計是否為，時間復雜度為，為總數。這時中存儲了每兩位的統計結果，可以進行兩兩相加，最后求和。

算法：統計整數的二進制表達式中的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，結果為10，10替代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-0b1，1=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

GPU云服務器云服務器 bit位運算 java 解析2進制 java源碼算法 java集合源碼分析

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76489.html

Java HashMap 源碼解析

摘要：所以利用哈希表這種數據結構實現具體類時，需要設計個好的函數，使沖突盡可能的減少其次是需要解決發生沖突后如何處理。源碼剖析首先從構造函數開始講，遵循集合框架的約束，提供了一個參數為空的構造函數與有一個參數且參數類型為的構造函數。本文章首發于個人博客，鑒于sf博客樣式具有賞心悅目的美感，遂發表于此，供大家學習、批評。本文還在不斷更新中，最新版可移至個人博客。? 繼上一篇文章Java集合...

Aklman 2019-08-14 12:26 評論0 收藏0
大廠算法面試之leetcode精講9.位運算

摘要：空間復雜度方法是否為最大的冪的約數思路最大的的冪為，判斷是否是的約數即可。復雜度時間復雜度，一個整數統計二進制的復雜度，最壞的情況下是。大廠算法面試之leetcode精講9.位運算視頻教程（高效學習）:點擊學習目錄：1.開篇介紹2.時間空間復雜度3.動態規劃4.貪心5.二分查找6.深度優先&廣度優先7.雙指針...

番茄西紅柿 2021-11-29 10:50 評論0 收藏2637
Java集合之HashMap源碼解析

摘要：之前，其內部是由數組鏈表來實現的，而對于鏈表長度超過的鏈表將轉儲為紅黑樹。非線程安全，即任一時刻可以有多個線程同時寫，可能會導致數據的不一致。有時兩個會定位到相同的位置，表示發生了碰撞。原文地址 HashMap HashMap 是 Map 的一個實現類，它代表的是一種鍵值對的數據存儲形式。大多數情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。 HashM...

lindroid 2019-08-15 18:12 評論0 收藏0
集合源碼學習之路---hashMap(jdk1.8)

摘要：值得位數有的次方，如果直接拿散列值作為下標訪問主數組的話，只要算法比較均勻，一般是很難出現碰撞的。但是內存裝不下這么大的數組，所以計算數組下標就采取了一種折中的辦法，就是將得到的散列值與數組長度做一個與操作。 hashMap簡單介紹 hashMap是面試中的高頻考點，或許日常工作中我們只需把hashMap給new出來，調用put和get方法就完了。但是hashMap給我們提供了一個絕佳...

kamushin233 2019-08-16 10:56 評論0 收藏0
源碼|jdk源碼之HashMap分析(一)

摘要：看屬性有一個，所以是紅黑樹的節點。會在鏈表過長的時候，將其重構成紅黑樹，這個看后面的代碼。如果是紅黑樹的話，調用紅黑樹的查找函數來最終找到這個節點。該位置為平衡樹。但是這導致鏈表增長，需要觸發鏈表重構成平衡樹的判斷邏輯。 hash表是應用最廣泛的數據結構，是對鍵值對數據結構的一種重要實現。它能夠將關鍵字key映射到內存中的某一位置，查詢和插入都能達到平均時間復雜度為O(1)的性能。 ...

AndroidTraveler 2019-08-16 12:42 評論0 收藏0