位運算應用和工具

有時需要追求效率，會代替一些算術運算。

• 求商：a >> n  <=>  a / 2^n
• 求積：a << n  <=>  a * 2^n
• 求餘：a & ((1 << n) - 1)  <=>  a % 2^n
• 奇偶判斷：a & 1 == 1  <==>  a % 2 == 1

一般1表示選中或者開啟項，0表示未選或者關閉項。

• 獲取全部項：(1 << n) - 1
• 獲取指定項：1 << idx
• 獲取反選項：~a
• 開啟指定項：a |= b
• 合併兩選項：a | b
• 關閉指定項：a &= ~b
  說明：a中的項，遇到1時變0，遇到0時不變。
• 查看公共項：a & b
• 保留指定項：a &= b
  說明：a中的項，遇到0時變0，遇到1時不變。
  
• 切換指定項：a ^= b
  說明：a中的項，遇到0時不變，遇到1時變化，0變1，1變0。
• 查看改變項：a1 ^ a2
  說明：a1是變化前，a2是變化後，a1 ^ a2就可以計算出前後的變化項。
• 查看未變項：~(a1 ^ a2) = ~a1 ^ a2 = a1 ^ ~a2

輸出組合，如下示例，輸出abcd的組合。

public static void main(String[] args) {
    char[] chars = "abcd".toCharArray();
    int len = chars.length;
    
    int bits = (1 << len) - 1;
    for (int i = bits; i > 0 ; i = (i - 1) & bits) {
        System.out.printf("%" + len + "s：", Integer.toBinaryString(i));
        for(int j = 0; j < len; j++) {
            if(((i >> j) & 1) == 1)
                System.out.print(chars[j]);
        }
        System.out.println();
    }
}

輸出結果：

1111：abcd
1110：bcd
1101：acd
1100：cd
1011：abd
1010：bd
1001：ad
1000：d
 111：abc
 110：bc
 101：ac
 100：c
  11：ab
  10：b
   1：a

位移註意事項：

• >>是帶符號右移，即正數時左邊補0，負數時左邊補1。
• >>>是無符號右移，即總是左邊補0。

Long.bitCount(long)，Integer.bitCount(int)：計算1的數量。

BitSet：用於表示可以比long更長的存儲位數。

• int cardinality()，計算1的數量。
• and(BitSet)，與運算，即保留指定項，a &= b。boolean intersects(BitSet)，判斷是否存在公共項。
• or(BitSet)，或運算，即開啟指定項，a |= b。
• xor(BitSet)，異或運算，切換指定項，即a ^= b。flip(...)，切換指定項，即a ^= b。
• andNot(BitSet)，與非運算，即關閉目標項，a &= ~b。
• int length()，獲取長度。boolean isEmpty()，判斷長度是否為0。
• set(...)，開啟指定項。clear(...)，關閉指定項。set(..., boolean)，設置指定項的值。clear()，關閉所有項，並清空，即長度重置為0。
• boolean get(int)，獲取指定項的開關值。
• int previousSetBit(int)/int nextSetBit(int)：從指定位置開始查找上一個/下一個開啟項的索引。
• int previousClearBit(int)/int nextClearBit(int)：從指定位置開始查找上一個/下一個關閉項的索引。
• BitSet get(int, int)：截取子集。
• 構造：s+valueOf(ByteBuffer/byte[]/LongBuffer/long[])
• 轉換：toLongArray()/toByteArray()

參考文章：http://blog.csdn.net/u011039332/article/details/49967559