前幾天聽了 CMU 一大神的算法公開課，算是近距離見識了算法大神的冰山一角，管中窺豹，可見一斑。

先稍微介紹一下大神，方便感興趣的童鞋進一步了解他。

• 姓名：王赟 Maigo

• Maigo 的知乎專欄
• Maigo 的 Github

想了解更多的就自己谷歌吧。知乎專欄就夠看好久的了。

我寫這篇文字的目的很簡單，

1. 分享給需要的和感興趣的同學
2. 看了好幾遍視頻，還是想自己從頭到尾復述一遍以加深印象，熟悉 bit 的操作。

算法的所有代碼，java 版本和 swift 版本，我都放在了我的 Github 上。當然還有歡迎訂閱我的博客。

為了找工作過 OA 關，也是沒辦法用 swift，更不想用 C++，還不如臨時學 java 來的效率點。所以這里就用 java 代碼來講解一下。我這里用的是 “15 queens”，共5個方法，第四個開始速度有了質的提升，但需要第三個方法的基礎，反正后一個的提升都基于前一個。

Queen 1

我自己的電腦上跑的時間是// Time elapsed: 28423ms。用的是最基礎的回溯法（back tracking）。最后就不把所有的解都打印出來了，打印的時間其實和算法本身關系并不大，而且因為是15 皇后，容易死機。

public class Main {
    private static final int n = 15;
    private static int count = 0;
    private static int[] sol;
    
    public static void main(String[] args) {
        sol = new int[n];
        long tic = System.currentTimeMillis();
        DFS(0);
        long toc = System.currentTimeMillis();
        System.out.println("Total solutions: " + count);
        System.out.println("Time elapsed: " + (toc - tic) + "ms");
    }
    
    private static void DFS(int row) {
        for (int col = 0; col < n; col++) {
            boolean ok = true;
            // 注意下面這個循環(huán)，后面會做改進
            for (int i = 0; i < row; i++) {
                if (col == sol[i] || i - row == sol[i] - col || i - row == col - sol[i]) {
                    ok = false;
                    break;
                }
            }
            if (!ok) continue;
            sol[row] = col;
            if (row == n - 1) {
                count++;
            } else {
                DFS(row + 1);
            }
        }
    }
}

Queen 2

Queen1 的時間是：// Time elapsed: 28423ms
這個方法的時間是：// Time elapsed: 16024ms

這里就需要開始介紹一個小竅門，因為上面的方法，每次都要和之前的所有行相比較（看上面代碼的注釋部分），如果我們可以用一個 boolean 數(shù)組，記錄下每一列，每一個對角線的情況，就可以不用所有都比較了。那么如何求行和列呢

Paste_Image.png

如上圖，一共有 2n － 1 個對角線，大神是語言研究所的博士生，他用的是中文的“豎”，“撇”和“捺”來表示兩種對角線，可以很容易知道它們的 index 就是 0 -> 2n - 2。所以上面的代碼注釋部分就可以改成：

int j = col + row, k = n - 1 + col - row;
if (shu[col] || pie[j] || na[k]) continue;

就是如果當前列和對角線都被占用的話，就直接 continue。當然我們還需要設置和清除。把已經(jīng)被占用的設為 true，一趟完事了就重新設為 false。

shu[col] = true; pie[j] = true; na[k] = true;
DFS(row + 1);
shu[col] = false; pie[j] = false; na[k] = false;

Queen 3

Queen1 ：// Time elapsed: 28423ms
Queen2 ：// Time elapsed: 16024ms
這個方法：// Time elapsed: 10302ms

從這個方法開始引入 bit array，關鍵點是:

用 32 位的 bit array（也就是一個整數(shù)（int）的長度），代替 32 位長度的 boolean 。

位運算的基本操作是：與，或，異或，取反，左移，右移。很容易理解，這里瞬間就節(jié)省了超多的空間。也很容易就想到這里并不會節(jié)省時間很多時間，因為整個的流程是沒什么太大的區(qū)別的。所以上面的 boolean[] shu, pie, na; 就成了 int shu, pie, na;，默認為 0。上面的判斷條件也成了

if ((((shu >> col) | (pie >> (col + row)) | (na >> (n - 1 + col - row))) & 1) != 0) continue;

這個乍一看有點復雜，先看一下這個 bit 是如何模擬數(shù)組操作的，其實就是讀和寫：

