如何计算32位无符号整数中的前导零

请问有人能告诉我什么是一种有效的算法来计算C编程中32位无符号整数中前导零的数量?

此讨论假定您的编译器不支持该操作,或者它不能产生足够好的程序集。 请注意,现在这两种情况都不太可能,所以我建议在编译器上使用__builtin_clz作为gcc或等效__builtin_clz

请注意,确定哪个是“最佳”clz算法只能由您完成。 现代处理器是复杂的动物,这些算法的性能将在很大程度上取决于您运行它的平台,您投入的数据以及使用它的代码。 唯一可以确定的方法是测量,测量和测量更多。 如果你无法区分,那么你可能没有看到你的瓶颈,你的时间会更好地花在其他地方。

现在无聊的免责声明已经不在了,让我们来看看Hacker’s Delight对这个问题的看法。 一项快速调查显示,所有算法都依赖于某些描述的二进制搜索。 这是一个简单的例子:

 int n = 32; unsigned y; y = x >>16; if (y != 0) { n = n -16; x = y; } y = x >> 8; if (y != 0) { n = n - 8; x = y; } y = x >> 4; if (y != 0) { n = n - 4; x = y; } y = x >> 2; if (y != 0) { n = n - 2; x = y; } y = x >> 1; if (y != 0) return n - 2; return n - x; 

请注意,这适用于32个整数,如果需要,它也可以转换为迭代版本。 不幸的是,这个解决方案并没有很多指令级的并行性,并且有很多分支,这些分支并没有带来非常好的一点点算法。 请注意,上面代码的分支免费版本存在,但它更详细,所以我不会在这里重现。

因此,让我们使用pop指令(计算位数)来改进解决方案:

 x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >>16); return pop(~x); 

那怎么办? 关键是最后的pop(~x)指令,它计算x的零个数。 为了使零的计数有意义,我们首先需要摆脱不领先的所有0。 我们通过使用二进制算法正确传播1来做到这一点。 虽然我们仍然没有太多的指令级并行性,但我们确实摆脱了所有分支,并且它比先前的解决方案使用更少的周期。 好多了。

那么流行教学怎么样,不是作弊? 大多数架构都有一个1周期弹出指令,可以通过编译器内置函数访问(例如gcc的__builtin_pop )。 否则,存在基于表的解决方案,但是在对高速缓存访​​问的周期进行折衷时必须小心,即使该表完全保留在L1高速缓存中也是如此。

最后,正如黑客的喜悦一样,我们开始在陌生的地区游荡。 让我们用浮点数来计算一些前导零:

 union { unsigned asInt[2]; double asDouble; }; asDouble = (double)k + 0.5; return 1054 - (asInt[LE] >> 20); 

首先,一点警告: 不要使用这种算法 。 就标准而言,这会触发未定义的行为。 这是有趣因素的再现,而不是任何实际用途。 使用你自己的危险。

现在免责声明已经不在了,它是如何运作的? 它首先将int转换为double,然后继续提取double的指数分量。 整洁的东西。 如果在little-endian机器上执行,则LE常量应为1,在big-endian机器上执行0。

这应该为您简要介绍一下这个问题的各种比特算法。 请注意,这本书有几种不同的变化,可以进行各种权衡,但我会让你自己发现它们。

这可能是在纯C中实现它的最佳方式:

 int clz(uint32_t x) { static const char debruijn32[32] = { 0, 31, 9, 30, 3, 8, 13, 29, 2, 5, 7, 21, 12, 24, 28, 19, 1, 10, 4, 14, 6, 22, 25, 20, 11, 15, 23, 26, 16, 27, 17, 18 }; x |= x>>1; x |= x>>2; x |= x>>4; x |= x>>8; x |= x>>16; x++; return debruijn32[x*0x076be629>>27]; } 

一个限制:写入时,它不支持零输入(结果应为32)。 如果所有输入都小于0x80000000 ,则可以通过将表中的第一个值更改为32来支持零而无需额外成本。否则,只需在开头添加一行:

  if (!x) return 32; 

让我们计算不是前导零的位数。 之后我们就做了(32 – n)。 首先,如果数字为零,则n为零。 除此以外:

 n = 1 + floor(log2(x)) 

也就是说,我们使用基数为2的对数来找出最重要的非零位在什么位置。 我们可以使用FYL2X指令在x86上有效地执行此操作,该指令计算log2。

但是现在我们正在讨论x86指令,我们也可以看一下真正可用的内容。 这里是! http://en.wikipedia.org/wiki/Find_first_set – 您可以看到有很多指令可以直接执行您想要的操作 – 如果您愿意编写汇编或至少确认您的优化编译器生成这些指令给你一些精心编写的C代码。

一种解决方案是(在Obj-c中):

 // Assuming, your 32-bit unsigned integer is in i NSInteger nrLeadingZeroes = 0; while (i >= 0) { i = i << 1; nrLeadingZeroes++; } 

编辑:(见下面的评论):

 // Assuming, your 32-bit unsigned integer is in j int i = (int)j; int nrLeadingZeroes = 0; while (i >= 0) { i = i << 1; nrLeadingZeroes++; }