一、前言

你是什么時(shí)候注意到位運(yùn)算？

從畢業(yè)入職公司看大佬的代碼出現(xiàn) 2 << 4 開始？從小白晉升高開讀框架的源碼看到 MAXIMUM_CAPACITY = 1 << 30; 開始？還是從什么時(shí)候開始？

其實(shí)二進(jìn)制的位運(yùn)算一直在我們那身邊，從你開始編寫 Hello Word 打印輸出時(shí)就有二進(jìn)制流的處理，只不過隱藏的很深不好發(fā)現(xiàn)。所以在我們開始意識(shí)到代碼和二進(jìn)制的關(guān)系往往都是來自于看到可以用二進(jìn)制完成的計(jì)算，包括；二進(jìn)制計(jì)算效率高于乘機(jī)，也包括二進(jìn)制可以更好的體現(xiàn)出你要設(shè)置值的大小范圍。比如你要設(shè)定一個(gè)指定范圍大小的 Int 值 = 1073741824，那么是給這樣一個(gè)整數(shù)值看起來直觀，還是二進(jìn)制 1<< 30 更直觀呢？其實(shí)他們兩個(gè)值是相等的。所以這樣的情況下也會(huì)有二進(jìn)制運(yùn)算的體現(xiàn)。

而小傅哥在學(xué)習(xí)編程階段，第一次注意到二進(jìn)制的運(yùn)算是關(guān)于a、b兩個(gè)值的互換，如果不引入第三個(gè)值就可以完成？

int a = 2, b = 3;
a = a ^ b;
b = a ^ b;
a = a ^ b;

一個(gè) ^ 帽子一樣的運(yùn)算符，就把兩個(gè)數(shù)給替換，替換后 a = 3，b = 2 那它是怎么辦到的呢？

?^ 異或運(yùn)算：兩個(gè)操作數(shù)的同位中，如果值相同（都是 0 或者都是 1）則為 0，不同（一個(gè)是 0，一個(gè)是 1）則為 1

• 以二進(jìn)制數(shù)據(jù)為基礎(chǔ)進(jìn)行運(yùn)算解析 a = 2 二進(jìn)制數(shù)為 0010、b = 3 二進(jìn)制數(shù)為 0011a = a ^ b = 0010 ^ 0011 = 0001b = a ^ b = 0001 ^ 0011 = 0010 = 2a = a ^ b = 0001 ^ 0010 = 0011 = 3
• 異或運(yùn)算的基本定理解析 a = a ^ bb = a ^ b = a ^ b ^? b = a = 2a = a ^ b = a ^ a ^ b = b = 3

而二進(jìn)制的運(yùn)算魅力還遠(yuǎn)不至于此，還可以完成奇偶判斷、有效位計(jì)算、乘法、加法等。這些內(nèi)容的學(xué)習(xí)可以讓我們研發(fā)人員，積累編程邏輯和拓展思維模式。接下來小傅哥就帶著大家學(xué)習(xí)一下。

二、位操作介紹

位操作是程序設(shè)計(jì)中對(duì)位數(shù)組或二進(jìn)制數(shù)的一元和二元操作。在許多古老的微處理器上，位運(yùn)算比加減運(yùn)算略快，通常位運(yùn)算比乘除法運(yùn)算要快很多。在現(xiàn)代架構(gòu)中，位運(yùn)算的運(yùn)算速度通常與加法運(yùn)算相同（仍然快于乘法運(yùn)算），但是通常功耗較小，因?yàn)橘Y源使用減少。

四種基本的位運(yùn)算包括；與&、或|、非~、異或^

int a = 1; // 0001
int b = 2; // 0010
int c = 4; // 0100
int d = 8; // 1000
int e = 15;// 1111

// 與運(yùn)算；0001
System.out.println(Integer.toBinaryString(a & e)); // 0001
// 或運(yùn)算；0011
System.out.println(Integer.toBinaryString(a | b)); // 0011
// 異或運(yùn)算；0101
System.out.println(Integer.toBinaryString(a ^ c)); // 0101
// 非運(yùn)算；...11110111
System.out.println(Integer.toBinaryString(~d));

