以前上課的時候老師有提過這個問題，這些是當時的筆記，我覺得最後

的解法蠻有趣的，跟大家分享。


假定有一個非零正數x以二進位表示，要找出最後一個1的位置，範例：

0100101000100000 <- 第 6 個位置為1，所以輸出 5

（計算0-base的位置，也可以想像成是算最後有幾個0）

在這邊先假設n為機器上表示一個整數所使用的位元數，以n=32來示範。

首先可以把題目簡化，假定x中只有一個bit為1，如果x中有兩個以

上的bit為1，可以利用 x &= (~x+1)來把最後一個1分離。

（x &= -x也可以，如果是二的補數表示法）

當分離出來之後，就有很多種計算法了，這邊就不考慮用組合語言的解法。

第一種是迴圈法

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

不過這種方法會需要n次的計算。

第二種是二分搜尋法，這需要lg n次的比較。

第三種方法是用bitwise parallel的技巧，其實跟二分搜尋法是一樣的道理

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

雖然需要lg n次的計算，但是不像二分搜尋法要做比較運算。

第四種方法是查表，不過x的範圍很大，所以只能分段查表。

第五種方法是利用perfect hash的技巧。

因為x只有32種可能，可以設計一個perfect hash function直接查

出index。

而這個hash function一般會用 x % 37，同時需要開一個大小為37

的table（所以有一些空間會浪費了）。

這方法很好設計，就是找比n稍微大一點的數字來試試看即可。


第六種是利用de Bruijn sequence。

其實這方法跟第五種方法很像，也是設計一個perfect hash function。

只是這方法免除了取餘數的運算，同時也只需要大小為32的table。

hash function是 (x * 0x077CB531) >> 27 其中的0x077CB531就是

de Bruijn sequence。

這方法對於n是二的次方數的機器都可以使用，至於n不是二的次方數

的機器應該不多。

這方法的原理從兩個方面來看，第一個是x本身一定是二的次方數，

所以任何一個數字乘以x，就相當於左移的運算。

而de Bruijn sequence的特殊之處，就是在於此序列中的任意連續

五位元都是相異的。五個位元總共有三十二種可能性，而至少要有

三十二個位元才有可能包含所有三十二種可能性（序列要想成頭尾

相接的）

舉例：00010111就包含了 000, 001, 010, 101, 011, 111, 110, 100

這八種三位元的所有組合。

所以當de Bruijn sequence乘以 x 又右移27個位元的時候，就相

當於是把sequence中的一組五位元子序列取出，這保證不同的x一

定會有不同的子序列，所以是一個很好的hash函數。

（32位元的de Bruijn sequence有很多個，但是這方法要用的時候
必須挑00000開頭的）


關於第六種方法的詳細研究可以參考下面這網址，裡面還有說當一
個數字有兩個bit為1的時候，怎樣可以快速找出來
http://supertech.csail.mit.edu/papers/debruijn.pdf

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51