### Discover more content...

Enter some keywords in the search box above, we will do our best to offer you relevant results.

### We're sorry!

We couldn't find any results for your search. Please try again with another keywords.

## 三. 德布鲁因序列的定义和性质

### 3. 数量

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

``````

|B(2,n)|= 2 ^ 2^(n−1)^ / 2^n^

|B(k,n)| 的数量为 (k!) ^ (k^n-1^) / k^n^

### 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)

``````

B(2，1) 就唯一一种情况。

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

``````

B(2，2) 由4位二进制位组成。也是唯一一种情况。

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

``````

B(2，3) 由8位二进制位组成。有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位二进制位组成。对应有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

``````

``````
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位二进制位组成。对应有2048种德布鲁因序列。由于太多了，这里没法一一列举出来，任意挑选一个出来举例：

``````
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位二进制位组成。对应有67,108,864种德布鲁因序列。由于太多了，这里没法一一列举出来，任意挑选一个出来举例：

``````
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) 在实际生产中都有广泛的用途。

## 五. 位扫描器

``````
x &= (~x+1)

// 或者

x &= -x

``````

``````
3932700031202623488

11011010010011110000011101011110010000000000000000000000000000

``````

### 1. 循环

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

``````

### 3. 构造特殊数字进行位运算

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

``````

### 6. 德布鲁因序列

``````
(x * 0x077CB531) >> 27

``````

0x077CB531 是32位的德布鲁因序列之一。

1. 由于这个二进制数是我们筛选出来的特殊的二进制数，原来的二进制数的末尾的1被我们筛选出来了。它本身其实就是二的次方，所以任何一个数字乘以这个特殊的二进制的数，都相当于左移运算。左移的位数就是原二进制数末尾1所在的位子。
2. 德布鲁因序列相当于是全排列，枚举了所有的情况。所以它的两两子序列之间肯定不相同，这就是完美的哈希。

``````

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,
}

``````

``````
// 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
}

``````

deBruijn32 和 deBruijn64 分别是德布鲁因序列。两两之间的子序列都是不相同的，并且所有的子序列构成了一个全排列。

``````
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

``````

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

``````

n 是二进制数的位数。于是也就可以理解 ((x&-x)deBruijn32)>>27 和 ((x&-x)(deBruijn64&_M))>>58 是什么意思了，这就是在算对应的哈希值。

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

``````

``````
0011011011101100110011001001001111110011000000000000000000000000

``````

x & -x 以后的结果

``````
1000000000000000000000000

``````

``````
0000001111110111100111010111000110110100110010101000101100001001

``````

``````
0111000110110100110010101000101100001001000000000000000000000000

``````

``````
// 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 {
}

``````

## 六. 工业应用

De Bruijn 序列的奇妙不仅体现在魔术上。我们还可以使用它为机器人做路标定位：将两种不同颜色的小方块排成一条长线摆在机器人行进的路上，机器人只要识别出自己前后的几个方块是什么颜色，既不需要GPS，也不需要高精度探测仪，就可以知道自己走了多少米。

Reference：

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Previous Post

Next Post