带来一篇Lua疾速盘算log2

欢迎大家来到仓酷云论坛！lua的源码，欣喜愈来愈多。好比明天看到了一个疾速盘算log2(x)的***。代码以下：
intluaO_log2(unsignedintx){
staticconstlu_bytelog_2[256]={
0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
};
intl=-1;
while(x>=256){l+=8;x>>=8;}
returnl+log_2[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的***的时分又看到了QuakeIII中的奇妙代码。我不能不说，QuakeIII真是一个奇妙的引擎，内里有大批值得进修的代码，等我浏览完lua的源码以后下一步就是浏览它了。先来看看它是怎样举行log2盘算的：


staticconstintdebruijn[32]={
0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8,
31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9
};
#defineLOG2(X)(debruijn[((Uint32)(((X)&-(X))*0x077CB531U))>>27])




看到这段代码我至心都快被吓尿了。起首我只晓得(x)&(-x)的意义是掏出x开端的0和第一次呈现的1。其他我就一概不了然。最奇妙的是这内里又呈现一个magicnumber0x077CB531U。前次在QuakeIII里看到的谁人牛顿转换的初始值的谁人magicnumber的时分我就尿了。此次不破例。还幸亏网上看到了Matrix67给出的注释，不外没有细心看，等过段工夫再看看。

Lua：lobject.c
QuakeIII：trick代码
Matrix67：奥秘常量复出！用0x077CB531盘算开端0的个数
如果您觉得本篇CentOSLinux教程讲得好，请记得点击右边漂浮的分享程序，把好文章分享给你的小伙伴们！