作者：小傅哥

部落格：https://bugstack.cn

源碼：https://github.com/fuzhengwei/java-algorithms

沉澱、分享、成長，讓自己和他人都能有所收獲！

一、前言

你是什麼時候注意到位運算？

從畢業入職公司看大佬的代碼出現 2 << 4 開始？從小白晉升高開讀架構的源碼看到 MAXIMUM_CAPACITY = 1 << 30; 開始？還是從什麼時候開始？

其實二進制的位運算一直在我們那身邊，從你開始編寫 Hello Word 列印輸出時就有二進制流的處理，隻不過隐藏的很深不好發現。是以在我們開始意識到代碼和二進制的關系往往都是來自于看到可以用二進制完成的計算，包括；二進制計算效率高于乘機，也包括二進制可以更好的展現出你要設定值的大小範圍。比如你要設定一個指定範圍大小的 Int 值 = 1073741824，那麼是給這樣一個整數值看起來直覺，還是二進制 1<< 30 更直覺呢？其實他們兩個值是相等的。是以這樣的情況下也會有二進制運算的展現。

而小傅哥在學習程式設計階段，第一次注意到二進制的運算是關于a、b兩個值的互換，如果不引入第三個值就可以完成？

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

一個 ^ 帽子一樣的運算符，就把兩個數給替換，替換後 a = 3，b = 2 那它是怎麼辦到的呢？

^ 異或運算：兩個操作數的同位中，如果值相同（都是 0 或者都是 1）則為 0，不同（一個是 0，一個是 1）則為 1

以二進制資料為基礎進行運算解析 a = 2 二進制數為 0010、b = 3 二進制數為 0011a = a ^ b = 0010 ^ 0011 = 0001b = a ^ b = 0001 ^ 0011 = 0010 = 2a = a ^ b = 0001 ^ 0010 = 0011 = 3
異或運算的基本定了解析 a = a ^ bb = a ^ b = a ^ b ^ b = a = 2a = a ^ b = a ^ a ^ b = b = 3

而二進制的運算魅力還遠不至于此，還可以完成奇偶判斷、有效位計算、乘法、加法等。這些内容的學習可以讓我們研發人員，積累程式設計邏輯和拓展思維模式。接下來小傅哥就帶着大家學習一下。

二、位操作介紹

位操作是程式設計中對位數組或二進制數的一進制和二進制操作。在許多古老的微處理器上，位運算比加減運算略快，通常位運算比乘除法運算要快很多。在現代架構中，位運算的運算速度通常與加法運算相同（仍然快于乘法運算），但是通常功耗較小，因為資源使用減少。

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

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

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

與運算；兩個數都轉為二進制，然後從高位開始比較，如果兩個數都為1則為1，否則為0。
或運算；兩個數都轉為二進制，然後從高位開始比較，兩個數隻要有一個為1則為1，否則就為0。
非運算；兩個數轉為二進制，然後從高位開始比較，如果相同則為0，不相同則為1。
異或運算；如果位為0，結果是1，如果位為1，結果是0

三、位運算案例

1. 擷取位值

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

目的：擷取二進制數字中，指定位置的值。
邏輯：該方法将目标值右移到最右邊，即位數組的第0個位置上，如；0001 的二進制形式。之後與 1 進行與操作。如果目标位是1，那麼結果就是1，反之結果是0；

2. 設定位值

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

目的：設定二進制數字中，指定位置的值
邏輯：1 就像一個子彈，左移指定位數到目标位置，如；0010 的二進制形式。與目标值 number 做或運算(把子彈打進去)，設定結果并傳回。

3. 清空位值

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

目的：清空二進制數字中，指定位置的值
邏輯：類似于設定位值，把1左移指定位數後取反，從 0010 得到 1101 并與目标值 number 做與&運算，清掉目标位的值。

4. 更新位值

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

目的：清空二進制數字中，指定位置的值
邏輯：結合清空clearBit、設定setBit，兩個方法将制定位置替換為設定值。

5. 偶數判斷

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

目的：檢測 number 是否為偶數
邏輯：檢測二進制的最右側一位，如果是1，那麼一定是奇數。是以可以與1做與&運算的結果和0判斷。不等于0是奇數，等于0是偶數。

6. 正數判斷

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

目的：判斷 number 值是否為正數。
邏輯：基于二進制正數最左邊的值是0的這個事實，右移31位，和1做與&運算，如果結果等于1為負數，反正為正數。

7. 左移乘二

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

目的：乘以2
邏輯：該方法将原始數字向左移動一位。是以所有位都将乘以2，是以數字本身也将乘以2。

8. 右移除二

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

目的：除以2
邏輯：該方法将原始數字向右移動一位。是以所有位都将除以2，是以數字本身也将除以2,且不會産生餘數。

9. 正負交換

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

目的：正數轉負數，負數轉正數
邏輯：通過二進制異或運算取反，如 1000 = 8 取反 1.....0111 = -9 + 1 = -8

10. 乘法運算(有符号)

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

