• 寫在前面
• 標記left-most 1與right-most 1
• 確定位置
• 德布魯因序列（De Bruijn sequence）
• 德布魯因序列的使用
• 德布魯因序列的生成與索引表的構建
• 參考

博客：博客園 | CSDN | blog

寫在前面

在數值計算中，為了控制精度以及避免越界，需要嚴格控制數值的范圍，有時需要知道二進制表示中"left-most 1"或"right-most 1”的位置，這篇文章就來介紹一下通過德布魯因序列（De Bruijn sequence）來快速定位的方法，

標記left-most 1與right-most 1

對于一個二進制數\(v\)，如何僅保留最低位或最高位的1?

最低位的1，即right-most 1，其特點是這一位右側均為0，可通過v & -v或者v & ((~v)+1)來標記最低位的1，

比如0101 1010，取反后為1010 0101，再加1為1010 0110，與后為0000 0010，

最高位的1，即left-most 1，其特點是這一位左側均為0，可通過下面來標記最高位的1，

uint32_t keepHighestBit( uint32_t n )
{
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

前5行移位將最高位1右側的所有位均置為1，n-(n >> 1)再將他們清0，

至此，我們已經得到了一個二進制的“one hot”表示，只有1位為1，它標記了最高位或最低位1的位置，

確定位置

假設，得到的“one hot”表示為0000 0100 0000 0000，如何確定1在哪一位呢？

比較直接的想法是通過移位計數，不斷右移，并計數，直到最低位為1，

有沒有更好的方法？

令得到的“one hot”表示為h，對于uint32，h只有32種，我們希望找到的這32種one hot表示與\(0\sim 31\)的映射關系，即\(f(h) \rightarrow 0\sim 31\)，

• 查表：以h對應的uint32數為下標，構建陣列，通過查表方式得到，但h最大為\(2^{31}\)，直接構建陣列不現實
• 哈希：再增加一層映射，\(f(g(h)) \rightarrow 0\sim 31\)，即找到一個hash函式\(g\)，先將\(h\)映射到\(0 \sim 31\)，再通過查表\(0\sim 31 \rightarrow 0\sim 31\)，但一般哈希會涉及到取余操作，還要考慮不要有碰撞

對這個特殊問題，可以使用 德布魯因序列——可視為一種特殊的哈希，不需要取余，且絕不會發生碰撞，

德布魯因序列（De Bruijn sequence）

先看一個德布魯因序列的例子，令字符集\(A = \{0, 1\}\)，字符有\(k=2\)種，子串長度\(n=2\)，則所有可能的子串有\(\{00, 01, 10, 11\}\)，則回圈序列\(0011\)是一個德布魯因序列，\(0011\)的所有連續子串恰好為\(\{00, 01, 10, 11\}\)，都出現且只出現一次，同樣，回圈序列\(1001\)也是一個德布魯因序列，

可見，德布魯因序列并不唯一，且是個回圈序列，長度恰好為\(k^n\)，與所有可能子串的數量相同，

wiki上的定義如下，

In combinatorial mathematics, a de Bruijn sequence of order \(n\) on a size-\(k\) alphabet A is a cyclic?sequence in which every possible length-\(n\) string on \(A\) occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by \(B(k, n)\) and has length \(k^n\), which is also the number of distinct strings of length \(n\) on \(A\).

——from wiki De Bruijn sequence

再舉一個\(B(2, 4)\)的例子，序列長度為\(2^4=16\)，如下

其所有回圈子串如下，

每個位置的子串均不相同，所有子串對應著\(0\sim 2^n-1\)范圍的整數，恰好形成了\(2^n\)個位置與\(2^n\)個數的映射，

德布魯因序列的使用

將h與德布魯因序列相乘，相當于左移操作，把某位置的子串移到了最左端，再將該子串右移至最右，即僅保留該子串，可知道該子串是什么，因為序列中每個子串的位置都是唯一的，根據映射關系可知道該子串的位置，相當于知道了h，為此需要建立 子串與位置 對應關系的檢索表，

unsigned int v;   
int r;           
static const int MultiplyDeBruijnBitPosition[32] = 
{
  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
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
// The index of the LSB in v is stored in r

//return the index of the most significant bit set from a 32 bit unsigned integer
uint8_t highestBitIndex( uint32_t b )
{
    static const uint32_t deBruijnMagic = 0x06EB14F9;
    static const uint8_t deBruijnTable[32] = {
         0,  1, 16,  2, 29, 17,  3, 22, 30, 20, 18, 11, 13,  4,  7, 23,
        31, 15, 28, 21, 19, 10, 12,  6, 14, 27,  9,  5, 26,  8, 25, 24,
    };
    return deBruijnTable[(keepHighestBit(b) * deBruijnMagic) >> 27];
}

因為德布魯因序列是回圈序列，而左移操作會自動在最低位填0，所以習慣將全0子串放在序列的最高位，這樣比較方便，不需要特殊處理，

德布魯因序列的生成與索引表的構建

德布魯因序列可以通過構建德布魯因圖得到，圖中每條哈密頓路徑（Hamiltonian path）都對應一個德布魯因序列，

數量共有

具體生成方式和證明可查看De Bruijn sequence和神奇的德布魯因序列，

保存子串與位置映射關系的檢索表可通過如下方式生成，其中debruijn32為德布魯因序列對應的uint32正整數，

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

參考

• De Bruijn sequence
• 神奇的德布魯因序列
• De Bruijn Sequences for Fun and Profit
• Bit mathematics cookbook

標籤：其他

上一篇：2020牛客暑期多校訓練營（第一場）H Minimum-cost Flow

下一篇：差分陣列