將只有兩種狀態(tài)的一組對象用二進制進行表示是一種常用建模方法，因此位運算技巧是比較重要的。

位操作經(jīng)典題目：
37. 解數(shù)獨 這題的位運算有點秀
劍指 Offer 15. 二進制中1的個數(shù) LCOF 類似于Integer.bitCount()的功能

• 代替數(shù)組用來表示字符出現(xiàn)與否/出現(xiàn)次數(shù)是奇數(shù)還是偶數(shù)

模擬小寫字典字符，出現(xiàn)與否：
面試題 01.01. Is Unique LCCI

    public boolean isUnique(String astr) {
        int count = 0;
        for (int i = 0; i < astr.length(); ++i) {
            int move = astr.charAt(i) - 'a';
            if ((count & 1 << move) == 0) {
                count |= 1 << move;
            } else {
                return false;
            }
        }
        return true;
    }

模擬小寫字典字符（總共26個），使用int類型（32位，每一位記錄不同的字符是否出現(xiàn)）足夠了。注意題目中，使用|=是可以的，但是+=是不可以的，如果出現(xiàn)次數(shù)多可能會出現(xiàn)進位。

模擬128個ASCII字符，統(tǒng)計出現(xiàn)次數(shù)是奇數(shù)還是偶數(shù)：
面試題 01.04. Palindrome Permutation LCCI
用兩個long，每一位對應于某一個ASCII字符。并且使用亦或來統(tǒng)計出現(xiàn)次數(shù)是奇數(shù)還是偶數(shù)。
因為long是64位的，int是32位的，所以如果使用long只需要2個分別代表高64位和低64位即可。如果用int則需要4個。

    public boolean canPermutePalindrome(String s) {
        long highBitmap = 0;
        long lowBitmap = 0;
        for (char ch : s.toCharArray()) {
            if (ch >= 64) {
                highBitmap ^= 1L << ch - 64;
            } else {
                lowBitmap ^= 1L << ch;
            }
        }
        return Long.bitCount(highBitmap) + Long.bitCount(lowBitmap) <= 1;
    }

這里有一個易錯點，也是long類型使用中的易錯點，如果上面代碼中的1L寫成了1，代碼會出錯。因為1默認為int類型，只有32位，如果左移的位數(shù)超過32，則會從0重新開始。比如'A'是第65個字符， 1左移一位，highBitmap做了亦或之后是2。'a'是第97個字符，1 <<(97 - 64) 相當于1 << 33，因為對于32位的int來說只能左移0-31位，如果是33相當于33%32 == 1，即最后效果是左移一位。這回導致“Aa”會判定某一位出現(xiàn)次數(shù)為偶數(shù)。

• 判斷奇數(shù)、偶數(shù)
  用num&1代替num % 2

• 1的探針：n & (1 << i)
  測試n的從右往左數(shù)第i位是否為1

• b & (?b) 得到 bb 二進制表示中最低位的 1。
  解釋：
  two's complement: -b = ~b + 1
  我們假設b的二進制表示：111000
  -b = ~b + 1， 即000111 + 1 = 001000
  111000 & 001000= 001000
  直觀地來理解一下，~ b和b是完全相反的，+1會使~b最低位的連續(xù)的 1 都變?yōu)?0，而~b最低位的 0變?yōu)?1，從而這些變化的位與原來的b是相同的，位與運算之后會得到保留（即保留了b最低位的連續(xù)的 0和b最低位的 1）。
  如果想要知道這個1位于從右往左數(shù)的哪一位
  可以使用

Integer.bitCount(digitMask - 1)

• mask &= (mask - 1) 抹去最低位的1
  mask：101010
  mask - 1：101001
  mask &= (mask - 1) ： mask = 101000
  還有一種操作：
  上面我們用b & (?b) 得到了最低位的1，用亦或也可以抹去。
  b ^ (b & (?b)) = 111000 ^ 001000 = 110000

• 亦或的巧用
  亦或可以用作開關，這點可以參考37. 解數(shù)獨 。
  里面flip方法使用了下面這種亦或

line[i] ^= (1 << digit);

在回溯中連續(xù)調(diào)用兩次，可以打到選中/取消的效果（輸入1，原來是0變成1，原來是1變成0）

flip(i, j, digit);

• 一些小坑點：
  使用位運算的時候，一定要小心語法錯誤，等于的判斷優(yōu)先級高于位運算的優(yōu)先級，因此類似于這種判斷是錯誤的，int不能和boolean進行位運算（先進行了==后進行&）

if (input & (input - 1) == 0) 
//應該寫成：
if ((input & (input - 1)) == 0) 

參考