數(shù)學(xué)中存在這樣一個(gè)序列，它充滿魔力，在實(shí)際工程中也有一部分的應(yīng)用馅闽。今天就打算分享一下這個(gè)序列，它在 Google S2 中是如何使用的以及它在圖論中，其他領(lǐng)域中的應(yīng)用福也。這個(gè)序列就是德布魯因序列 De Bruijn孝冒。

一. 從一個(gè)魔術(shù)開(kāi)始說(shuō)起

有這樣一個(gè)撲克牌魔術(shù)。魔術(shù)師手上拿著一疊牌拟杉，給5個(gè)人(這里的人數(shù)只能少于等于32庄涡，原因稍后會(huì)解釋)分別檢查撲克牌，查看撲克牌的花色和點(diǎn)數(shù)是否都是不同的搬设，即沒(méi)有相同的牌穴店。

檢查完撲克牌，沒(méi)有重復(fù)的牌以后拿穴，就可以給這5個(gè)人洗牌了泣洞。讓這5個(gè)人任意的抽一疊牌從上面放到下面，即切牌默色。5個(gè)人輪流切完牌球凰，牌的順序已經(jīng)全部變化了。

接著開(kāi)始抽牌腿宰。魔術(shù)師讓最后一個(gè)切牌的人抽走這疊牌最上面的一張呕诉，依次給每個(gè)人抽走最上面的一張。這時(shí)候抽走了5張牌吃度。魔術(shù)師會(huì)說(shuō)甩挫，“我已經(jīng)看透了你們的心思，你們手上的牌我都知道了”椿每。然后魔術(shù)師會(huì)讓拿黑色牌的人站起來(lái)(這一步很關(guān)鍵伊者！)。然后魔術(shù)師會(huì)依次說(shuō)出所有人手上的牌间护。最后每個(gè)人翻出自己的牌亦渗，全部命中。全場(chǎng)歡呼汁尺。

二. 魔術(shù)原理揭秘

在整個(gè)魔術(shù)中法精，有三個(gè)地方比較關(guān)鍵。第一個(gè)是參與的人數(shù)只能少于等于32 均函。一副完整的撲克牌中亿虽，總共有54張牌，但是除去2張鬼牌(因?yàn)樗麄兓ㄉ挥?種)苞也，總共就52張牌洛勉。

在上述魔術(shù)中，所有的牌都用二進(jìn)制進(jìn)行編碼如迟，要想任意說(shuō)出任意連續(xù)的5張牌收毫，那么必須這副牌具有全排列的特性攻走。即枚舉所有種組合，并且每個(gè)組合都唯一代表了一組排列此再。

如果窗口大小為5昔搂，5張連續(xù)的撲克牌。二進(jìn)制編碼 2⁵ = 32 输拇，所以需要32張牌摘符。如果窗口大小為6，6張連續(xù)的撲克牌策吠，二進(jìn)制編碼 2⁶ = 64逛裤，需要64張撲克牌『锬ǎ總共牌只有52張带族，所以不可能到64張。所以32個(gè)人是上限了 蟀给。

第二個(gè)關(guān)鍵的地方是蝙砌，只有讓拿黑色的牌的人或者拿紅色的牌的人站出來(lái)，魔術(shù)師才能知道這5個(gè)人拿到的連續(xù)5張撲克牌究竟是什么跋理。其實(shí)魔術(shù)師說(shuō)“我已經(jīng)知道你們所有人拿到的是什么牌”的時(shí)候择克，他并不知道每個(gè)人拿到的是什么牌。

撲克牌除了點(diǎn)數(shù)以外薪介，還有4種花色§艚龋現(xiàn)在需要32張牌越驻，就是1-8號(hào)牌汁政，每號(hào)牌都有4種花色∽号裕花色用2位二進(jìn)制編碼记劈，1-8用3位二進(jìn)制編碼。于是5位二進(jìn)制正好可以表示一張撲克牌所有信息并巍。

如上圖目木，00110 表示的就是梅花6 。11000 表示的是紅桃8（因?yàn)闆](méi)有 0 號(hào)牌懊渡，所以000就表示8）

第一步將撲克牌編碼完成以后刽射，第二步就需要找到一個(gè)序列，它必須滿足以下的條件：由 2^n-1個(gè)1和2^n-1個(gè)0構(gòu)成的序列或者圓排列剃执，是否能存在在任意 n 個(gè)位置上0誓禁，1序列兩兩都不同。滿足這個(gè)條件的序列也稱為 n 階完備二進(jìn)圓排列肾档。

這個(gè)魔術(shù)中我們需要找的是 5 階完備二進(jìn)圓排列摹恰。答案是存在這樣一個(gè)滿足條件的序列辫继。這個(gè)序列也就是文章的主角，德布魯因序列俗慈。

