以前上課的時候老師有提過這個問題，這些是當時的筆記，我覺得最後
的解法蠻有趣的，跟大家分享。
假定有一個非零正數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