神秘常量复出!用0x077CB531计算末尾0的个数
解了近日O(1)时间复杂度求幂的二进制数1的位置的疑团.原来这个包含0~2^n-1的所有2进制表示的环叫做De Bruijn 序列.虽然在数据结构中见过,没有记住名字,所以在网上也搜不到,只搜出来另一个利用浮点数求平方根的神秘常量。旧闻一则:神秘的0x5f3759df 不可思议的Quake III源码,巧的是,2篇都是同一个作者写的。

相关的论文
Using de Bruijn Sequences to Index a 1 in a Computer Word
FAST INVERSE SQUARE ROOT