上述序列就是一個(gè)窗口大小為5的德布魯因序列姑宽。任意連續(xù)的5個(gè)二進(jìn)制相互之間都是兩兩不同的。所以給觀眾任意洗牌闺阱，不管怎么洗牌炮车，只要最終挑出來(lái)是連續(xù)的5張，這5張的組合都在最終的結(jié)果之中酣溃。

將窗口大小為5的德布魯因序列每5個(gè)二進(jìn)制位都轉(zhuǎn)換成撲克牌的編碼示血，如下：

所以32張牌的初始順序如下：

梅花8，梅花A救拉，梅花2难审，梅花4，黑桃A亿絮，方片2告喊，梅花5，黑桃3派昧，方片6黔姜，黑桃4，紅桃A蒂萎，方片3秆吵，梅花7，黑桃7五慈，紅桃7纳寂，紅桃6，紅桃4泻拦，紅桃8毙芜，方片A，梅花3争拐，梅花6腋粥，黑桃5，紅桃3架曹，方片7隘冲，黑桃6，紅桃5绑雄，紅桃2展辞，方片5，黑桃2绳慎，方片4纵竖，黑桃8漠烧，方片8。

上面這32張牌的初始順序魔術(shù)師是要記在心里的靡砌。

將所有的排列組合列舉出來(lái)已脓，如上圖。當(dāng)魔術(shù)師讓黑色或者紅色的牌的人出列的時(shí)候通殃，就能確定到具體是哪一種組合了度液。于是也就可以直接說(shuō)出每個(gè)人手上拿的是什么牌了。

這個(gè)魔術(shù)中選取的德布魯因序列也非常特殊画舌，是可以通過(guò)一部分的遞推得到堕担。

這個(gè)特殊的序列，任意取出其中一個(gè)窗口曲聂，即5個(gè)連續(xù)的二進(jìn)制霹购，5個(gè)二進(jìn)制的第一位和第三位，或者倒數(shù)第三位和倒數(shù)第五位相加朋腋，加法遵循二進(jìn)制規(guī)則齐疙，即可得到這個(gè)窗口緊接著的下一位。

如上圖的例子旭咽，假設(shè)當(dāng)前窗口里面的五位是 00001贞奋，左數(shù)第一位加上第三位，或者右數(shù)第三位加上第五位穷绵，得到的是0轿塔，那么這個(gè)窗口緊接著的后一位就是0 ，即 000010 仲墨。再舉一個(gè)例子勾缭，當(dāng)前窗口里面是 11000 ，左數(shù)第一位加上第三位為1宗收，所以緊接著的下一位是1漫拭，即 110001 。

最后一個(gè)關(guān)鍵的地方就在切牌的手法上混稽。由于德布魯因序列是一個(gè)循環(huán)的序列，為了維護(hù)這個(gè)序列审胚，切牌只能把上面的牌切到下面去匈勋，不能亂切。只有上面的牌切到下面膳叨，因?yàn)檠h(huán)的原因洽洁，這樣才不能影響德布魯因序列。

魔術(shù)能成功實(shí)施菲嘴，必要條件就是要先記住32張牌的初始位置饿自。然后切牌的時(shí)候暗示觀眾牌是洗過(guò)的汰翠。最后根據(jù)觀眾拿了黑色花色的牌(梅花和黑桃)舉手，快速定位到5個(gè)連續(xù)的牌位于32張牌的哪個(gè)窗口昭雌，然后說(shuō)出這5張牌的花色和點(diǎn)數(shù)复唤。

三. 德布魯因序列的定義和性質(zhì)

1. 定義

德布魯因序列(De Bruijn sequence)，記為B(k, n)烛卧，是 k 元素構(gòu)成的循環(huán)序列佛纫。所有長(zhǎng)度為 n 的 k 元素構(gòu)成序列都在它的子序列（以環(huán)狀形式）中，出現(xiàn)并且僅出現(xiàn)一次总放。

例如呈宇，序列 00010111 屬于B(2,3)。 00010111 的所有長(zhǎng)度為3的子序列為000,001,010,101,011,111,110,100局雄，正好構(gòu)成了 {0,1} ³ 的所有組合甥啄。

2. 長(zhǎng)度

德布魯因序列的長(zhǎng)度為 kⁿ。

注意到炬搭，所有長(zhǎng)度為 n 的 k 元素構(gòu)成的序列總共有 kⁿ型豁。而對(duì)于德布魯因序列中的每個(gè)元素，恰好構(gòu)成一個(gè)以此元素開(kāi)頭長(zhǎng)度為 n 的子序列尚蝌。所以德布魯因序列的長(zhǎng)度為 kⁿ 迎变。

3. 數(shù)量

德布魯因序列的數(shù)量 B(k,n) 的數(shù)量為 (k!) ^ (k^n-1) / kⁿ 。

我們用數(shù)學(xué)歸納法證明一下上述的結(jié)論飘言。

