Java中的位運算及簡單的演算法應用介紹

眾所周知，電腦底層是二進位。而java作為一門電腦編程語言，也對二進位的位運算提供了完整的支持。

在java中，int是32位的，也就是說可以用來實現32位的位運算。方便起見，我們一般用16進位對它賦值，比如： 0011表示成16進位是 0x3, 110111表示成16進位是 0x37。

那麼什麼是位運算呢？位運算是將數據看做二進位，進行位級別的操作。主要有移位運算和邏輯運算

移位運算：

• 左移：操作符為<<，向左移動，右邊的低位補0，左邊高位捨棄，將二進位看做整數，左移1位就相當於乘以2。
• 無符號右移：操作符為>>>，向右移動，右邊的捨棄掉，左邊補0。
• 有符號右移：操作符為>>，向右移動，右邊的捨棄掉，左邊補的值取決於原來最高位，原來是1就補1，原來是0就補0，將二進位看做整數，右移1位相當於除以2。

例如：

int a = 4; // 100
a = a >> 2; // 001，等於1
a = a << 3 // 1000，變為8

邏輯運算有：

• 按位與 &：兩位都為1才為1
• 按位或 |：只要有一位為1，就為1
• 按位取反 ~： 1變為0，0變為1
• 按位異或 ^ ：相異為真，相同為假

例如：

int a = ...; 
a = a & 0x1 // 返回0或1，就是a最右邊一位的值。
a = a | 0x1 //不管a原來最右邊一位是什麼，都將設為1

我們來看幾個簡單的應用場景：

場景一：判斷奇偶

分析：奇數都不是2的整數倍，轉換成二進位後最低位必然為1，偶數則相反。利用這個特性我們可以很容易的通過位運算判斷一個整數的奇偶性。

看代碼：

    int i = 1;// 二進位存儲方式為00000000000000000000000000000001
    int j = 5;// 二進位存儲方式為00000000000000000000000000000101
    int k = 6;// 二進位存儲方式為00000000000000000000000000000110
    if ((i & j) == 1) {
      System.out.println("j的最低位為1，為奇數");
    }
    if ((i & k) == 0) {
      System.out.println("k的最低位為0，為偶數");
    }

場景二：判斷一個正整數是不是2的整數次冪

分析：我們先來看一下常見的2的整數次冪的數：2、4、8、16，轉化成二進位依次為：10、100、1000、10000，發現規律了沒有？那就是除了首位是1，其他全是0。恰巧這些數減去1後等於他們依次按位取反的結果，比如8-1=7，二進位是111，可以通過8的二進位1000按位取反得到。而8&7=0，提取一下規律就是：

(n&(n-1))==0

符合這個規律的n就是2的整數次冪了。

場景三：簡單的集合處理

不廢話，直接看代碼：

public class SimpleSet {
  public static final int A = 0x01;// 最後四位為0001
  public static final int B = 0x02;// 最後四位為0010
  public static final int C = 0x04;// 最後四位為0100
  public static final int D = 0x08;// 最後四位為1000

  private int set = 0x00;// 初始0000，空集合

  public void add(int i) {// 將i對應位的值置為1，重覆add不影響。預設傳入值為ABCD之一，此處省去邊界判斷
    set |= i;
  }

  public boolean contain(int i) {// 判斷相應位置是否為1
    return (set & i) == i;
  }

  public boolean remove(int i) {// 來不及不解釋了快看代碼
    if (contain(i)) {
      set -= i;
      return true;
    } else {
      return false;
    }
  }
}

測試一下：

  public static void main(String[] args) {
    SimpleSet set = new SimpleSet();
    System.out.println(set.contain(A));
    set.add(B);
    System.out.println(set.contain(A));
    System.out.println(set.contain(B));
    set.add(A);
    set.add(C);
    System.out.println(set.contain(A));
    set.remove(A);
    System.out.println(set.contain(A));
    System.out.println(set.remove(A));
    System.out.println(set.contain(C));
  }

輸出為：

false
false
true
true
false
false
true

好的，沒有問題。

大家可能會覺得，上面的示例代碼中的A、B、C、D有點類似於枚舉，事實上jdk源碼中的關於枚舉的集合類EnumSet使用的就是類似的方案，當然比這個複雜得多，有興趣的可以去翻一下源碼，這個方案它有個名字，叫位向量

結語：

位運算是電腦最擅長的運算，jdk的源碼中也大量地使用了它，搞明白它有助於我們更加深入的理解電腦，也有助於我們寫出更優雅的代碼。