【飞秋】位运算与组合搜索（二）
這篇文章接著講怎樣高效地遍歷所有的組合。同樣，假定全集的大小不大于機器字長，計算模型為 word-RAM，即諸如 +, –, *, /, %, &, |, >>, << 等此類操作皆可以在 O(1) 時間內完成。當然，一般 / 和 % 操作明顯要慢上一些，因此我們總是希望能夠盡量避免使用兩個操作。在上一篇 blog 中的子集遍歷比較簡單，基本上只用到了 +, – , & 三種操作。而組合遍歷相對要復雜得多，一些讓人不舒服的操作總是難以避免。下面將要介紹兩種完全不同的組合遍歷算法，其中一種用到了 / 操作，而另一種則使用了三目運算符。盡管不算十分完美，也應該是足夠高效啦。
--------------------------------------------------------------------------------
2 遍歷所有組合
2.1 colex & reverse colex
說到各種位運算技巧，早年從 MIT 流傳出來的一份技術報告 HAKMEM 可謂是一本黑暗圣經。在 HAKMEM 的第175條中記錄著一個非常巧妙而實用的技巧，被稱為 Gosper’s hack，它僅僅使用幾個非常簡單的算術運算和位運算，即可得到與當前所輸入的整數含有相同數目的1的下一個整數：
s = x & (-x);
r = s + x;
n = r | (((x ^ r) >> 2) / s);
在上面這段代碼中 x 是輸入，n 是輸出，為大于 x 且與 x 含1個數相同的最小整數。比如若輸入 x = 0b0101, 那么將輸出 n = 0b0110。使用這一技巧使得我們可以非常容易地生成所有組合，代碼如下：（這是一個成員函數，完整的代碼可在位運算與組合搜索（一）所附的壓縮包中找到）：
view sourceprint?1 bool next(unsigned long &x) const
2 {?
3???? if (x == last_) return false;?
4???? unsigned long r, s;?
5???? s = x & (-(long)x);?
6???? r = s + x;?
7???? x = r | (((x ^ r) >> 2) / s);?
8???? return true;?
9 }
上面代碼中的 last_ 表示的是最后一個組合。這里遍歷組合的序為 colex，最小的組合是所有1都在低位，而最大的組合（即 last_） 是當所有1都在高位。比如若全集為 {a, b, c, d, e}，我們用以上代碼遍歷其所有大小為2的子集，順序將如下表所示：
序號 值 位串 子集
1 0b00011 11000 {a, b}
2 0b00101 10100 {a, c}
3 0b00110 01100 {b, c}
4 0b01001 10010 {a, d}
5 0b01010 01010 {b, d}
6 0b01100 00110 {c, d}
7 0b10001 10001 {a, e}
8 0b10010 01001 {b, e}
9 0b10100 00101 {c, e}
10 0b11000 00011 {d, e}
現在稍微來解釋 Gosper’ hack 是怎樣工作的：
第一條語句：s = x & (-x)， 用于標識出 x 最低位的1（設最低的1右邊有 c 個0）。 e.g. 0b10110 –> 0b00010
第二條語句：r = s + x， 將 x 右端的連續一段1清零（紅色標識的部分，設這一段有 k 個1），并將前一位設為1。 e.g. 0b10110 –> 0b11000
第三條語句：n = r | (((x ^ r) >> 2) / s)， 這里先用 x 異或 r 得到 k + 1 + c 個連續的1。然后右移 2 位，再除于 s （相當于右移 c 位），得到 k – 1 位連續的1，最后添加到 r 的最右邊，打完收工。e.g. 0b11000 | 0b00001 = 0b11001
由于該 hack 中的除法實際上只是用來移位的，因此可以想辦法繞過去 （如果你實在看不順眼那個除號的話）。比如可以使用 bsr 指令計算出 c ，然后直接移位即可。但經過我的測試，發現還是直接除法來得比較快。
view sourceprint?1 // Find last bit set?
2 static inline unsigned long __fls(unsigned long x)?
3 {?
4???? __asm bsr eax, x;?
5 }
現在如果想要反向生成所有的組合那又該如何呢，其實很簡單，因為 colex 具有一種某種意義上的對稱性：某個組合的前一個組合等于這個組合的補集的下一個組合的補集。如果我們想要得到組合 x 按照 colex 的上一個組合，只需生成 ~x 的下一個組合，再取反即可：
view sourceprint?1 bool prev(unsigned long &x) const
2 {?
3???? if (x == first_) return false;?
4???? x = ~x;?
5???? next(x);?
6???? x = ~x;?
7???? return true;?
8 }
--------------------------------------------------------------------------------
2.2 cool-lex & reverse cool-lex
cool-lex，顧名思義，就是非常 cool 的 lex。cool-lex 是由 Frank Ruskey 和 Aaron Williams 發明的，如果想要詳細的了解 cool-lex 的性質，可以看一下參考文獻6。另外在這里還有一段 cool-lex 的音樂，感興趣的可以試聽一下。雖然它不怎么好聽，也顯然不可能給你帶來關于 cool-lex 的任何洞見。下面我只簡單介紹一下怎樣按照 cool-lex 或者反向 cool-lex 進行組合遍歷。
cool-lex 的生成算法是基于后綴旋轉的（如果是針對位串表示則是前綴旋轉，但下面我們都是針對二進制整數表示，也就是低位在右邊）：找到最短的以010或者110開始的后綴（如果不存在則選定全部位），然后向左旋轉1位。比如組合0b01101,? 首先找出最短的以010或者110開始的后綴（用紅色表示）：0b01101，然后將這個后綴向左旋轉1位（即循環左移1位）即得到下一個組合：0b01011。
如何借助于位運算高效的完成后綴旋轉呢，Donald 在 TAoCP 中7.2.1.3節習題55的答案中給出了一個 MMIX 實現。下面的代碼是我寫的一個C++版：
view sourceprint?01 bool next(unsigned long &x) const
02 {?
03???? if (x == last_) return false;?
04????
05???? unsigned long r, s;?
06???? r = x & (x + 1);?
07???? s = r ^ (r - 1);?
08???? r = ((s + 1) & x) ? s : 0;?
09???? x = x + (x & s) - r;?
10???? return true;?
11 }
上面代碼中的 last_ 當然也是指最后一個組合。cool-lex 中的第一個組合也是所有1在低位，即類似于這樣：0b0…01…1。最后一個組合是1個1在最高位，而其余的1在低位，即形如 0b10…01…1。這段代碼到底是怎么起作用的？你猜！我就不分析了，不過我等下會詳細解釋生成 reverse cool-lex 的代碼。下表是 cool-lex 序的一個例子（同樣，全集為 {a, b, c, d, e}，子集大小為 2）：
序號 值 位串 子集
1 0b00011 11000 {a, b}
2 0b00110 01100 {b, c}
3 0b00101 10100 {a, c}
4 0b01010 01010 {b, d}
5 0b01100 00110 {c, d}
6 0b01001 10010 {a, d}
7 0b10010 01001 {b, e}
8 0b10100 00101 {c, e}
9 0b11000 00011 {d, e}
10 0b10001 10001 {a, e}
現在來講怎樣反向遍歷 cool-lex。reverse cool-lex 被提到的不多，網上以及各種文獻上也并沒有生成 reverse cool-lex 的代碼，因此我只好自己寫了一個。想要得到高效的 cool-lex 反向遍歷代碼，首先需要一個簡單的生成規則。這個規則其實根據正向 cool-lex 的規則可以很容易地yy出來：找到最短的以100或者101開始的后綴（如果不存在則選定全部位），然后向右旋轉1位。（后來我向 Frank 請教了一下，他說這個規則的確是正確的，另外還告訴我 Aaron 的另一篇文章 “loopless generation of multiset permutations by prefix shifts” 對 reverse cool-lex 作了介紹。）
規則有了，還剩下最后一個問題，那就是怎樣借助于位運算高效的實現這個規則。下面是我的實現：
view sourceprint?01 bool prev(unsigned long &x) const
02 {?
03???? if (x == first_) return false;?
04???? unsigned long r, s, v;?
05???? v = x | 1;?
06???? r = v & (v + 1);?
07???? s = r ^ (r - 1);?
08???? v = s & x;?
09???? r = (v & 1) ? s - (s >> 1) : 0;?
10???? x = x & (~s) | r | (v >> 1);?
11???? return true;?
12 }
上面的代碼中，基本上都是非常基礎的位運算技巧，如果你對此并不熟悉，不妨看一下參考文獻1或3。首先，我們需要找到最短的以 100 或者 101 開始的后綴，這將通過下面四條語句來完成：
第一條語句：v = x | 1，將最低位置1。e.g. 0b01010 –> 0b01011
第二條語句：r = v & (v + 1)，清除右邊連續的1。 e.g. 0b01011 –> 0b01000
第三條語句：s = r ^ (r – 1)，標記最低位的1以及其后的0。e.g. 0b01000 –> 0b01111
第四條語句：v = s & x，得到后綴。e.g. 0b01111 & 0b01010 –> 0b01010
至此，滿足條件的后綴已經找出來了，下一步的工作就是將它右旋一位：
第五條語句：r = (v & 1) ? s - (s >> 1) : 0， 得到旋轉后的后綴的最高位。 e.g. 0b01111 - 0b00111 –> 0b01000
第六條語句：x = x & (~s) | r | (v >> 1)，將后綴右移一位，與最高位相或，再與其余不相干的位合并，即得到最終結果。 e.g. 0b00101
在第五條語句用到了三目運算符，這里其實也可以借助 bsr 指令繞過去。我并沒有比較哪種更快一些。
完。（做人要厚道，轉載請注明出處
--------------------------------------------------------------------------------
3 參考文獻
Henry S. W., Hacker’s Delight.
J?rg A., Matters Computational.
Donald E. K., The Art of Computer Programming: Bitwise Tricks and Techniques. Volume 4, Pre-Fascicle 1A.
Donald E. K., The Art of Computer Programming: Generating all Combinations and Partitions. Volume 4, Fascicle 3.
Beeler M., Gosper R. W., and Schroeppel R., HAKMEM
Frank R., Aaron W., The Coolest Way To Generate Combinations.
P.S. 對于我這種從小就怕寫作文的人來說，寫篇稍正式一點的技術文章實在是太辛苦了，因此關于位運算與組合搜索就先寫到這里，雖然有很多想說的還沒有談到。以后有心情了再來討論怎樣高效實現（一）中提到的映射操作及其逆操作。
關注技術文章飛秋：http://www.freeeim.com/，24小時專業轉載。
總結
以上是生活随笔為你收集整理的【飞秋】位运算与组合搜索（二）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Linux常用命令全名
- 下一篇： Javascript中“==”与“===