以前上课的时候老师有提过这个问题，这些是当时的笔记，我觉得最後 的解法蛮有趣的，跟大家分享。 假定有一个非零正数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