－ 寫
把第 i 位置1：a |= (1 << i)
把第 i 位置0: a &= ~(1 << i)
把第 i 位取反：a ^= (1 << i)
－ 讀
讀取第 i 位的值：(a >> i)&1

所以上面那個條件其實就是取第col位的值 (shu >> col) & 1，每個都是這樣，所以就先把三個都|或起來，再和 1 &與。操作是等價的，存儲空間不同而已。后面的設置與清除也成了：

shu ^= (1 << col); pie ^= (1 << (row + col)); na ^= (1 << (n - 1 + col - row));

就是把shu的第col位置1，本來是0，取反就成了1。用異或的好處就是清除和設置的代碼相同，更方便。

Queen 4

Queen1 ：// Time elapsed: 28423ms
Queen2 ：// Time elapsed: 16024ms
Queen3 ：// Time elapsed: 10302ms
這個方法：// Time elapsed: 1962ms

可以從上面這個時間比較看出來瞬間少了個數(shù)位。因為這一方法用到了系統(tǒng)級別的運算，利用了 bit array 可以一步操作多位的優(yōu)勢，不像一般的 array，必須要一個一個操作，而 bit array 可以在一個整形的長度內，O(1) 時間任意存取任意位置的數(shù)。為了更好的理解這個方法，這里我們需要介紹另一個 bit 的操作，取最后一個 1:

a & -a

懂負數(shù)的原理就很容易理解了，負數(shù)就是取反＋1。例子：

a = 0001100
-a = 1110011 + 1 = 1110100
a & -a = 0000100

枚舉 bit array 中的1，就是：

while(a != 0) {
    int p = a & -a; // p 就是取出來的 1
    a ^= p;
    Do something with p; 
}

之前是枚舉每個位置，然后檢查是否沖突，而現(xiàn)在我們可以利用這點，直接枚舉不沖突的位置。那么在第 row 行，相應的shu，pie，na中沖突的位置在哪里呢？

shu 沖突的位置：shu
pie 沖突的位置：pie >> row
na 沖突的位置：na >> (n - 1 - row)

就是之前式子 pie[row ＋ col], na[n - 1 + col - row] 的一個變形，用 bit array 來代替普通的 boolean array。所以現(xiàn)在這個 DFS 方法就成了：

private static void DFS(int row) {
        int ok = ((1 << n) - 1) & ~(shu | (pie >> row) | (na >> (n - 1 - row)));
        while (ok != 0) {
            int p = ok & -ok;
            ok ^= p;
            if (row == n - 1) {
                count++;
            } else {
                shu ^= p; pie ^= (p << row); na ^= (p << (n - 1 - row));
                DFS(row + 1);
                shu ^= p; pie ^= (p << row); na ^= (p << (n - 1 - row));
            }
        }
    }

Queen 5

Queen1 ：// Time elapsed: 28423ms
Queen2 ：// Time elapsed: 16024ms
Queen3 ：// Time elapsed: 10302ms
Queen4 ：// Time elapsed: 1962ms
這個方法：// Time elapsed: 1350ms

為了更好的理解這個方法，這里有個 google developer 的文檔，講的是 Propagation and backtracking。所謂的 Propagation，就是：

Propagation consists of taking some constraint—which might be a constraint of the original problem, or a constraint learned or hypothesized along the way—and applying it to variables.

利用之前學到的，來限制接下來的。

這個方法中，我們把 shu，pie，na 都當成形參，把當前行學到的“不能放”的限制信息，保留到下一行，從而限制下一行的決策。這也就是 Propagation 的意思。所以我們的代碼也就成了

public class Main {
    private static final int n = 15;
    private static int count = 0;
    
    public static void main(String[] args) {
        long tic = System.currentTimeMillis();
        DFS(0, 0, 0, 0);
        long toc = System.currentTimeMillis();
        System.out.println("Total solutions: " + count);
        System.out.println("Time elapsed: " + (toc - tic) + "ms");
    }
    
    private static void DFS(int row, int shu, int pie, int na) {
        // shu, pie, na 當前行的位置不能放
        int ok = ((1 << n) - 1) & ~(shu | pie | na);
        while (ok != 0) {
            int p = ok & -ok;
            ok ^= p;
            if (row == n - 1) {
                count++;
            } else {
                // 把當前行的 shu，pie，na 設為 0，從而之后的所有行都不能放
                DFS(row + 1, shu ^ p, (pie ^ p) >> 1, (na ^ p) << 1);
            }
        }
    }
}