• 與運(yùn)算；兩個(gè)數(shù)都轉(zhuǎn)為二進(jìn)制，然后從高位開始比較，如果兩個(gè)數(shù)都為1則為1，否則為0。
• 或運(yùn)算；兩個(gè)數(shù)都轉(zhuǎn)為二進(jìn)制，然后從高位開始比較，兩個(gè)數(shù)只要有一個(gè)為1則為1，否則就為0。
• 非運(yùn)算；如果位為0，結(jié)果是1，如果位為1，結(jié)果是0。
• 異或運(yùn)算；兩個(gè)數(shù)轉(zhuǎn)為二進(jìn)制，然后從高位開始比較，如果相同則為0，不相同則為1。

三、位運(yùn)算案例

1. 獲取位值

public int getBit(int number, int bitPosition){
    return (number >> bitPosition) & 1;
}

• 目的：獲取二進(jìn)制數(shù)字中，指定位置的值。
• 邏輯：該方法將目標(biāo)值右移到最右邊，即位數(shù)組的第0個(gè)位置上，如；0001 的二進(jìn)制形式。之后與 1 進(jìn)行與操作。如果目標(biāo)位是1，那么結(jié)果就是1，反之結(jié)果是0；

2. 設(shè)置位值

public int setBit(int number, int bitPosition){
    return number | (1 << bitPosition);
}

• 目的：設(shè)置二進(jìn)制數(shù)字中，指定位置的值
• 邏輯：1 就像一個(gè)子彈，左移指定位數(shù)到目標(biāo)位置，如；0010 的二進(jìn)制形式。與目標(biāo)值 number 做或運(yùn)算(把子彈打進(jìn)去)，設(shè)置結(jié)果并返回。

3. 清空位值

public int clearBit(int number, int bitPosition){
    int mask = ~(1 << bitPosition);
    return number & mask;
}

• 目的：清空二進(jìn)制數(shù)字中，指定位置的值
• 邏輯：類似于設(shè)置位值，把1左移指定位數(shù)后取反，從 0010 得到 1101 并與目標(biāo)值 number 做與&運(yùn)算，清掉目標(biāo)位的值。

4. 更新位值

public int updateBit(int number, int bitPosition, int bitValue){
    int clearMask = ~(1 << bitPosition);
    return (number & clearMask) | (bitValue << bitPosition);
}

• 目的：清空二進(jìn)制數(shù)字中，指定位置的值
• 邏輯：結(jié)合清空clearBit、設(shè)置setBit，兩個(gè)方法將制定位置替換為設(shè)置值。

5. 偶數(shù)判斷

public boolean isEven(int number){
    return (number & 1) == 0;
}

• 目的：檢測(cè) number 是否為偶數(shù)
• 邏輯：檢測(cè)二進(jìn)制的最右側(cè)一位，如果是1，那么一定是奇數(shù)。所以可以與1做與&運(yùn)算的結(jié)果和0判斷。不等于0是奇數(shù)，等于0是偶數(shù)。

6. 正數(shù)判斷

public boolean isPositive(int number) {
    if (number == 0) {
        return false;
    }
    return ((number >> 31) & 1) == 0;
}

• 目的：判斷 number 值是否為正數(shù)。
• 邏輯：基于二進(jìn)制正數(shù)最左邊的值是0的這個(gè)事實(shí)，右移31位，和1做與&運(yùn)算，如果結(jié)果等于1為負(fù)數(shù)，反正為正數(shù)。

7. 左移乘二

public int multiplyByTwo(int number){
    return number << 1;
}

• 目的：乘以2
• 邏輯：該方法將原始數(shù)字向左移動(dòng)一位。因此所有位都將乘以2，因此數(shù)字本身也將乘以2。

8. 右移除二

public int divideByTwo(int number){
    return number >> 1;
}

• 目的：除以2
• 邏輯：該方法將原始數(shù)字向右移動(dòng)一位。因此所有位都將除以2，因此數(shù)字本身也將除以2,且不會(huì)產(chǎn)生余數(shù)。

9. 正負(fù)交換

public int switchSign(int number){
    return ~number + 1;
}

• 目的：正數(shù)轉(zhuǎn)負(fù)數(shù)，負(fù)數(shù)轉(zhuǎn)正數(shù)
• 邏輯：通過二進(jìn)制取反運(yùn)算，如 1000 = 8 取反 1.....0111 = -9 + 1 = -8

10. 乘法運(yùn)算(有符號(hào))

