寫在前面

二進制位運算是最貼近計算機真實運算操作，通過位運算，我們可以高效的完成各種基礎運算（加減乘除取餘等），我們還可以使用位運算巧妙的完成原本很複雜的工作，真正理解計算機，我們才能更好的使用計算機。在這一篇文章，我將通過基礎理解開始，講解到 Java 中的一些實際應用。

機器數和機器數的真值

一個數在計算機中的二進制表示形式，叫做這個數的機器數。機器數是帶符號的，在計算機用機器數的最高位存放符號，正數為 0，負數為 1。舉個例子，比如在機器字長為 8 位的情況下（機器字長是指計算機直接處理的二進制數據的位數，它決定了計算機的運算精度，一般是 8 的整數倍，8 位、16 位、32 位、64 位、128 位），十進制中的+3，轉換成二進制就是 0000 0011，如果是-3，轉換成二進制就是 1000 0011。轉換的二進制數 0000 0011 和 1000 0011 就是機器數。

這裡我們還需要知道的就是機器數的真值，由於機器數的第一位是符號位，所以機器數的形式值就不等於真正的數值。例如上面的有符號數 1000 0011，其最高位 1 代表負，其真正數值是-3，而不是形式值 131（1000 0011 轉換成十進制等於 131），所以，為了區別起見，將帶符號的機器數對應的真正數值成為機器數的真值。比如 0000 0001 的真值 = +000 0001 = +1，1000 0001 的真值 = –000 0001 = –1

原碼、反碼和補碼的基礎概念和計算方法

上面我們瞭解了機器數，也就是二進制數，不過計算機要使用一定的編碼方法進行儲存，原碼、反碼和補碼就是機器存儲一個具體數字的編碼方式。

原碼

原碼就是符號位加上真值的絕對值，即用第一位表示符號，其餘位表示值，比如：如果 8 位二進制：

[+1]原= 0000 0001

[-1]原= 1000 0001

第一位是符號位，因為第一位是符號位，所以 8 位二進制數的取值範圍就是：（即第一位不表示值，只表示正負。）[1111 1111 , 0111 1111]，也就是十進制的[-127 , 127]（小聲嗶嗶，其實可以說成原碼是帶符號的機器數）。

反碼

正數的反碼就是其本身，負數的反碼是其原碼的基礎上，符號位不變，其餘各個位取反。

[+1] = [0000 0001]原= [0000 0001]反

[-1] = [1000 0001]原= [1111 1110]反

補碼

補碼的表示方法是，正數的補碼就是其本身，負數的補碼是在其原碼的基礎上，符號位不變，其餘各位取反，最後+1（也就是在其反碼的基礎上+1）

[+1] = [0000 0001]原= [0000 0001]反= [0000 0001]補

[-1] = [1000 0001]原= [1111 1110]反= [1111 1111]補

知道了這三個基本概念之後，值得一提的是，如果用反碼相加，會產生兩個零的問題（-0 和+0），所以我們使用補碼，不僅僅修復了 0 的符號以及存在兩個編碼的問題，而且還能夠多表示一個最低數。這就是為什麼 8 位二進制，使用原碼或反碼錶示的範圍為[-127, +127]，而使用補碼錶示的範圍為[-128, 127]。因為機器使用補碼，所以對於編程中常用到的有符號的 32 位 int 類型，可以表示範圍是: [-231, 231-1] 因為第一位表示的是符號位，而使用補碼錶示時又可以多保存一個最小值。

Java 中的運算符

注意了，以下所有的位運算都是通過補碼進行的，正數的補碼就是它本身，負數自己對應算，兩個操作數都為正數，則結果直接取二進制轉十進制，如果兩個操作數其中有一個是負數或者兩個都為負數，則結果如果符號位是 1（即負的），則得到的是補碼，需要從補碼轉到原碼，再轉換成十進制，如果結果符號位是 0，直接取二進制轉十進制。也就是運算時逢負取補，結果是逢負取原。可以自己先把下面十進制數全部轉換成二進制補碼，然後帶進去算，看一下是不是正確結果。

異或運算符號是“^”，相同的為 0，不同的為 1，代碼舉例如下：

<code>public static void main(String[] args) {
    System.out.println("2^3 運算的結果是 :"+(2^3));
    //打印的結果是:   2^3 運算的結果是 :1
}

//2 的二進制 0010，3 的二進制 0011，2^3 就為 0001，結果就是 1

public static void main(String[] args) {
    System.out.println("-2^3 運算的結果是 :"+(-2^3));
    //打印的結果是:   -2^3 運算的結果是 :-3
}

//-2 的二進制補碼 1110，3 的二進制 0011，-2^3 就為 0001，結果就是-3/<code>

與運算符號是“&”，只要有一個為 0 就為 0，代碼舉例如下：

<code>public static void main(String[] args) {
     System.out.println("2&3 運算的結果是 :"+(2&3));
     //打印的結果是:   2&3 運算的結果是 :2
}

