原文連結
前言
位運算在生産或算法解題中并不常見，不過如果你用得好，可以達到事半功倍的效果，而且位運算用得好，也可以極大地提升性能，如果在生産或面試中能看到使用位運算來解題，會讓人眼前一亮，覺得你還是 有點逼格 的，巧用位運算，不僅會提升性能，還會讓代碼的可讀性更好，達到四兩撥千斤的效果，今天我們就來學學位運算在解題中的一些技巧，最後會用位運算來看看怎麼解八皇後這道大 Boss 題，相信你看完肯定會有收獲！
本文将會從以下幾個方面來講解位運算：
- 什麼是位運算，位運算常見操作
- 位運算使用技巧簡介
- 巧用位運算解算法題
在現代計算機中所有的資料在記憶體中都是以二進制存在的，位運算就是直接對整數在記憶體中的二進制位進行操作，由于位運算直接對記憶體資料進行操作，無需轉成十進制，是以使用位運算的處理速度是很快的。
舉個簡單的例子， 當我們要計算 6 & 4 的結果，在做位運算的時候首先要把 6，4 轉成二進制，然後再做相應的位操作（與）。
基本的位運算有與、或、異或、取反、左移、右移這6種，介紹如下：
& 與：隻有當兩位都是 1 時結果才是 1，否則為 0 。
0110
& 0100
-----------
0100 | 或：兩位中隻要有 1 位為 1 結果就是 1，兩位都為 0 則結果為 0。
0110
& 0110
-----------
0110 ^ 異或：兩個位相同則為 0，不同則為 1
0110
^ 0100
-----------
0010 ~ 取反：0 則變為 1，1 則變為 0
~ 0110
-----------
1001
<< 左移：向左進行移位操作，高位丢棄，低位補 0
int a = 8;
a << 3;
移位前：00000000000000000000000000001000
移位後：00000000000000000000000001000000 >> 右移：向右進行移位操作，對無符号數，高位補 0，對于有符号數，高位補符号位。
unsigned int a = 8;
a >> 3;
移位前：00000000000000000000000000001000
移位後：00000000000000000000000000000001
int a = -8;
a >> 3;
移位前：11111111111111111111111111111000
移位後：11111111111111111111111111111111 接下來我們就由淺入深地來學習一下使用位運算的那些黑科技
1、 判斷整型的奇偶性
使用位運算操作如下
if((x & 1) == 0) {
// 偶數
} else {
// 奇數
} 這個例子相信大家都見過，隻需判斷整型的第一位是否是 1 即可，如果是說明是奇數，否則是偶數
2、 判斷第 n 位是否設定為 1
if (x & (1<<n)) {
// 第 n 位設定為 1
}
else {
// 第 n 位設定為 1
} 在上例中我們判斷第一位是否為 1，是以如果要判斷第 n 位是否 1，隻要把 1 左移 n 位再作與運算不就完了。
3、 将第 n 位設定為 1
y = x | (1<<n) 思路同第二步，先把 1 移到第 n 位再作或運算，這樣第 n 位就肯定為 1。
4、 将第 n 位設定為 0
y = x & ~(1<<n) 先将 1 左移到 第 n 位，再對其取反，此時第 n 位為 0，其他位都為 1，這樣與 x 作與運算後，x 的第 n 位肯定為 0。
5、将第 n 位的值取反
y = x ^ (1<<n) 我們知道異或操作是兩個數的每一位相同，結果為 0，否則是 1，是以現在把 1 左移到第 n 位，則如果 x 的第 n 位為 1，兩數相同結果 0，如果 x 的第 n 位為 0，兩數不相同，則為 1。來看個簡單的例子
01110101
^ 00100000
--------
01010101
如圖示，第五位剛好取反
6、 将最右邊的 1 設為 0
y = x & (x-1) 如果說上面的 5 點技巧有點無聊，那第 6 條技巧确實很有意思，也是在 leetcode 經常出現的考點，下文中大部分習題都會用到這個知識點，務必要謹記！掌握這個很重要，有啥用呢，比如我要統計 1 的位數有幾個，隻要寫個如下循環即可，不斷地将 x 最右邊的 1 置為 0，最後當值為 0 時統計就結束了。
count = 0
while(x) {
x = x & (x - 1);
count++;
}
先介紹這麼多吧，如果大家對其他的位運算技巧感興趣可以看看文末的參考連結。
接下來我們看看位運算在算法題中的應用。
1、 高頻面試題：老鼠試毒
有 8 個一模一樣的瓶子，其中有 7 瓶是普通的水，有一瓶是毒藥。任何喝下毒藥的生物都會在一星期之後死亡。現在，你隻有 3 隻小白鼠和一星期的時間，如何檢驗出哪個瓶子裡有毒藥？
解題步驟如下：
1、 把這 8 個瓶子從 0 到 7 進行編号，用二進制表示如下
000
001
010
011
100
101
110
111 2、 将 0 到 7 編号中第一位為 1 的所有瓶子（即 1，3，5，7）的水混在一起給老鼠 1 吃，第二位值為 1 的所有瓶子（即2，3，6，7）的水混在一起給老鼠 2 吃， 第三位值為 1 的所有瓶子（4，5，6，7）的水混在一起給老鼠 3 吃，現在假設老鼠 1，3 死了，那麼有毒的瓶子編号中第 1，3 位肯定為 1，老鼠 2 沒死，則有毒的瓶子編号中第 2 位肯定為 0，得到值 101 ，對應的編号是 5， 也就是第五瓶的水有毒。
這道題及其相關的變種在面試中出現地比較頻繁，比如我現在把 8 瓶水換成 1000 瓶，問你至少需要幾隻老鼠才能測出有毒的瓶子，有了上述的思路相信應該不難，幾隻老鼠就相當于幾個進制位，顯然 2^10 = 1024 > 1000，即 10 隻老鼠即可測出來。
2、 利用位運算來解八皇後問題
接下來我們來看看終級 Boss 題，如何用位運算來解八皇後問題，解題中運用到了非常多的位運算技巧，相信你學完會收獲不少。
在 8×8 格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法
舉個簡單的下圖所示的例子，如果在棋盤上放置一個皇後，則與這個皇後同一行，同一列，且皇後所在斜線經過的格子不能再放其他皇後。
如圖示，在其中任意一行放置一個皇後，則與此皇後同行，同列，同對角線的都不允許再放其他皇後，圖中藍色區塊不允許放其他皇後。
一般我們用回溯法解八皇後。這裡簡單介紹一下啥是回溯法。
在第一行從左到右先選擇一個位置放置皇後，由于第一行放了皇後，第二行可放皇後的位置受到了限制（下圖藍色區塊表示對應行的格子不能放皇後）
如圖示,第二行放皇後的位置隻能從第三個格子開始選
第二行我們選第三個格子放皇後，選完開始在第三行選，第三方可選的位置也受到了第一，二行皇後所放位置的影響
如圖示，第三行隻能從第五個格子開始放置皇後
同理，第三，四，五行都從左到右選擇符合條件的的格子放置皇後，選完後問題來了，第六行所在行沒有可選的位置了！如圖示
怎麼辦呢，回溯！重新擺放第五行的皇後，将其放到第八格上
重新擺放後發現第六行還是沒有符合條件的格子，咋辦，我們知道第六行可擺放皇後的格子受第五行影響，而第五行受第四行擺放皇後位置的影響的，是以回溯到第四行，将皇後位置擺放到目前行的其他位置（第七格），再接着往下放 5，6，7，8 行的皇後。。。，隻要不滿足條件，改變上一層的的條件重新來，上一層調整後還是不符合條件，再調整上上層的。。。，調整完後重新往下遞歸選擇，直到找到符合條件的，找到之後再在第一層換一個位置選皇後遞歸往下層選擇執行，直到找到所有的解，這種不滿足條件就回退上層調整再試的思想就是回溯法，可以看到回溯法一般是用遞歸實作的。
回溯算法有不少變種，這裡我們重點介紹使用位運算的回溯算法，它是所有解法中最高效的！如果在面試中能使用位運算來解回溯算法，絕對會讓面試官給你個大大的贊！
接下來是重點了，怎麼用位運算來求解。
在以上回溯法的分析中，我們不難發現，在八皇後問題中，問題的關鍵是找出行可放皇後的格子。找到之後問題就解決了 90%，是以接下來我們就來看看怎麼找這些可用的格子。
假設我們要求解第三行可放皇後的格子（說明一二行的皇後已放好了）那麼第三行可放皇後的位置受到哪些條件的限制呢。顯然在第一二行已放皇後的格子所在的列，左斜線，右斜線對應的方格都不能放皇後，如圖示:
我們以 column 來記錄所有上方行已放置的皇後導緻目前行格子不可用的集合，所在列如果放了皇後，則目前行格子對應的位置為 1，否則為 0，同理,以 pie（撇，左斜線） 記錄所有已放置的皇後左斜方向導緻目前行格子不可用的集合， na（捺，右斜線） 表示所有已放置的皇後右斜方向導緻目前行不可用的集合。則對于第三行來說我們有：
column = 10010000 (上圖中的第一個圖，第 1，4 列放了皇後，是以 1，4 位置為 1，其他位置為 0）
pie = 00100000 (上圖中的第二個圖，左斜線經過第三行的第三個方格，是以第三位為 1）
na = 00101000 (上圖中的第三個圖，右斜線經過第三行的第三, 五個方格，是以第三,五位為 1） 将這三個變量作或運算得到結果如下
10010000
| 00100000
| 00101000
-----------------------
10111000 也就是說對于第三層來說第 1，3，4，5 個格子不能放皇後。如圖示
于是可知 column | pie | na 得到的結果中值為 0 的代表目前行對應的格子可放皇後， 1 代表不能放，但我們想改成 1 代表格子可放皇後， 0 代表不可放皇後，畢竟這樣更符合我們的思維方式，怎麼辦，取反不就行了，于是我們有~(column| pie | na)。
問題來了，這樣取反是有問題的，因為這三個變量都是定義的 int 型，為 32 位，取反之後高位的 0 全部變成了 1，而我們隻想保留低 8 位（因為是 8 皇後），想把高位都置為 0，怎麼辦，這裡就要用到位運算的黑科技了
~(column | pie | na) & ((1 << 8)-1) 後面的的 ((1<< 8) -1) 表示先把 1 往左移 8 位，值為 100000000,再減 1 ，則低 8 位全部為 1，高位全部為 0！（即 0011111111）再作與運算，即可保留低 8 位，去除高位。
費了這麼大的勁，我們終于把目前行可放皇後的格子都找出來了（所有位值為 1 的格子可放置皇後）。接下來我們隻要做個循環，周遊所有位為 1 的格子，每次取出可用格子放上皇後，再找下一層可放置皇後的格子，依此遞歸下去即可,直到所有行都周遊完畢（遞歸的終止條件）。
還有一個問題，已知目前行的 column，pie，na，怎麼确定下一行的 column，pie，na 的值（畢竟選完目前行的皇後後，要确定下一行的可用格子，而下一行的可用格子依賴于 column，pie，na 的值）
上文可知，我們已經選出了目前行可用的格子（相應位為 1 對應的格子可用），假設我們在目前行選擇了其中一個格子來放置皇後，此位置記為 p（如果是目前行的最後一個格子最後一個格子，則值為 1，如果放在倒數第二個，值為 10，倒數第三個則為 100，依此類推），則對于下一行來說，顯然 column = column | p
那麼 pie 呢，仔細看下圖，顯然應該為 (pie | p) << 1, 左斜線往下一行的格子延展時，相當于左移一位，
如圖示：下一行的 pie 顯然為 (pie | p) << 1。
同理 下一行的 na 為 (na | p) >> 1。
有了以上詳細地解析，我們就可以寫出僞代碼了
void queenSettle(row, colomn,pie,na) {
N = 8; // 8皇後
if (row >= N) {
// 周遊到最後一行說明已經找到符合的條件了
count++;return
}
// 取出目前行可放置皇後的格子
bits = (~(colomn|pie|na)) & ((1 << N)-1)
while(bits > 0) {
// 每次從目前行可用的格子中取出最右邊位為 1 的格子放置皇後
p = bits & -bits
// 緊接着在下一行繼續放皇後
queenSettle(row+1, colomn | p, (pie|p) << 1, (na | p) >> 1)
// 目前行最右邊格子已經選完了，将其置成 0，代表這個格子已周遊過
bits = bits & (bits-1)
}
} 一開始傳入 queenSettle(0,0,0,0) 這樣即可得到最終的解。僞代碼寫得很清楚了，相信用相關語言不難實作，這裡就留給大家作個練習吧。
總結
本文帶大家由淺入深地完成了位運算的學習，掌握好位運算不僅僅是為了提升逼格，還能極大地提升效率，位運算也廣泛地應用于代碼編寫中，運用得當能極大地簡化代碼。
---END---
來源 | 五分鐘學算法
作者 | 程式員小吳