public int multiply(int a, int b) {
    int multiply = 0;
    while (a != 0 && b != 0) {
        System.out.print("計(jì)算步驟(" + (isEven(b) ? "偶數(shù)" : "奇數(shù)") + ")：a(" + String.format("%04d", Integer.valueOf(Integer.toBinaryString(a))) + ") = " + a + " | b(" + String.format("%04d", Integer.valueOf(Integer.toBinaryString(b))) + ") = " + b);
        // b 是偶數(shù)：2a * (b/2)
        if (isEven(b)) {
            a = multiplyByTwo(a);
            b = divideByTwo(b);
        }
        // b 奇數(shù)
        else {
            // b 正數(shù)：2a * (b - 1)/2 + a
            if (isPositive(b)) {
                multiply += a;
                a = multiplyByTwo(a);
                b = divideByTwo(b - 1);
            }
            // b 負(fù)數(shù)：2a * (b + 1)/2 - a
            else {
                multiply -= a;
                a = multiplyByTwo(a);
                b = divideByTwo(b + 1);
            }
        }
        System.out.println(" | multiply(" + String.format("%04d", Integer.valueOf(Integer.toBinaryString(multiply))) + ") = " + multiply);
    }
    return multiply;
}

• 目的：計(jì)算有符號(hào)二進(jìn)制乘積
• 公式：推到公式與代碼向?qū)?yīng)= a * b= 2a * (b/2) —— b為偶數(shù)= 2a * (b - 1)/2 + a —— b 為奇數(shù)、正數(shù)= 2a * (b + 1)/2 - a —— b 為奇數(shù)、負(fù)數(shù)
• 邏輯：乘數(shù)a不斷左移、乘數(shù)b不斷右移。當(dāng)b歸0時(shí)，a左移累計(jì)下來的值就是乘積總和。如圖

11. 乘法運(yùn)算(無符號(hào))

public int multiplyUnsigned(int number1, int number2) {
    int result = 0;
    int multiplier = number2;
    int bitIdx = 0;
    while (multiplier != 0) {
        if ((multiplier & 1) == 1) {
            System.out.println(number1 + " << " + bitIdx + " = " + (number1 << bitIdx));
            result += number1 << bitIdx;
        }
        bitIdx += 1;
        multiplier = multiplier >> 1;
    }
    return result;
}

• 目的：計(jì)算無符號(hào)二進(jìn)制乘積
• 公式：13 = 2^3 + 2^2 + 2^0x*13 = x*2^3 + x*2^2 + x*2^0x*13 = x<<3 + x<<2 + x<<02*13 = 2<<3 + 2<<2 + 2<<0 = 16 + 8 + 2 = 26
• 邏輯：每個(gè)數(shù)字都可以表示成一系列2的冪之和。例如 13 的二進(jìn)制是 1101，最右側(cè)第1位1，是2的0次冪，所以對(duì)應(yīng)2的進(jìn)制值是左移0位。再比如13的右數(shù)第3位是1，對(duì)應(yīng)位置值是4也就是2的2次冪，所以對(duì)應(yīng)2的進(jìn)制值是左移2位。最終把這些值相加就是乘積值。

12. 一的數(shù)量

public int countSetBits(int originalNumber){
    int setBitsCount = 0;
    int number = originalNumber;
    while (number != 0) {
        setBitsCount += number & 1;
        number >>>= 1;
    }
    return setBitsCount;
}

• 目的：使用位運(yùn)算符對(duì)一個(gè)數(shù)字里設(shè)置為1的位進(jìn)行記數(shù)
• 邏輯：把數(shù)字每次向右移動(dòng)1位，然后使用&操作符取出最右邊一位的值，1則記數(shù)加1，0則不計(jì)。

13. 轉(zhuǎn)換計(jì)算

public int bitsDiff(int number1, int number2){
    return countSetBits(number1 ^ number2);
}

• 目的：計(jì)算一個(gè)數(shù)字，轉(zhuǎn)換為另外一個(gè)數(shù)字，所需要的轉(zhuǎn)換位數(shù)。
• 邏輯：當(dāng)數(shù)字進(jìn)行XOR異或運(yùn)算時(shí)，結(jié)果將是不同位數(shù)的數(shù)量(即異或的結(jié)果中所有被設(shè)置為1的位的數(shù)量)。

14. 有效位數(shù)

