Skip to content

Latest commit

 

History

History
141 lines (107 loc) · 3.96 KB

4.debruijn.md

File metadata and controls

141 lines (107 loc) · 3.96 KB
Raw

Debruijn算法

用以寻找一个{0, 1}序列中1的位置。
原文：MIT paper
关于如何生成debruijn序列不在此。

I. 步骤描述

1. 找出一个 1

使用 y = x & (-x)，可以找出一个。
假设x = 01101000，则取负数的表示为-x = 10011000

01101000 -> 高位1(11101000) -> 按位取反(10010111) -> +1(10011000)。

则y = 00001000，找出了最右边的1。
要找到剩余的1，只需x - y移除这个已找到的1，重复上面过程。

2. 哈希

现在的问题变成了，在一个序列中只有一个1，找到其位置。
当序列长度n很小时，可以通过一个哈希函数将每个1存在的位置映射到哈希表中h(x)，通过查表快速得出结果。但是需要满足几个条件使其高效：

  • 哈希表要小
  • 哈希函数要容易计算
  • 哈希函数必须没有碰撞，不会出现 h(x) = h(y)

3. de Bruijn 序列

1. 序列描述

该序列是一个长度为n的串，n为2的指数。在其中取lgn长度的字串，将原序列看作循环队列，一次移动一位，依次取字串，所有字串不会重复。
如： n = 8，lgn = 3，已知序列为：00011101。
则长度为3的字串有{000}{001}{011}{111}{110}{101}{010}{100}

2. 哈希函数

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

假设使用的deBruijn序列为：00011101，则计算其哈希表为：

Index Number x h(x) h(x)Decimal
0 20 00000001 000 0
1 21 00000010 001 1
2 22 00000100 011 3
3 23 00001000 111 7
4 24 00010000 110 6
5 25 00100000 101 5
6 26 01000000 010 2
7 27 10000000 100 4

x * deBruijn等同于将deBruijn序列左移x位。
x为输入，即要找1的位置的数。
h(x)为计算出的哈希表下标。
index为计算出的哈希表的值。

Hash table[h(x)] = [...index]
Hash table = [0, 1, 6, 2, 7, 5, 4, 3]

论文作者给出了32位C实现

/* debruijn32 = 0000 0111 0111 1100 1011 0101 0011 0001 */
#define debruijn32 0x077CB531UL

/* table to convert debruijn index to standard index */
int index32[32];

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

/* compute index of rightmost 1 */
int rightmost_index( unsigned long b )
{
    b &= -b;
    b *= debruijn32;
    b >>= 27;
    return index32[b];
}

II. 使用

上述方式用于寻找最右侧的1，下面的使用场景找最左侧的1。(误
见 xtaci/smux 判断申请内存空间大小。
作者生成哈希表时使用的是补全1作为x，在查找时也要做相同操作。

1. 规定序列生成哈希表

定义debruijn序列为: 0x07C4ACDD

0000 0111 1100 0100 1010 1100 1101 1101
Index Number x h(x) h(x)Decimal
0 21-1 00000001 000 0
1 22-1 00000011 010 2
2 23-1 00000111 110 6
3 24-1 00001111 1110 14
... ... ... ... ...
28 229-1 ... 10011 19
29 230-1 ... 111 7
30 231-1 ... 1111 15
31 232-1 ... 11111 31

完整表为：

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

2. 查找

// 设size = 160 = 1010 0000 = A0
func msb(size int) byte {
	v := uint32(size)
	v |= v >> 1
	v |= v >> 2
	v |= v >> 4
	v |= v >> 8
	v |= v >> 16
    // 以上将右侧全部补为1: 1111 1111
	return debruijinPos[(v*0x07C4ACDD)>>27]
}

(FF * 0x07C4ACDD) >> 27
去除溢出位得：BCE83023 >> 1B
得：17
debruijinPos[17] 为 7