public static void main(String[] args) {
     System.out.println("-2&3 運算的結果是 :"+(-2&3));
     //打印的結果是:   -2&3 運算的結果是 :2
}/<code>

或運算符是“|”，只要有一個為 1 就是 1，代碼舉例如下：

<code>public static void main(String[] args){
    System.out.println("2|3 運算的結果是 ："+(2|3));
    //打印的結果是： 2|3 運算的結果是 ： 3
}

public static void main(String[] args){
    System.out.println("-2|3 運算的結果是 ："+(-2|3));
    //打印的結果是： -2|3 運算的結果是 ： -1
}/<code>

非運算符是“~”，就是各位取反，代碼舉例如下：

<code>public static void main(String[] args){
    System.out.println("~5 運算的結果是 ："+(~5));
    //打印的結果是： ~5 運算的結果是 ： -6
}

public static void main(String[] args){
    System.out.println("~(-5)運算的結果是 ："+(~(-5)));
    //打印的結果是： ~(-5)運算的結果是 ： 4
}/<code>

向左位移符號“<

<code>public static void main(String[] args) {
     System.out.println("2<<3 運算的結果是 :"+(2<<3));
     //打印的結果是:   2<<3 運算的意思是，向左移動 3 位，其結果是 :16 

}

public static void main(String[] args) {
     System.out.println("-2<<3 運算的結果是 :"+(-2<<3));
     //打印的結果是:   -2<<3 運算的意思是，向左移動 3 位，其結果是 :-16
}/<code>

向右位移符號“>>”，二進制向右移動 n 位，若值為正，則在高位插入 0，若值為負，則在高位插入 1

<code>public static void main(String[] args) {
     System.out.println("2>>3 運算的結果是 :"+(2>>3));
     //打印的結果是:   2>>3 運算的意思是，向右移動 3 位，其結果是 :0
}

public static void main(String[] args) {
     System.out.println("-2>>3 運算的結果是 :"+(-2>>3));
     //打印的結果是:   -2>>3 運算的意思是，向右移動 3 位，其結果是 :-1
}/<code>