目的：計算有符号二進制乘積
公式：推到公式與代碼向對應 = a * b= 2a * (b/2) —— b為偶數= 2a * (b - 1)/2 + a —— b 為奇數、正數= 2a * (b + 1)/2 - a —— b 為奇數、負數
邏輯：乘數a不斷左移、乘數b不斷右移。當b歸0時，a左移累計下來的值就是乘積總和。如圖

11. 乘法運算(無符号)

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

目的：計算無符号二進制乘積
公式： 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
邏輯：每個數字都可以表示成一系列2的幂之和。例如 13 的二進制是 1101，最右側第1位1，是2的0次幂，是以對應2的進制值是左移0位。再比如13的右數第3位是1，對應位置值是4也就是2的2次幂，是以對應2的進制值是左移2位。最終把這些值相加就是乘積值。

12. 一的數量

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

目的：使用位運算符對一個數字裡設定為1的位進行記數
邏輯：把數字每次向右移動1位，然後使用&操作符取出最右邊一位的值，1則記數加1，0則不計。

13. 轉換計算

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

目的：計算一個數字，轉換為另外一個數字，所需要的轉換位數。
邏輯：當數字進行XOR異或運算時，結果将是不同位數的數量(即異或的結果中所有被設定為1的位的數量)。

14. 有效位數

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

目的：計算二進制數值的有效位數，例如 14 = 1110 有效位為4位。
邏輯：通過1不斷地左移加和與 number 做對比，隻要比number小就累加1位。

15. 幂值判斷

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

目的：檢查number是否為2的幂值。
邏輯：2的幂值形式的數字為2、4、8、16 等，那麼可以把一個二進制數進行錯位與&運算，如果錯位比對都為0，那麼就是2的幂數。

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

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

目的：計算有符号二進制加法
邏輯：二進制的累加可以對照下計算10進制累加時一樣，對應2個數字相加，當有進位的時候記錄進位。首先二進制的加和計算，1+1 = 10、1+0=01、0+1=01、0+0=00，那麼正好對應上 ^ 非運算，相同則為0，不相同則為1，因為即使兩個1相加，目前位的值也是0。之後是進位相加，兩數想加後，還可能有進位上來的數值與兩數進行相加。結果相加完成後，計算進位，并保留進位用于下次計算。進位的計算為；ai & bi = 1 | 與進位 aiPlusBi & carryIn = 1，無論是兩數相加，還是兩數的和 aiPlusBi 與進位相加，隻要與運算是1，那麼就要保留進位。最後是累加結果，把對應位置的結果計算，按照目前計算到到二進制的位數左移到目标為止，累加到 result，最後就是結果值。

四、常見面試題

& 和 ~ 是什麼運算？
兩數交換不引入第三個變量如何處理？
二進制中1個個數怎麼計算？
實作一個兩數加和？
實作一個無符号兩數成績？

《程式員數學：位運算》——如何使用二進制計算乘法？

一、前言

二、位操作介紹

三、位運算案例

1. 擷取位值

2. 設定位值

3. 清空位值

4. 更新位值

5. 偶數判斷

6. 正數判斷

7. 左移乘二

8. 右移除二

9. 正負交換

10. 乘法運算(有符号)

11. 乘法運算(無符号)

12. 一的數量

13. 轉換計算

14. 有效位數

15. 幂值判斷

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

四、常見面試題

繼續閱讀

什麼叫蘋果雲手機？ios雲手機如何使用

巨量千川計劃輔助神器一鍵起量的使用技巧。如何使用巨量千川的一鍵起量功能？一鍵起量功能雖然已推出一段時間，但使用效果不盡如

Java常見面試題：什麼是值傳遞？許多人可能仍不清楚值傳遞的概念。盡管他們知道如何使用引用傳遞，但他們可能不了解其實際原

如何使用EV代碼簽名證書，注冊Windows硬體開發中心帳戶？

其實，現在時代所謂的科技發達。在我看來，沒一點神秘、了得之處。因為，一切的一切，都是建立在，電、電子、電路闆之上的。而原

關于統招專升本的這些資訊表，你一定要知道它們如何使用，掌握這些表的資訊及使用方法，也是成功上岸的重要組成部分。#惠衆專升

中視訊計劃的釋出入口。你知道中視訊夥伴計劃正确的釋出入口嗎？隻有從正确的釋出入口釋出作品，才能獲得西瓜平台、抖音平台和今

緩存注解大揭秘：SpringCloud中如何使用緩存注解？

如何使用人工智能來做事：AI實用指南

如何使用 PSEXEC 在遠端計算機上運作指令

如何使用Golang的Gin架構渲染HTML頁面

如何使用NS遊戲機？現在教你如何進入學習軟體。·首先打開NS遊戲機，設定開機選項。更多設定中包含學習軟體，若未找到，請先

如何使用 OFFICE 365 保留政策

如何使用PyTorch建構Transformer模型實作語言生成任務

如何使用Transformer模型實作語言分類任務

php源碼安裝，如何使用源碼的方式安裝PHP環境