程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> 計算機程序的思維邏輯 (27)，思維27

計算機程序的思維邏輯 (27)，思維27

編輯：JAVA綜合教程

計算機程序的思維邏輯 (27)，思維27

本節繼續探討包裝類，主要介紹Integer類，下節介紹Character類，Long與Integer類似，就不再單獨介紹了，其他類基本已經介紹完了，不再贅述。

一個簡單的Integer還有什麼要介紹的呢？它有一些二進制操作，我們來看一下，另外，我們也分析一下它的valueOf實現。

為什麼要關心實現代碼呢？大部分情況下，確實不用關心，我們會用它就可以了，我們主要是為了學習，尤其是其中的二進制操作，二進制是計算機的基礎，但代碼往往晦澀難懂，我們希望對其有一個更為清晰深刻的理解。

我們先來看按位翻轉。

位翻轉

用法

Integer有兩個靜態方法，可以按位進行翻轉：

public static int reverse(int i)
public static int reverseBytes(int i)

位翻轉就是將int當做二進制，左邊的位與右邊的位進行互換，reverse是按位進行互換，reverseBytes是按byte進行互換。我們來看個例子：

int a = 0x12345678;
System.out.println(Integer.toBinaryString(a));

int r = Integer.reverse(a);
System.out.println(Integer.toBinaryString(r));

int rb = Integer.reverseBytes(a);
System.out.println(Integer.toHexString(rb));

a是整數，用十六進制賦值，首先輸出其二進制字符串，接著輸出reverse後的二進制，最後輸出reverseBytes的十六進制，輸出為：

10010001101000101011001111000
11110011010100010110001001000
78563412

reverseBytes是按字節翻轉，78是十六進制表示的一個字節，12也是，所以結果78563412是比較容易理解的。

二進制翻轉初看是不對的，這是因為輸出不是32位，輸出時忽略了前面的0，我們補齊32位再看：

00010010001101000101011001111000
00011110011010100010110001001000

這次結果就對了。

這兩個方法是怎麼實現的呢？

reverseBytes

來看reverseBytes的代碼：

public static int reverseBytes(int i) {
    return ((i >>> 24)           ) |
           ((i >>   8) &   0xFF00) |
           ((i <<   8) & 0xFF0000) |
           ((i << 24));
}

以參數i等於0x12345678為例，我們來分析執行過程：

i>>>24 無符號右移，最高字節挪到最低位，結果是 0x00000012。

(i>>8) & 0xFF00，左邊第二個字節挪到右邊第二個，i>>8結果是 0x00123456，再進行 & 0xFF00，保留的是右邊第二個字節，結果是0x00003400。

(i << 8) & 0xFF0000，右邊第二個字節挪到左邊第二個，i<<8結果是0x34567800，再進行 & 0xFF0000，保留的是右邊第三個字節，結果是0x00560000。

i<<24，結果是0x78000000，最右字節挪到最左邊。

這四個結果再進行或操作|，結果就是0x78563412，這樣，通過左移、右移、與和或操作，就達到了字節翻轉的目的。

reverse

我們再來看reverse的代碼：

public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

這段代碼雖然很短，但非常晦澀，到底是什麼意思呢？

代碼第一行是一個注釋， "HD, Figure 7-1"，這是什麼意思呢？HD表示的是一本書，書名為Hacker's Delight，HD是它的縮寫，Figure 7-1是書中的圖7-1，這本書中，相關內容如下圖所示：

可以看出，Integer中reverse的代碼就是拷貝了這本書中圖7-1的代碼，這個代碼的解釋在圖中也說明了，我們翻譯一下。

高效實現位翻轉的基本思路，首先交換相鄰的單一位，然後以兩位為一組，再交換相鄰的位，接著是四位一組交換、然後是八位、十六位，十六位之後就完成了。這個思路不僅適用於二進制，十進制也是適用的，為便於理解，我們看個十進制的例子，比如對數字12345678進行翻轉，

