请问有什么高效的算法可以在C编程中计算32位无符号整数前导零的数量？
3个回答
25
本讨论假设你的编译器要么不支持该操作，要么无法生成足够好的汇编代码。请注意，这两种情况在现今都不太可能发生，因此我建议您只需在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来实现这一点。虽然我们仍然没有太多的指令级并行性，但我们已经摆脱了所有的分支，并且使用的周期比之前的解决方案少。好得多。
那么这个pop指令怎么样，这不是欺骗吗？大多数架构都有一个1个周期的pop指令，可以通过编译器内置函数（例如gcc的__builtin_pop）访问。否则，存在基于表格的解决方案，但必须注意在时间和缓存访问之间进行折衷，即使表格完全保存在L1缓存中也是如此。
最后，像往常一样，对于《黑客乐园》，我们开始漫步在奇怪的领域。让我们使用浮点数计算一些前导零：
union {
unsigned asInt[2];
double asDouble;
};
asDouble = (double)k + 0.5;
return 1054 - (asInt[LE] >> 20);
首先，有一个小警告：不要使用这个算法。就标准而言，这会触发未定义行为。这个算法只是为了好玩而复制而不是实际使用。使用需自担风险。
既然免责声明已经说完了，那么它是如何工作的呢？它首先将int转换为double，然后提取double的指数部分。很简洁的东西。如果在一个小端机器上执行，LE常量应该是1，如果在一个大端机器上执行，则为0。
这应该为你提供了各种位操作算法的简要概述。请注意，本书有几个这些算法的变体，其中有各种权衡，但我会让你自己去发现它们。
- Ze Blob
2
1使用这个函数，您可以忽略机器的字节序。int clz(uint32_t x) {
union {
double ddd;
int64_t uu;
} u;
u.ddd = x + 0.5;
return 1054 - (int)(u.uu >> 52);
} - martian
1不幸的是，hackersdelight.org似乎已经不存在了，该域名被垃圾邮件发送者接管。通过谷歌搜索可以在网上找到一些PDF副本。 - Edward Falk
23
这可能是使用纯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;
- R.. GitHub STOP HELPING ICE
4
2值得一提的是，《黑客的乐趣》也包含了这个算法以及它如何以及为什么有效的解释。我只是懒得复制整个表格 :) - Ze Blob
我的表格和他们的一样吗？我通过手动反转用于ctz函数的表格，使其作为clz使用。 - R.. GitHub STOP HELPING ICE
3实际上有两种方法。第一种是Harley的方法，使用更大的表格尺寸（64），没有增量，并且使用不同的乘数（0x06EB14F9）和移位操作（26）。第二种是Goryavsky的方法，实际上派生了几个变体，具有各种权衡（较小的表格尺寸，更好的ILP等）。 - Ze Blob
法律方面：您是否允许在商业软件中使用您的“clz”？询问是因为2018年5月2日（UTC）或之后贡献的内容根据CC BY-SA 4.0条款（[链接]（https://stackoverflow.com/help/licensing））分发。而CC BY-SA 4.0可能与商业/专有软件的许可证存在（兼容性）问题。如果可以，那么在什么条件下？ - pmor
-3
让我们数一下不是前导零的数字的数量。之后我们只需要做 (32 - n)。首先，如果数字是零，那么 n 就是零。否则：
n = 1 + floor(log2(x))
也就是说，我们使用二进制对数来确定最高位非零位的位置。在x86上，我们可以使用FYL2X指令来高效地完成这个操作，该指令计算log2。
但既然我们正在谈论x86指令，我们不妨看看实际可用的内容。在这里！http://en.wikipedia.org/wiki/Find_first_set - 你可以看到有很多直接执行所需操作的指令 - 如果你愿意编写汇编代码或至少确认你的优化编译器在给定一些精心编写的C代码后生成这些指令。
- John Zwinck
5
1OP特别要求最好的算法是用C语言编写的，而不是x86汇编语言。 - R.. GitHub STOP HELPING ICE
2“Efficiently”和“fyl2x”不适合放在同一句话中。这是迄今为止最慢的指令之一。 - harold
2为什么你要选择这种古老的（而且慢 - x87）方式，而不是在新架构上使用
bsr或lzcnt呢？ - Brett Hale@BrettHale：我链接了关于bsr的维基百科页面。当然应该使用这个。我在最后一段讨论了这个问题。 - John Zwinck
@John Zwinck，非常感谢您提供的所有信息。我们还可以使用ceil(log2(x+1))来找到x中二进制位的数量。对吗？现在，计算它需要恒定的时间吗？如果是有符号整数，我应该怎么做才能计算给定输入的二进制位数？再次感谢您的合作 :) - rzmuc
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
longlong.h中执行此操作的代码。它由2200行代码组成，具有多个分支，取决于CPU及其特性。该文件没有使用一行内联ASM。 - jww__asm__。 - pmor