public int bitLength(int number){
    int bitsCounter = 0;
    while ((1 << bitsCounter) <= number) {
        bitsCounter += 1;
    }
    return bitsCounter;
}

• 目的：計(jì)算二進(jìn)制數(shù)值的有效位數(shù)，例如 14 = 1110 有效位為4位。
• 邏輯：通過1不斷地左移加和與 number 做對(duì)比，只要比number小就累加1位。

15. 冪值判斷

public boolean isPowerOfTwo(int number) {
    return (number & (number - 1)) == 0;
}

• 目的：檢查number是否為2的冪值。
• 邏輯：2的冪值形式的數(shù)字為2、4、8、16 等，那么可以把一個(gè)二進(jìn)制數(shù)進(jìn)行錯(cuò)位與&運(yùn)算，如果錯(cuò)位比對(duì)都為0，那么就是2的冪數(shù)。

16. 加法運(yùn)算(Ripple-carry adder)

public int fullAdder(int a, int b) {
    int result = 0;
    // 計(jì)算每次的進(jìn)位值，1 + 1 = 0010 進(jìn)位為1。是一種&運(yùn)算。
    int carryOut = 0;
    System.out.println("| aBit | bBit | carryIn | aiPlusBi | bitSum | carryOut | result |");
    for (int i = 0; i < 32; i++) {
        int aBit = getBit(a, i);
        int bBit = getBit(b, i);
        int carryIn = carryOut;
        System.out.print("|   " + aBit + "  |  " + bBit + "   |       " + carryIn);
        // 加和 - 兩個(gè)值；如果相同則為0，不相同則為1
        int aiPlusBi = aBit ^ bBit;
        System.out.print(" |        " + aiPlusBi);
      
        // 加和 - 進(jìn)位；
        int bitSum = aiPlusBi ^ carryIn;
        System.out.print(" |      " + bitSum);
      
        // 進(jìn)位；同位置 ai & bi = 1 | 與進(jìn)位 aiPlusBi & carryIn = 1
        carryOut = (aBit & bBit) | (aiPlusBi & carryIn);
        System.out.print(" |  " + carryOut + "(" + Integer.toBinaryString(carryOut) + ")   ");
      
        // 累加；把當(dāng)前位置計(jì)算的值，左移n位
        result = result | (bitSum << i);
        System.out.println(" | " + result + "(" + String.format("%04d", Integer.valueOf(Integer.toBinaryString(result))) + ")|");
    }
    return result;
}

• 目的：計(jì)算有符號(hào)二進(jìn)制加法
• 邏輯：二進(jìn)制的累加可以對(duì)照下計(jì)算10進(jìn)制累加時(shí)一樣，對(duì)應(yīng)2個(gè)數(shù)字相加，當(dāng)有進(jìn)位的時(shí)候記錄進(jìn)位。首先二進(jìn)制的加和計(jì)算，1+1 = 10、1+0=01、0+1=01、0+0=00，那么正好對(duì)應(yīng)上 ^ 非運(yùn)算，相同則為0，不相同則為1，因?yàn)榧词箖蓚€(gè)1相加，當(dāng)前位的值也是0。之后是進(jìn)位相加，兩數(shù)想加后，還可能有進(jìn)位上來的數(shù)值與兩數(shù)進(jìn)行相加。結(jié)果相加完成后，計(jì)算進(jìn)位，并保留進(jìn)位用于下次計(jì)算。進(jìn)位的計(jì)算為；ai & bi = 1 | 與進(jìn)位 aiPlusBi & carryIn = 1，無論是兩數(shù)相加，還是兩數(shù)的和 aiPlusBi 與進(jìn)位相加，只要與運(yùn)算是1，那么就要保留進(jìn)位。最后是累加結(jié)果，把對(duì)應(yīng)位置的結(jié)果計(jì)算，按照當(dāng)前計(jì)算到到二進(jìn)制的位數(shù)左移到目標(biāo)為止，累加到 result，最后就是結(jié)果值。

四、常見面試題

• & 和 ~ 是什么運(yùn)算？
• 兩數(shù)交換不引入第三個(gè)變量如何處理？
• 二進(jìn)制中1個(gè)個(gè)數(shù)怎么計(jì)算？
• 實(shí)現(xiàn)一個(gè)兩數(shù)加和？
• 實(shí)現(xiàn)一個(gè)無符號(hào)兩數(shù)成績(jī)？