無符號右移符號“>>>”，忽略符號位，空位都以 0 補齊。 “>>>”與“>>”唯一的不同是它無論原來的最左邊是什麼數，統統都用 0 填充。比如，byte 是 8 位的，-1 表示為 byte 型是 11111111(補碼錶示法） b>>>4 就是無符號右移 4 位，即 00001111，這樣結果就是 15。(小聲嗶嗶，別問我有沒有無符號左移，等你真正融會貫通之後，你會發現這是一個很 low 的問題。）

<code>public static void main(String[] args) {
     System.out.println("16>>2 運算的結果是 :"+((16)>>2));
     //打印的結果是:   16>>2 運算的結果是 :4
}
public static void main(String[] args) {
     System.out.println("-16>>2 運算的結果是 :"+((-16)>>2));
     //打印的結果是:   -16>>2 運算的結果是 :-4
}

public static void main(String[] args) {
     System.out.println("16>>>2 運算的結果是 :"+((16)>>>2));
     //打印的結果是:   16>>>2 運算的結果是 :4
}

public static void main(String[] args) {
     System.out.println("-16>>>2 運算的結果是 :"+((-16)>>>2));
     //打印的結果是:   -16>>>2 運算的結果是 :1073741820
}/<code>

不用乘除算乘除

加法

以 13+9 為例，我們像這樣來拆分這個運算過程：

步驟一：不考慮進位，分別對各位數進行相加，結果為存為 sum，個位數 3 加上 9 為 2；十位數 1 加上 0 為 1；最終結果為 12；
步驟二：只考慮進位，結果存為 carry，3 + 9 有進位，進位的值為 10；
步驟三：如果步驟二所得進位結果 carry 不為 0，對步驟一所得 sum 以及步驟二所得 carry，重複步驟一、二、三。如果 carry 為 0 則結束，最終結果為步驟一所得 sum。

這裡其實就是對 sum = 12 和 carry = 10 重複以上三個步驟

(a) 不考慮進位，分別對各位數進行相加，sum = 22;
(b) 只考慮進位: 上一步沒有進位，所以 carry = 0； (c) 步驟 2carry = 0，結束，結果為 sum = 22.

這是我們在十進制中進行的運算演示，那我們換成二進制看看是不是一樣，13 的二進制為 0000 1101，9 的二進制為 0000 1001:

第一步：不考慮進位，分別對各位數進行相加，sum = 0000 1101 + 0000 1001 = 0000 0100
第二步：考慮進位，有兩處進位，第 0 位和第 3 位，只考慮進位的結果為： carry = 0001 0010
第三步：carry == 0 ?，不為 0，重複步驟一、二、三；為 0 則結束，結果為 sum。

本例中

不考慮進位 sum = 0001 0110;
只考慮進位 carry = 0;
carry == 0，結束，結果為 sum = 0001 0110

轉換成十進制剛好是 22。其實就是三個步驟，用形象的偽代碼來理解如下，這次用 3+9 舉例。

<code>a = 0011, b = 1001;
    start;

    first loop;
    1.1 sum = 1010
    1.2 carry = 0010
    1.3 carry != 0 , go on;

    second loop;
    2.1 sum = 1000;
    2.2 carry = 0100;
    2.3 carry != 0, go on;

    third loop;
    3.1 sum = 1100;
    3.2 carry = 0000;
    3.3 carry == 0, stop; result = sum;

en
/<code>

<code>//1、遞歸形式實現
int add(int a ,int b){
    if (b == 0)
        return a;
    else{
        int carry = (a & b) << 1;
        a = a ^b;
        return add(a,carry);
    }
}

//非遞歸形式實現
int add2(int a ,int b){
   int carry;
   while (b != 0){
   carry = (a & b) << 1;
       a = a ^b;
       b = carry;
   }
   return a;
}/<code>

減法

我們知道了位運算實現加法運算，那減法運算就相對簡單一些了。我們實現了加法運算，自然的，我們會想到把減法運算 11 - 6 變形為加法運算 11 + (-6)，即一個正數加上一個負數。是的，很聰明，其實我們的計算機也是這樣操作的，那有的人會說為什麼計算機不也像加法器一樣實現一個減法器呢？對的，這樣想當然是合理的，但是考慮到減法比加法來的複雜，實現起來比較困難。為什麼呢？我們知道加法運算其實只有兩個操作，加、進位，而減法呢，減法會有借位操作，如果當前位不夠減那就從高位借位來做減法，這裡就會問題了，借位怎麼表示呢？加法運算中，進位通過與運算並左移一位實現，而借位就真的不好表示了。所以我們自然的想到將減法運算轉變成加法運算。怎麼實現呢？

剛剛我們說了減法運算可轉變成一個正數加上一個負數，那首先就要來看看負數在計算機中是怎麼表示的。

+8 在計算機中表示為二進制的 1000，那-8 怎麼表示呢？很容易想到，可以將一個二進制位（bit）專門規定為符號位，它等於 0 時就表示正數，等於 1 時就表示負數。比如，在 8 位機中，規定每個字節的最高位為符號位。那麼，+8 就是 00001000，而-8 則是 10001000。這只是直觀的表示方法，其實計算機是通過 2 的補碼來表示負數的，那什麼是 2 的補碼（同補碼，英文是 2’s complement，其實應該翻譯為 2 的補碼）呢？它是一種用二進制表示有號數的方法，也是一種將數字的正負號變號的方式，求取步驟：

第一步，每一個二進制位都取相反值，0 變成 1，1 變成 0（即反碼）。
第二步，將上一步得到的值（反碼）加 1。

簡單來說就是取反加一！

<code>int subtraction(int a ,int b){
     b = ~b+1;
     return this.add(a,b);
 }/<code>

乘法

考慮我們現實生活中手動求乘積的過程，這種方式同樣適用於二進制，下面我以 13*14 為例，向大家演示如何用手動計算的方式求乘數和被乘數絕對值的乘積。

圖解

從上圖的計算過程可以看出，如果乘數當前位為 1，則取被乘數左移一位的結果加到最終結果中；如果當前位為 0，則取 0 加到乘積中（加 0 也就是什麼也不做）

判斷乘數是否為 0，為 0 跳轉至步驟(4)
將乘數與 1 作與運算，確定末尾位為 1 還是為 0，如果為 1，則相加數為當前被乘數；如果為 0，則相加數為 0；將相加數加到最終結果中；
被乘數左移一位，乘數右移一位；回到步驟(1)
確定符號位，輸出結果；

<code>      //a 被乘數，b 乘數
      int multiplication(int a,int b){
          int i = 0;
          int res = 0;
          //乘數不為 0
          while (b != 0){
              //處理當前位
              //當前位是 1
             if ((b & 1) == 1){
                 res += (a << i);
                 b = b >> 1;
                 //記錄當前是第幾位
                 i++;
             }else {
                 //當前位是 0 

                 b = b >> 1;
                 i++;
             }
         }
         return res;
     }
/<code>

除法

除法運算很容易想到可以轉換成減法運算，即不停的用除數去減被除數，直到被除數小於除數時，此時所減的次數就是我們需要的商，而此時的被除數就是餘數。這裡需要注意的是符號的確定，商的符號和乘法運算中乘積的符號確定一樣，即取決於除數和被除數，同號為證，異號為負；餘數的符號和被除數一樣。計算機是一個二元的世界，所有的 int 型數據都可以用[2^0, 21,…,231]這樣一組基來表示（int 型最高 31 位）。不難想到用除數的 231,230,…,22,21,2^0 倍嘗試去減被除數，如果減得動，則把相應的倍數加到商中；如果減不動，則依次嘗試更小的倍數。這樣就可以快速逼近最終的結果。

2 的 i 次方其實就相當於左移 i 位，為什麼從 31 位開始呢？因為 int 型數據最大值就是 2^31 啊。

<code>    int division(int a,int b){
          int res;
          if(a              return 0;
          }else{
              res=division(subtraction(a, b), b)+1;
          }
          return res;
     } /<code>