位扭曲的黑客

Warning: Can only detect less than 5000 characters

Warning: Can only detect less than 5000 characters

因此，例如，如果r为0，则有c = int（log2（（double）v））。如果r为1，那么我们有c = int（log2（sqrt（（double）v））））如果r为2，那么我们有c = int（log2（pow（（double）v，1./4） ））。 2005年6月11日，福尔克·赫夫纳（FalkHüffner）指出，ISO C99 6.5 / 7留下了类型标准的习惯用法*（int *）＆amp;未定义，他建议使用memcpy。 unsigned int v; //输入以计数尾随零位int c; //输出：c将计数v的尾随零位，//因此，如果v为1101000（以2为底），则c将为3if（v）{v =（v ^（v-1））＆gt; ＆gt; 1; //将v的尾随0s设置为1s，并为（c = 0; v; c ++）{v＆gt; == 1; }}其他{c = CHAR_BIT * sizeof（v）;}

（均匀分布的）随机二进制数中尾随零位的平均数为1，因此与以下更快的方法相比，此O（尾随零）解决方案还不错。 Jim Cole建议我在2007年8月15日添加一个线性时间方法来计算尾随零。2007年10月22日，Jason Cunningham指出我忽略了为v。unsigned int v粘贴unsigned修饰符； // 32位字输入，对rightunsigned int c = 32上的零位进行计数； // c将是右边的零位数v＆amp; = -signed（v）; if（v）c-; if（v＆amp; 0x0000FFFF）c-= 16; if（v＆amp; 0x00FF00FF）c -= 8; if（v＆amp; 0x0F0F0F0F）c-= 4; if（v＆amp; 0x33333333）c-= 2; if（v＆amp; 0x55555555）c-= 1;

在这里，我们基本上执行与并行查找对数基数2相同的操作，但是我们首先隔离最低的1位，然后从最大值开始递减，然后递减。对于N位字，操作数最多为3 * lg（N）+ 4。 Bill Burdick建议进行优化，将时间从2011年2月4日的4 * lg（N）减少。 // 32位字输入，对rightunsigned int c上的零位进行计数； // c是右边的零位数，//因此，如果v为1101000（以2为底），则c为3 //注意：如果0 == v，则c = 31.if（v＆amp; ; 0x1）{//奇数v的特殊情况（假设发生一半的时间）c = 0;} else {c = 1; if（（v＆amp; 0xffff）== 0）{v＆gt;＆gt; = 16; c + = 16; } if（（v＆amp; 0xff）== 0）{v＆gt;＆gt; = 8; c + = 8; } if（（v＆amp; 0xf）== 0）{v＆gt;＆gt; = 4; c + = 4; } if（（v＆amp; 0x3）== 0）{v＆gt;＆gt; = 2; c + = 2; } c-= v＆amp; 0x1;}

上面的代码类似于前面的方法，但是它通过类似于二进制搜索的方式通过累加c来计算尾随零的数量。第一步，它检查v的低16位是否为零，如果是，则移位v右移16位并将c加16，这会使v中考虑的位数减少一半。随后的每个条件步骤同样将位数减半直到只有1。此方法比最后一个方法快（大约33％），因为if语句的主体执行的频率较低。马特·惠特洛克（Matt Whitlock）于2006年1月25日提出了这一建议。安德鲁·夏皮拉（Andrew Shapira）在2007年9月5日关闭了几次手术（通过将c = 1设置为无条件减法）。 unsigned int v; //在vint r中找到尾随零的数目； //

......