標(biāo)題: De Bruijn序列與計(jì)算二進(jìn)制數(shù)計(jì)算末尾0的個(gè)數(shù) [打印本頁(yè)]
作者: bibi    時(shí)間: 2015-4-18 21:11
標(biāo)題: De Bruijn序列與計(jì)算二進(jìn)制數(shù)計(jì)算末尾0的個(gè)數(shù)
　　下面這個(gè)位運(yùn)算小技巧可以迅速給出一個(gè)數(shù)的二進(jìn)制表達(dá)中末尾有多少個(gè) 0 。比如， 123 456 的二進(jìn)制表達(dá)是 1 11100010 01000000 ，因此這個(gè)程序給出的結(jié)果就是 6 。
unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
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];
    熟悉位運(yùn)算的朋友們可以認(rèn)出， v & -v 的作用就是取出右起連續(xù)的 0 以及首次出現(xiàn)的 1 。當(dāng) v = 123 456 時(shí)， v & -v 就等于 64 ，即二進(jìn)制的 1000000 。怪就怪在，這個(gè) 0x077CB531 是怎么回事？數(shù)組 MultiplyDeBruijnBitPosition 又是什么玩意兒呢？

    這還得從 0x077CB531 本身的一個(gè)性質(zhì)開(kāi)始說(shuō)起。把這個(gè)常數(shù)寫(xiě)成 32 位二進(jìn)制，可以得到
00000111011111001011010100110001
    這個(gè) 01 串有一個(gè)無(wú)比牛 B 的地方：如果把它看作是循環(huán)的，它正好包含了全部 32 種可能的 5 位 01 串，既無(wú)重復(fù)，又無(wú)遺漏！其實(shí)，這樣的 01 串并不稀奇，因?yàn)闃?gòu)造這樣的 01 串完全等價(jià)于尋找一個(gè)有向圖中的 Euler 回路。如下圖，構(gòu)造一個(gè)包含 16 個(gè)頂點(diǎn)的圖，頂點(diǎn)分別命名為 0000, 0001, 0010, …, 1111 。如果某個(gè)點(diǎn)的后 3 位，正好等于另一個(gè)點(diǎn)的前 3 位，就畫(huà)一條從前者出發(fā)指向后者的箭頭。也就是說(shuō)，只要兩個(gè)頂點(diǎn)上的數(shù)滿(mǎn)足 abcd 和 bcde 的關(guān)系（ a 、 b 、 c 、 d 、 e 可能代表相同的數(shù)字），就從 abcd 出發(fā)，連一條到 bcde 的路，這條路就記作 abcde 。注意，有些點(diǎn)之間是可以相互到達(dá)的（比如 1010 和 0101 ），有些點(diǎn)甚至有一條到達(dá)自己的路（比如 0000 ）。
  
    構(gòu)造一個(gè)字符串使其包含所有可能的 5 位 01 子串，其實(shí)就相當(dāng)于沿著箭頭在上圖中游走的過(guò)程。不妨假設(shè)字符串以 0000 開(kāi)頭。如果下一個(gè)數(shù)字是 1 ，那么 00001 這個(gè)子串就被包含了，同時(shí)最新的 4 位數(shù)就變成了 0001 ；但若下一個(gè)數(shù)字還是 0 ，那么 00000 就被包含了進(jìn)來(lái)，最新的 4 個(gè)數(shù)仍然是 0000 。從圖上看，這無(wú)非是一個(gè)從 0000 點(diǎn)出發(fā)走了哪條路的問(wèn)題：你是選擇了沿 00001 這條路走到了 0001 這個(gè)點(diǎn)，還是沿著 00000 這條路走回了 0000 這個(gè)點(diǎn)。同理，每添加一個(gè)數(shù)字，就相當(dāng)于沿著某條路走到了一個(gè)新的點(diǎn)，路上所寫(xiě)的 5 位數(shù)就是剛被考慮到的 5 位數(shù)。我們的目的便是既無(wú)重復(fù)又無(wú)遺漏地遍歷所有的路。顯然圖中的每個(gè)頂點(diǎn)入度和出度都是 2 ，因此這個(gè)圖一定存在 Euler 回路，我們便能輕易構(gòu)造出一個(gè)滿(mǎn)足要求的 01 串了。這樣的 01 串就叫做 De Bruijn 序列。
    De Bruijn 序列在這里究竟有什么用呢？它的用途其實(shí)很簡(jiǎn)單，就是為 32 種不同的情況提供了一個(gè)唯一索引。比方說(shuō)， 1000000 后面有 6 個(gè) 0 ，將 1000000 乘以 0x077CB531 ，就得到
   00000111011111001011010100110001
-> 11011111001011010100110001000000
    相當(dāng)于把 De Bruijn 序列左移了 6 位。再把這個(gè)數(shù)右移 27 位，就相當(dāng)于提取出了這個(gè)數(shù)的頭 5 位：
   11011111001011010100110001000000
->                            11011
    由于 De Bruijn 序列的性質(zhì)，因此當(dāng)輸入數(shù)字的末尾 0 個(gè)數(shù)不同時(shí)，最后得到的這個(gè) 5 位數(shù)也不同。而數(shù)組 MultiplyDeBruijnBitPosition 則相當(dāng)于一個(gè)字典的功能。 11011 轉(zhuǎn)回十進(jìn)制是 27 ，于是我們查一查 MultiplyDeBruijnBitPosition[27] ，程序即返回 6 。
    注意到當(dāng)輸入數(shù)字的末尾 0 個(gè)數(shù)超過(guò) 27 個(gè)時(shí)，程序也是正確的，因?yàn)樽笠茣r(shí)低位正好是用 0 填充的。
    這段神一般的代碼取自Bit Twiddling Hacks  http://graphics.stanford.edu/~seander/bithacks.html ，歡迎大家前去圍觀






歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1