Lua快速计算log2

分类:CentOS运维 阅读:49953 次

lua 的源码,惊喜越来越多。比如今天看到了一个快速计算 log2(x) 的方法。代码如下:

想法也很朴素,就是把整数转换成 2^n 的形式,然后求出 n 就可以了。比如 256 是 2^8 ,所以这里数组 log_2[256] = 8,那些转换不成 2^n 的数也就被近似计算了,比如 255,我们知道 256 = 2^8,而 128 = 2^7,所以 128 和 256 之间的数都被近似成 256 了,结果也都是 8。我们可以看到 log_2[128] 到 log_2[255] 都等于 8。

这里误差也就是 1。完全可以忽略了。如果这个数大于 256,那么就让他除以 256,同时结果加 8 就可以了。最后的误差仍然是 1。

其实你也完全可以把这个 log_2 的数组设计的更大一些,这样需要进入 while 循环的条件就要求所求的数更大。作者定在 256 估计是考虑到在实际计算过程中对于大于等于 256 的数求 log2 已经很少用到了。这个 log_2 的数组你还可以设计的更合理一些,比如把 log_2[128] 到 log_2[255] 之间的数不全部设成 8,而是把靠近 128 的地方的数设成 7,把靠近 255 的地方设成 8,不过这样就又陷入到更麻烦的考虑中,比如到底把哪里开始设成 8,哪里设成 7 等等。本来是为了快速计算的一个函数,最后又变麻烦,必然不好。

最后我在网上搜索快速计算 log2 的方法的时候又看到了 Quake III 中的神奇代码。我不得不说,Quake III 真是一个神奇的引擎,里面有大量值得学习的代码,等我阅读完 lua 的源码之后下一步就是阅读它了。先来看看它是怎么进行 log2 计算的:

看到这段代码我真心都快被吓尿了。首先我只知道 (x) & (-x) 的意思是取出 x 末尾的 0 和第一次出现的 1。其他我就一概不明了。最神奇的是这里面又出现一个 magic number 0x077CB531U。上次在 Quake III 里看到的那个牛顿转换的初始值的那个 magic number 的时候我就尿了。这次不例外。还好在网上看到了 Matrix67 给出的解释,不过没有仔细看,等过段时间再看看。

Lua :lobject.c

Quake III:trick 代码

Matrix67:神秘常量复出!用0x077CB531计算末尾0的个数