我們先假設(shè)德布魯因序列是二進(jìn)制的衣形，即 k = 2。想計(jì)算序列數(shù)量總共有多少個(gè)姿鸿，其實(shí)可以看這個(gè)序列每個(gè)子序列轉(zhuǎn)換成10進(jìn)制的數(shù)最大的是多少谆吴，那么就是它的數(shù)量。

由于每相鄰的子序列是相互依賴的關(guān)系苛预，比如下一個(gè)子序列是前一個(gè)子序列左移一位再加上 0 或者 1句狼，產(chǎn)生下一個(gè)子序列。當(dāng)然最后要 mod 2ⁿ热某，這樣控制每個(gè)子序列的長(zhǎng)度都在 n 位之間腻菇。于是我們可以得到這樣的一個(gè)式子：

s[i+1]=(2s[i]+(0|1))mod(2^n)

利用錯(cuò)位相減法，我們可以得到通項(xiàng)公式：

|B(2,n)|= 2 ^ 2^(n?1) / 2ⁿ

最后利用數(shù)學(xué)歸納法我們可以得到一個(gè)通用的式子昔馋，即：

|B(k,n)| 的數(shù)量為 (k!) ^ (k^n-1) / kⁿ

最最常用的德布魯因序列就是 k = 2 筹吐。計(jì)算一下 |B(2,n)| 的數(shù)量，如下：

4. 生成方式

由于德布魯因序列并不唯一秘遏，所以用代碼可以生成其中的任意一種丘薛。