第一輪，相鄰單一數字進行互換，結果為：

21 43 65 87

第二輪，以兩個數字為一組交換相鄰的，結果為：

43 21 87 65

第三輪，以四個數字為一組交換相鄰的，結果為：

8765 4321

翻轉完成。

對十進制而言，這個效率並不高，但對於二進制，卻是高效的，因為二進制可以在一條指令中交換多個相鄰位。

這行代碼就是對相鄰單一位進行互換：

x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>>  1;

5的二進制是0101，0x55555555的二進制表示是：

01010101010101010101010101010101

x & 0x55555555就是取x的奇數位。

A的二進制是1010，0xAAAAAAAA的二進制表示是：

10101010101010101010101010101010

x & 0xAAAAAAAA就是取x的偶數位。

(x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>>  1;

表示的就是x的奇數位向左移，偶數位向右移，然後通過|合並，達到相鄰位互換的目的。這段代碼可以有個小的優化，只使用一個常量0x55555555，後半部分先移位再進行與操作，變為：

(i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;

同理，如下代碼就是以兩位為一組，對相鄰位進行互換：

i = (i & 0x33333333) << 2 | (i & 0xCCCCCCCC)>>>2;

3的二進制是0011，0x33333333的二進制表示是：

00110011001100110011001100110011

x & 0x33333333就是取x以兩位為一組的低半部分。

C的二進制是1100，0xCCCCCCCC的二進制表示是：

11001100110011001100110011001100

x & 0xCCCCCCCC就是取x以兩位為一組的高半部分。

(i & 0x33333333) << 2 | (i & 0xCCCCCCCC)>>>2;

表示的就是x以兩位為一組，低半部分向高位移，高半部分向低位移，然後通過|合並，達到交換的目的。同樣，可以去掉常量0xCCCCCCCC，代碼可以優化為：

(i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;

同理，下面代碼就是以四位為一組，進行交換。

i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;

到以八位為單位交換時，就是字節翻轉了，可以寫為如下更直接的形式，代碼和reverseBytes基本完全一樣。

i = (i << 24) | ((i & 0xff00) << 8) |
    ((i >>> 8) & 0xff00) | (i >>> 24);

reverse代碼為什麼要寫的這麼晦澀呢？或者說不能用更容易理解的方式寫嗎？比如說，實現翻轉，一種常見的思路是，第一個和最後一個交換，第二個和倒數第二個交換，直到中間兩個交換完成。如果數據不是二進制位，這個思路是好的，但對於二進制位，這個效率比較低。

CPU指令並不能高效的操作單個位，它操作的最小數據單位一般是32位（32位機器），另外，CPU可以高效的實現移位和邏輯運算，但加減乘除則比較慢。

reverse是在充分利用CPU的這些特性，並行高效的進行相鄰位的交換，也可以通過其他更容易理解的方式實現相同功能，但很難比這個代碼更高效。

循環移位

用法

Integer有兩個靜態方法可以進行循環移位：

public static int rotateLeft(int i, int distance)
public static int rotateRight(int i, int distance)

rotateLeft是循環左移，rotateRight是循環右移，distance是移動的位數，所謂循環移位，是相對於普通的移位而言的，普通移位，比如左移2位，原來的最高兩位就沒有了，右邊會補0，而如果是循環左移兩位，則原來的最高兩位會移到最右邊，就像一個左右相接的環一樣。我們來看個例子：

int a = 0x12345678;
int b = Integer.rotateLeft(a, 8);
System.out.println(Integer.toHexString(b));

int c = Integer.rotateRight(a, 8);
System.out.println(Integer.toHexString(c))

b是a循環左移8位的結果，c是a循環右移8位的結果，所以輸出為：

34567812
78123456

實現代碼

這兩個函數的實現代碼為：

public static int rotateLeft(int i, int distance) {
    return (i << distance) | (i >>> -distance);
}
public static int rotateRight(int i, int distance) {
    return (i >>> distance) | (i << -distance);
}

這兩個函數中令人費解的是負數，如果distance是8，那 i>>>-8是什麼意思呢？其實，實際的移位個數不是後面的直接數字，而是直接數字的最低5位的值，或者說是直接數字 & 0x1f的結果。之所以這樣，是因為5位最大表示31，移位超過31位對int整數是無效的。

理解了移動負數位的含義，我們就比較容易上面這段代碼了，比如說，-8的二進制表示是：

11111111111111111111111111111000

其最低5位是11000，十進制就是24，所以i>>>-8就是i>>>24，i<<8 | i>>>24就是循環左移8位。

上面代碼中，i>>>-distance就是 i>>>(32-distance)，i<<-distance就是i<<(32-distance)。

按位查找、計數

Integer中還有其他一些位操作，包括：

public static int signum(int i)

查看符號位，正數返回1，負數返回-1，0返回0

public static int lowestOneBit(int i)

找從右邊數第一個1的位置，該位保持不變，其他位設為0，返回這個整數。比如對於3，二進制為11，二進制結果是01，十進制就是1，對於20，二進制是10100，結果就是00100，十進制就是4。

public static int highestOneBit(int i)

找從左邊數第一個1的位置，該位保持不變，其他位設為0，返回這個整數。

public static int bitCount(int i)

找二進制表示中1的個數。比如20，二進制是10100，1的個數是2。

public static int numberOfLeadingZeros(int i)

左邊開頭連續為0的個數。比如20，二進制是10100，左邊有27個0。

public static int numberOfTrailingZeros(int i)

右邊結尾連續為0的個數。比如20，二進制是10100，右邊有兩個0。

關於其實現代碼，都有注釋指向Hacker's Delight這本書的相關章節，本文就不再贅述了。

valueOf的實現

上節我們提到，創建包裝類對象時，可以使用靜態的valueOf方法，也可以直接使用new，但建議使用valueOf，為什麼呢？我們來看valueOf的代碼：

public static Integer valueOf(int i) {
    assert IntegerCache.high >= 127;
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

它使用了IntegerCache，這是一個私有靜態內部類，代碼如下所示：

private static class IntegerCache {
    static final int low = -128;
    static final int high;
    static final Integer cache[];

    static {
        // high value may be configured by property
        int h = 127;
        String integerCacheHighPropValue =
            sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
        if (integerCacheHighPropValue != null) {
            int i = parseInt(integerCacheHighPropValue);
            i = Math.max(i, 127);
            // Maximum array size is Integer.MAX_VALUE
            h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
        }
        high = h;

        cache = new Integer[(high - low) + 1];
        int j = low;
        for(int k = 0; k < cache.length; k++)
            cache[k] = new Integer(j++);
    }

    private IntegerCache() {}
}

IntegerCache表示Integer緩存，其中的cache變量是一個靜態Integer數組，在靜態初始化代碼塊中被初始化，默認情況下，保存了從-128到127，共256個整數對應的Integer對象。

在valueOf代碼中，如果數值位於被緩存的范圍，即默認-128到127，則直接從IntegerCache中獲取已預先創建的Integer對象，只有不在緩存范圍時，才通過new創建對象。

通過共享常用對象，可以節省內存空間，由於Integer是不可變的，所以緩存的對象可以安全的被共享。Boolean/Byte/Short/Long/Character都有類似的實現。這種共享常用對象的思路，是一種常見的設計思路，在<設計模式>這本著作中，它被賦予了一個名字，叫享元模式，英文叫Flyweight，即共享的輕量級元素。

小結

本節介紹了Integer中的一些位操作，位操作代碼比較晦澀，但性能比較高，我們詳細解釋了其中的一些代碼，如果希望有更多的了解，可以根據注釋，查看Hacker's Delight這本書。我們同時介紹了valueOf的實現，介紹了享元模式。

下一節，讓我們來探討Character。

----------------

未完待續，查看最新文章，敬請關注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術的本質。用心寫作，原創文章，保留所有版權。