De Bruijn sequence
本文是寫程式產生 De Bruijn sequence 的副產品，因此純為筆記性質，科普文可參考： 数学魔术：难倒数学家的表演
De Bruijn sequence B(k, n) 是一種 sequence，由 k 種不同符號組成，且其所有長度為 n 之連續子序列恰為 k 種符號組成長度為 n 的所有排列。 例如：00010111 即為一 B(2, 3) 序列，因其連續子序列（尾端循環至開頭） 000, 001, 010, 101, 011, 111, 110, 100 恰為所有由 {0, 1} 組成且長度 3 的序列。
若由 k 種符號組成之所有長度為 n 之序列表為有向圖中的頂點，則圖中有 k^n 個頂點， 若頂點 m 去掉第一個符號並在尾端添加一符號可得頂點 n，則有一有向邊由 m 指向 n，此即 De Bruijn graph。 例如：k = 2, n = 3 的圖中，頂點 010 有兩條對外的邊，分別指向 101 及 100。
在 De Bruijn graph 中之 Hamiltonian path 即為 De Bruijn sequence，下方左圖中紅色有向邊即為一組 Hamiltonian path， 圖中可見對應之 De Bruijn sequence 為 10111000，且此組 Hamiltonian path 等價於長度 2 的 De Bruijn graph 中的一組 Eulerian cycle， 下方右圖邊上標記的即為對應之順序。
 |
 |
| k = 2, n = 3 | k = 2, n = 2 |
k = 3（使用符號 0, 1, 2）的狀況同樣可畫出 De Bruijn graph，左圖中標記的 Hamiltonian path 為 102112200，右方同樣是等價的 Eulerian cycle。
 |
 |
| k = 3, n = 2 | k = 3, n = 1 |
應用：
0100101000100000 <- 第 6 個位置為 1，所以輸出 5（計算 0-base 的位置，也可以想像成是算最後有幾個 0）
在這邊先假設n為機器上表示一個整數所使用的位元數，以 n = 32 來示範。
首先可以把題目簡化，假定x中只有一個 bit 為 1，如果 x 中有兩個以上的 bit 為 1，
可以利用 x &= (~x + 1) 來把最後一個 1 分離。（x &= -x 也可以，如果是二的補數表示法）
當分離出來之後，就有很多種計算法了，這邊就不考慮用組合語言的解法。
[...略...]
第六種是利用 de Bruijn sequence。
其實這方法跟第五種方法很像，也是設計一個 perfect hash function。
只是這方法免除了取餘數的運算，同時也只需要大小為 32 的 table。
hash function 是 (x * 0x077CB531) >> 27 其中的 0x077CB531 就是 de Bruijn sequence。
這方法對於 n 是二的次方數的機器都可以使用，至於 n 不是二的次方數的機器應該不多。
這方法的原理從兩個方面來看，第一個是x本身一定是二的次方數，
所以任何一個數字乘以 x，就相當於左移的運算。
而 de Bruijn sequence 的特殊之處，就是在於此序列中的任意連續五位元都是相異的。
五個位元總共有三十二種可能性，而至少要有三十二個位元才有可能包含所有三十二種可能性
（序列要想成頭尾相接的）
舉例：00010111就包含了 000, 001, 010, 101, 011, 111, 110, 100 這八種三位元的所有組合。
所以當 de Bruijn sequence 乘以 x 又右移27個位元的時候，就相當於是把 sequence 中的一組五位元子序列取出，
這保證不同的x一定會有不同的子序列，所以是一個很好的 hash 函數。
（32 位元的 de Bruijn sequence 有很多個，但是這方法要用的時候必須挑 00000 開頭的）
關於第六種方法的詳細研究可以參考下面這網址，
裡面還有說當一個數字有兩個 bit 為 1 的時候，怎樣可以快速找出來
http://supertech.csail.mit.edu/papers/debruijn.pdf
-- FRAXIS, [心得] Bit index和de Bruijn sequence