def de_bruijn(k, n):
    """
    de Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    try:
        # let's see if k can be cast to an integer;
        # if so, make our alphabet a list
        _ = int(k)
        alphabet = list(map(str, range(k)))

    except (ValueError, TypeError):
        alphabet = k
        k = len(k)

    a = [0] * k * n
    sequence = []

    def db(t, p):
        if t > n:
            if n % p == 0:
                sequence.extend(a[1:p + 1])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return "".join(alphabet[i] for i in sequence)

二進(jìn)制的德布魯因序列用的比較多，接下來(lái)看看它生成的序列邦危。

B(2洋侨，1) 就唯一一種情況舍扰。

i  01  s[i]
0  0    0
1   1   1

B(2，2) 由4位二進(jìn)制位組成希坚。也是唯一一種情況边苹。

i  0011|0  s[i]
0  00 . . . 0
1   01      1
2  . 11 . . 3
3     1|0   2

B(2，3) 由8位二進(jìn)制位組成吏够。有2種德布魯因序列勾给。

i  00010111|00 s[i]    i  00011101|00 s[i]
0  000 . . . .  0      0  000 . . . .  0
1   001         1      1   001         1
2  . 010 . . .  2      2  . 011 . . .  3
3     101       5      3     111       7
4  . . 011 . .  3      4  . . 110 . .  6
5       111     7      5       101     5
6  . . . 11|0   6      6  . . . 01|0   2
7         1|00  4      7         1|00  4

B(2，4) 由16位二進(jìn)制位組成锅知。對(duì)應(yīng)有16種德布魯因序列播急。

0x09af  0000100110101111
0x09eb  0000100111101011
0x0a6f  0000101001101111
0x0a7b  0000101001111011
0x0b3d  0000101100111101
0x0b4f  0000101101001111
0x0bcd  0000101111001101
0x0bd3  0000101111010011
0x0cbd  0000110010111101
0x0d2f  0000110100101111
0x0d79  0000110101111001
0x0de5  0000110111100101
0x0f2d  0000111100101101
0x0f4b  0000111101001011
0x0f59  0000111101011001
0x0f65  0000111101100101

取出其中的 0x0d2f ：

 i  0000110100101111|000 s[i]
 0  0000 . . . . . . . .  0
 1   0001                 1
 2  . 0011 . . . . . . .  3
 3     0110               6
 4  . . 1101 . . . . . . 13
 5       1010            10
 6  . . . 0100 . . . . .  4
 7         1001           9
 8  . . . . 0010 . . . .  2
 9           0101         5
10  . . . . . 1011 . . . 11
11             0111       7
12  . . . . . . 1111 . . 15
13               111|0   14
14  . . . . . . . 11|00  12
15                 1|000  8

B(2，5) 由32位二進(jìn)制位組成售睹。對(duì)應(yīng)有2048種德布魯因序列桩警。由于太多了，這里沒(méi)法一一列舉出來(lái)昌妹，任意挑選一個(gè)出來(lái)舉例：

 i  00000111011010111110011000101001|0000 s[i]
 0  00000 . . . . . . . . . . . . . . . .  0
 1   00001                                 1
 2  . 00011 . . . . . . . . . . . . . . .  3
 3     00111                               7
 4  . . 01110 . . . . . . . . . . . . . . 14
 5       11101                            29
 6  . . . 11011 . . . . . . . . . . . . . 27
 7         10110                          22
 8  . . . . 01101 . . . . . . . . . . . . 13
 9           11010                        26
10  . . . . . 10101 . . . . . . . . . . . 21
11             01011                      11
12  . . . . . . 10111 . . . . . . . . . . 23
13               01111                    15
14  . . . . . . . 11111 . . . . . . . . . 31
15                 11110                  30
16  . . . . . . . . 11100 . . . . . . . . 28
17                   11001                25
18  . . . . . . . . . 10011 . . . . . . . 19
19                     00110               6
20  . . . . . . . . . . 01100 . . . . . . 12
21                       11000            24
22  . . . . . . . . . . . 10001 . . . . . 17
23                         00010           2
24  . . . . . . . . . . . . 00101 . . . .  5
25                           01010        10
26  . . . . . . . . . . . . . 10100 . . . 20
27                             01001       9
28  . . . . . . . . . . . . . . 1001|0. . 18
29                               001|00    4
30  . . . . . . . . . . . . . . . 01|000   8
31                                 1|0000 16

B(2捶枢，6) 由64位二進(jìn)制位組成。對(duì)應(yīng)有67,108,864種德布魯因序列飞崖。由于太多了烂叔，這里沒(méi)法一一列舉出來(lái)，任意挑選一個(gè)出來(lái)舉例：

 i  0000001000101111110111010110001111001100100101010011100001101101|00000 s[i]
 0  000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  0
 1   000001                                                                 1
 2  . 000010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  2
 3     000100                                                               4
 4  . . 001000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  8
 5       010001                                                            17
 6  . . . 100010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
 7         000101                                                           5
 8  . . . . 001011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
 9           010111                                                        23
10  . . . . . 101111 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
11             011111                                                      31
12  . . . . . . 111111 . . . . . . . . . . . . . . . . . . . . . . . . . . 63
13               111110                                                    62
14  . . . . . . . 111101 . . . . . . . . . . . . . . . . . . . . . . . . . 61
15                 111011                                                  59
16  . . . . . . . . 110111 . . . . . . . . . . . . . . . . . . . . . . . . 55
17                   101110                                                46
18  . . . . . . . . . 011101 . . . . . . . . . . . . . . . . . . . . . . . 29
19                     111010                                              58
20  . . . . . . . . . . 110101 . . . . . . . . . . . . . . . . . . . . . . 53
21                       101011                                            43
22  . . . . . . . . . . . 010110 . . . . . . . . . . . . . . . . . . . . . 22
23                         101100                                          44
24  . . . . . . . . . . . . 011000 . . . . . . . . . . . . . . . . . . . . 24
25                           110001                                        49
26  . . . . . . . . . . . . . 100011 . . . . . . . . . . . . . . . . . . . 35
27                             000111                                       7
28  . . . . . . . . . . . . . . 001111 . . . . . . . . . . . . . . . . . . 15
29                               011110                                    30
30  . . . . . . . . . . . . . . . 111100 . . . . . . . . . . . . . . . . . 60
31                                 111001                                  57
32  . . . . . . . . . . . . . . . . 110011 . . . . . . . . . . . . . . . . 51
33                                   100110                                38
34  . . . . . . . . . . . . . . . . . 001100 . . . . . . . . . . . . . . . 12
35                                     011001                              25
36  . . . . . . . . . . . . . . . . . . 110010 . . . . . . . . . . . . . . 50
37                                       100100                            36
38  . . . . . . . . . . . . . . . . . . . 001001 . . . . . . . . . . . . .  9
39                                         010010                          18
40  . . . . . . . . . . . . . . . . . . . . 100101 . . . . . . . . . . . . 37
41                                           001010                        10
42  . . . . . . . . . . . . . . . . . . . . . 010101 . . . . . . . . . . . 21
43                                             101010                      42
44  . . . . . . . . . . . . . . . . . . . . . . 010100 . . . . . . . . . . 20
45                                               101001                    41
46  . . . . . . . . . . . . . . . . . . . . . . . 010011 . . . . . . . . . 19
47                                                 100111                  39
48  . . . . . . . . . . . . . . . . . . . . . . . . 001110 . . . . . . . . 14
49                                                   011100                28
50  . . . . . . . . . . . . . . . . . . . . . . . . . 111000 . . . . . . . 56
51                                                     110000              48
52  . . . . . . . . . . . . . . . . . . . . . . . . . . 100001 . . . . . . 33
53                                                       000011             3
54  . . . . . . . . . . . . . . . . . . . . . . . . . . . 000110 . . . . .  6
55                                                         001101          13
56  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 011011 . . . . 27
57                                                           110110        54
58  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101101 . . . 45
59                                                             01101|0     26
60  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101|00  . 52
61                                                               101|000   40
62  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 01|0000  16
63                                                                 1|00000 32

B(2固歪，5) 和 B(2蒜鸡，6) 在實(shí)際生產(chǎn)中都有廣泛的用途。

四. 在圖論中的應(yīng)用：歐拉回路 和 漢密爾頓回路

在圖論中牢裳，有這樣一種無(wú)向連通圖逢防，有一條通路，能經(jīng)過(guò)這個(gè)圖的每條邊一次并且僅一次的路徑被稱為歐拉回路蒲讯。這個(gè)問(wèn)題也是最常見(jiàn)的哥尼斯堡七橋問(wèn)題：能不能一次走遍所有的7座橋忘朝，并且每座橋只經(jīng)過(guò)一次。其實(shí)就是判斷是否存在歐拉回路判帮。

與歐拉問(wèn)題非常類似的是漢密爾頓回路的問(wèn)題局嘁。該問(wèn)題起源于英國(guó)數(shù)學(xué)家威廉漢密爾頓（Willian Hamilton）于1857年發(fā)明的一個(gè)關(guān)于正十二面體的數(shù)學(xué)游戲：正十二面體的每個(gè)棱角上標(biāo)有一個(gè)當(dāng)時(shí)非常有名的城市，游戲的目的是“環(huán)繞地球”旅行脊另，也就是說(shuō)导狡，尋找一個(gè)環(huán)游路線使得經(jīng)過(guò)每個(gè)城市一次且恰好一次。

如果把正十二面體的20個(gè)棱角看成圖中的頂點(diǎn)偎痛，將正十二面體畫成如上圖的平面圖，那么問(wèn)題就轉(zhuǎn)換成：能否在圖中找到一條回路独郎，經(jīng)過(guò)每個(gè)頂點(diǎn)一次有且僅有一次踩麦。上圖就給出了一條符合要求的回路枚赡。

歐拉回路的問(wèn)題一般求解方法有兩種，DFS 和 Fleury 佛羅萊算法谓谦。但是漢密爾頓圖沒(méi)有一個(gè)有效的判斷方法贫橙，它只是給出了一些充分條件或者必要條件，并非充要條件反粥。

德布魯因序列 和 歐拉回路卢肃，漢密爾頓回路 有緊密的聯(lián)系。

若由 k 種符號(hào)組成的所有長(zhǎng)度為 n 的序列列表為有向圖的頂點(diǎn)才顿，則圖中有 kⁿ 個(gè)頂點(diǎn)莫湘， 若頂點(diǎn) m 去掉第一個(gè)符號(hào)并在尾端添加一個(gè)符號(hào)便可得頂點(diǎn) n ，則有一個(gè)有向邊由 m 指向 n郑气，此時(shí)圖就是 德布魯因圖幅垮。如下圖，k = 2尾组， n = 3 的圖中忙芒，頂點(diǎn) 010 有兩條對(duì)外的邊，分別指向 101 和 100 讳侨。

我們以 B(2,3) 舉例呵萨。

在德布魯因圖中的漢密爾頓回路 即為 德布魯因序列。如下圖跨跨，左圖中紅色的漢密爾頓回路 潮峦，圖中對(duì)應(yīng)的德布魯因序列是 00010111，且這個(gè)漢密爾頓回路等價(jià)于窗口長(zhǎng)度為 2 的德布魯因序列中的一個(gè)歐拉回路歹叮，見(jiàn)下右圖中標(biāo)記的歐拉回路對(duì)應(yīng)的順序編號(hào)跑杭。

所以，窗口為 n 的德布魯因圖中的漢密爾頓回路可以等價(jià)轉(zhuǎn)換為窗口為 n - 1 的德布魯因圖中的歐拉回路咆耿。

當(dāng)然德谅，一個(gè)德布魯因圖中的漢密爾頓回路并不一定唯一。如上左圖萨螺，同樣是 k = 2窄做，n = 3 的德布魯因圖，還可以找到一條漢密爾頓回路慰技。對(duì)應(yīng)的歐拉回路的順序也對(duì)應(yīng)的發(fā)生了變化椭盏，見(jiàn)右圖。

這也說(shuō)明了吻商，k = 2掏颊，n = 3 的時(shí)候，德布魯因序列存在多個(gè)，并不唯一乌叶。

再進(jìn)一步盆偿，既然說(shuō)高階的德布魯因圖的漢密爾頓回路可以轉(zhuǎn)換成低級(jí)的歐拉回路。那么我們就用 k = 2准浴，n = 3 的德布魯因圖的歐拉回路去構(gòu)造高階的漢密爾頓圖事扭，可以么？答案是當(dāng)然可以乐横。

如上圖求橄，用 k = 2，n = 3 的德布魯因圖中的一條歐拉回路葡公，我們構(gòu)造出了 k = 2罐农，n = 4 的德布魯因序列。

同理匾南，當(dāng) k = 3啃匿，n = 2 的時(shí)候，德布魯因圖中依舊可以找到一條漢密爾頓回路蛆楞，與之對(duì)應(yīng)的 n = 1 的窗口的歐拉回路也存在溯乒。如下圖。

五. 位掃描器

德布魯因序列用的比較廣泛的一點(diǎn)應(yīng)用就是 位掃描器豹爹。在 Google S2 中也是這個(gè)作用裆悄。

先來(lái)看一個(gè)比較常見(jiàn)的問(wèn)題。

有一個(gè)非0的正數(shù)臂聋，它用二進(jìn)制表示的光稼。問(wèn)如何快速的找到它二進(jìn)制位中最后的1所在的位置。例如孩等，0101010010010100艾君，它的最后一個(gè)1所在的位置是從右往左數(shù)的第2位(從0開(kāi)始數(shù))。

這道題有幾種做法肄方，從粗糙到最優(yōu)依次分析分析冰垄。

最直接的想法是能把這個(gè)二進(jìn)制數(shù)轉(zhuǎn)換成只有一位為1的情況。如果上面這個(gè)問(wèn)題轉(zhuǎn)換成只有一個(gè)位上為1的情況权她，那很好解決虹茶。

那么問(wèn)題轉(zhuǎn)化為如何把末尾的1分離出來(lái)∮缫可以直接用位運(yùn)算進(jìn)行分離蝴罪。

x &= (~x+1)

// 或者

x &= -x

通過(guò)上面的操作可以把最后一位的1分離出來(lái)。

分離出來(lái)以后的解法就很多種了步清。

舉個(gè)例子：

假設(shè)某個(gè)64位的二進(jìn)制數(shù)如下：

3932700031202623488

11011010010011110000011101011110010000000000000000000000000000

經(jīng)過(guò) x & -x 操作以后要门，就能把末尾的1篩出來(lái)。原理是因?yàn)樨?fù)數(shù)的存儲(chǔ)方式是以原碼的補(bǔ)碼，即符號(hào)位不變暂衡，每位取反再加1 询微。末尾連續(xù)的0取反以后都為1崖瞭，所以加1以后會(huì)一直往前進(jìn)位狂巢，直到原來(lái)為1的那一位，因?yàn)樗》匆院筮@一位變成0了书聚，就不會(huì)往前進(jìn)位了唧领。

1. 循環(huán)

可以用 for 循環(huán)，不斷的右移目標(biāo)數(shù)雌续。找到末尾的1所在的位置斩个。

for ( index = -1; x > 0; x >>= 1, ++index ) ;

這種方式簡(jiǎn)單粗暴，時(shí)間復(fù)雜度為 O(n) 驯杜。

2. 二分搜索

把上述循環(huán)改成二分受啥，時(shí)間復(fù)雜度就變成了 O(lgn)

3. 構(gòu)造特殊數(shù)字進(jìn)行位運(yùn)算

這種方式看上去比較巧，但是實(shí)際還是利用了二分搜索的思想鸽心。

index = 0;
index += (!!(x & 0xAAAAAAAA)) * 1;
index += (!!(x & 0xCCCCCCCC)) * 2;
index += (!!(x & 0xF0F0F0F0)) * 4;
index += (!!(x & 0xFF00FF00)) * 8;
index += (!!(x & 0xFFFF0000)) * 16;

這種方式的時(shí)間復(fù)雜度也是 O(lgn) 滚局，但是實(shí)際計(jì)算會(huì)比二分搜索快很多，因?yàn)樗恍枰容^運(yùn)算顽频，都位運(yùn)算即可完成藤肢。

5. 哈希

這種方式就比之前的方式都要高效了。

假設(shè) x 有32位糯景，所以末尾的1出現(xiàn)的可能只有32種嘁圈。如果 x 為64，那就是64種可能蟀淮，每一位上都有可能最住。通過(guò)哈希的方式 O(1) 的時(shí)間復(fù)雜度查詢出結(jié)果。

6. 德布魯因序列

這種方式的原理也是哈希怠惶，但是這種方式比單純的哈希要快涨缚，因?yàn)樗苊獾娜∮嗟挠?jì)算。

如果 x 為32位甚疟，那么哈希函數(shù)可以構(gòu)造成下面這樣：

(x * 0x077CB531) >> 27 

0x077CB531 是32位的德布魯因序列之一仗岖。

構(gòu)造這樣一個(gè)哈希函數(shù)有2點(diǎn)優(yōu)點(diǎn)：

1. 由于這個(gè)二進(jìn)制數(shù)是我們篩選出來(lái)的特殊的二進(jìn)制數(shù)，原來(lái)的二進(jìn)制數(shù)的末尾的1被我們篩選出來(lái)了览妖。它本身其實(shí)就是二的次方轧拄，所以任何一個(gè)數(shù)字乘以這個(gè)特殊的二進(jìn)制的數(shù)，都相當(dāng)于左移運(yùn)算讽膏。左移的位數(shù)就是原二進(jìn)制數(shù)末尾1所在的位子檩电。
2. 德布魯因序列相當(dāng)于是全排列，枚舉了所有的情況。所以它的兩兩子序列之間肯定不相同俐末，這就是完美的哈希料按。

最后又移動(dòng)27位是為了保證能取出開(kāi)頭的5位。

在 Go 的原生代碼包中卓箫，有一個(gè) nat.go 文件载矿，在這個(gè)文件里面有這樣一段代碼：

const deBruijn32 = 0x077CB531

var deBruijn32Lookup = []byte{
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
}

const deBruijn64 = 0x03f79d71b4ca8b09

var deBruijn64Lookup = []byte{
    0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
    62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
    63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
    54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
}

在這個(gè)文件中，同樣有一個(gè)函數(shù)在解決上述的問(wèn)題烹卒，只不過(guò)它換了一個(gè)角度闷盔。

求一個(gè)二進(jìn)制數(shù)的末尾1所在的位置，其實(shí)可以轉(zhuǎn)化為求這個(gè)二進(jìn)制數(shù)末尾連續(xù)0有多少個(gè)的問(wèn)題旅急。

這個(gè)經(jīng)典的問(wèn)題在圖靈獎(jiǎng)獲得者 Donald Ervin Knuth 的著作 《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》的第四卷逢勾，section 7.3.1 上有，感興趣的同學(xué)可以看看這個(gè)問(wèn)題藐吮。

// trailingZeroBits returns the number of consecutive zero bits on the right
// side of the given Word.
// See Knuth, volume 4, section 7.3.1
func trailingZeroBits(x Word) int {
    // x & -x leaves only the right-most bit set in the word. Let k be the
    // index of that bit. Since only a single bit is set, the value is two
    // to the power of k. Multiplying by a power of two is equivalent to
    // left shifting, in this case by k bits.  The de Bruijn constant is
    // such that all six bit, consecutive substrings are distinct.
    // Therefore, if we have a left shifted version of this constant we can
    // find by how many bits it was shifted by looking at which six bit
    // substring ended up at the top of the word.
    switch _W {
    case 32:
        return int(deBruijn32Lookup[((x&-x)*deBruijn32)>>27])
    case 64:
        return int(deBruijn64Lookup[((x&-x)*(deBruijn64&_M))>>58])
    default:
        panic("Unknown word size")
    }

    return 0
}

這里還需要解釋一下 deBruijn32Lookup 和 deBruijn64Lookup 數(shù)組里面初始裝入的數(shù)字到底代表了什么意思溺拱。

deBruijn32 和 deBruijn64 分別是德布魯因序列。兩兩之間的子序列都是不相同的谣辞，并且所有的子序列構(gòu)成了一個(gè)全排列迫摔。

const deBruijn32 = 0x077CB531
// 0000 0111 0111 1100 1011 0101 0011 0001

const deBruijn64 = 0x03f79d71b4ca8b09
// 0000 0011 1111 0111 1001 1101 0111 0001 1011 0100 1100 1010 1000 1011 0000 1001

我們用下面的哈希函數(shù)構(gòu)造一個(gè)“完美”的哈希函數(shù)。

h(x) = (x * deBruijn) >> (n - lg n)

n 是二進(jìn)制數(shù)的位數(shù)潦闲。于是也就可以理解 ((x&-x)deBruijn32)>>27 和 ((x&-x)(deBruijn64&_M))>>58 是什么意思了攒菠，這就是在算對(duì)應(yīng)的哈希值。

那么數(shù)組里面存的值就是我們最終的結(jié)果了歉闰，即末尾1所在的位置或者末尾連續(xù)有多少個(gè)0 揭斧。

其實(shí)數(shù)組里面存的數(shù)字是這樣算出來(lái)的：

void setup( void )
{   
    int i;
    for(i=0; i<32; i++)
        index32[ (debruijn32 << i) >> 27 ] = i;
}

即把算出來(lái)的哈希值作為下標(biāo)演侯，對(duì)應(yīng)下標(biāo)存儲(chǔ)的值是左移的位數(shù)。這個(gè)左移的位數(shù)就是我們要的結(jié)果。所以先算哈希值汞斧，然后通過(guò)數(shù)組取出哈希值里面存儲(chǔ)的值即為我們的結(jié)果了阅嘶。

舉例蕾殴，假設(shè)原二進(jìn)制數(shù)是64位的

0011011011101100110011001001001111110011000000000000000000000000

x & -x 以后的結(jié)果

1000000000000000000000000

經(jīng)過(guò)這一步以后就把二進(jìn)制的末尾1截取出來(lái)了普办。剩下的問(wèn)題就是要找這個(gè)1從右往左數(shù)在第幾位了。

用64位的德布魯因序列來(lái)求：

0000001111110111100111010111000110110100110010101000101100001001

用上面 x & -x 算出來(lái)的結(jié)果乘以這個(gè)64位的德布魯因序列舱痘，就相當(dāng)于左移幾位变骡，直接看0的個(gè)數(shù)，我們可以看出來(lái)是左移24位：

0111000110110100110010101000101100001001000000000000000000000000

最后取出這個(gè)數(shù)的前6位就是我們要的結(jié)果了芭逝。lg 64 = 6塌碌，所以取出前6位，011100 旬盯。

// findLSBSetNonZero64 returns the index (between 0 and 63) of the least
// significant set bit. Passing zero to this function has undefined behavior.
//
// This code comes from trailingZeroBits in https://golang.org/src/math/big/nat.go
// which references (Knuth, volume 4, section 7.3.1).
func findLSBSetNonZero64(bits uint64) int {
    return int(deBruijn64Lookup[((bits&-bits)*(deBruijn64&digitMask))>>58])
}

上述程序和之前的實(shí)現(xiàn)方式完全一致台妆，只不過(guò)這里函數(shù)名的意義代表查找末尾1的位置翎猛，和查找末尾有多少個(gè)0，完全一致接剩！

上述代碼也是 Google S2 中的源碼切厘，它也是直接利用德布魯因序列來(lái)查找末尾1所在的位。

總結(jié)一下懊缺，數(shù)組的下標(biāo)和我們構(gòu)造的哈希函數(shù)值相對(duì)應(yīng)疫稿，哈希函數(shù)的值其實(shí)就是對(duì)應(yīng)德布魯因序列的前幾位。而末尾1所在的位置被我們處理成了一個(gè)特殊的二進(jìn)制數(shù)了桐汤，這個(gè)數(shù)的1所在的位置就是原二進(jìn)制數(shù)末尾1所在的位置而克。這個(gè)特殊的二進(jìn)制數(shù)末尾1后面全是0，所以任何數(shù)乘以它以后都相當(dāng)于左移末尾0的個(gè)數(shù)怔毛。于是末尾1所在的位置就被轉(zhuǎn)換成德布魯因序列左移多少位的問(wèn)題了。德布魯因序列左移多少位腾降，取出前幾位拣度，生成的數(shù)字就是哈希函數(shù)的值，它又和數(shù)組的下標(biāo)關(guān)聯(lián)起來(lái)了螃壤。于是最后查找數(shù)組里面對(duì)應(yīng)哈希值位里面存的值就是我們要的結(jié)果了抗果。

六. 工業(yè)應(yīng)用

De Bruijn 序列的奇妙不僅體現(xiàn)在魔術(shù)上。我們還可以使用它為機(jī)器人做路標(biāo)定位：將兩種不同顏色的小方塊排成一條長(zhǎng)線擺在機(jī)器人行進(jìn)的路上奸晴，機(jī)器人只要識(shí)別出自己前后的幾個(gè)方塊是什么顏色冤馏，既不需要GPS，也不需要高精度探測(cè)儀寄啼，就可以知道自己走了多少米逮光。

研究人員利用 De Bruijn 序列設(shè)計(jì)了每次可以產(chǎn)生一個(gè)用于加密的不同隨機(jī)數(shù)字的簡(jiǎn)單電子元件“反饋移位寄存器”，上一個(gè)隨機(jī)數(shù)字和下一個(gè)隨機(jī)數(shù)字之間只改變一個(gè)數(shù)位和移位一下就可以墩划，電路構(gòu)造非常簡(jiǎn)單涕刚。

在測(cè)量工程上，德布魯因序列還可以用在基于光柵投影模式的三維形貌快速測(cè)量系統(tǒng)研究中乙帮。

在基因工程中杜漠，德布魯因序列可以用在基因組重復(fù)區(qū)域組裝上。

在醫(yī)學(xué)研究中察净，德布魯因序列通常用于神經(jīng)科學(xué)和心理實(shí)驗(yàn)以檢測(cè)刺激序列對(duì)神經(jīng)系統(tǒng)的影響驾茴，其可專門用于功能磁共振成像。

在人工智能算法中氢卡，神經(jīng)網(wǎng)絡(luò)時(shí)間序列預(yù)測(cè)也有德布魯因序列的身影锈至。

Reference：

Wiki De Bruijn sequence
Wolfram Mathworld de Bruijn Sequence
http://chessprogramming.wikispaces.com/De+Bruijn+sequence
The On-Line Encyclopedia of Integer Sequences
De Bruijn cycle generator
On line Sequence Generator
de Bruijn cycles for neural decoding
De Bruijn sequence
《Using de Bruijn Sequences to Index a 1 in a Computer Word》

空間搜索系列文章：

空間搜索系列文章：

如何理解 n 維空間和 n 維時(shí)空
高效的多維空間點(diǎn)索引算法 — Geohash 和 Google S2
Google S2 中的 CellID 是如何生成的 ？
Google S2 中的四叉樹(shù)求 LCA 最近公共祖先
神奇的德布魯因序列
四叉樹(shù)上如何求希爾伯特曲線的鄰居 异吻？

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Source: https://halfrost.com/go_s2_De_Bruijn/