c++ - 在32位数字中查找第一个(最低)置位位置

Question

我需要在32位数字中获得一个1位数字，其中只有一个1位（总是）。用C ++或asm最快的方法。

例如

input:    0x00000001, 0x10000000
output:            0,         28

Answer 1

#ifdef __GNUC__，使用__builtin_ctz(unsigned)。 （GCC manual）。 GCC，clang和ICC都在所有目标ISA上都支持它。 （在没有本机指令的ISA上，它将调用GCC帮助器函数。）

对于64位整数，请使用__builtin_ctzll(unsigned long long)。不幸的是，GNU C位元内置函数没有采用固定宽度类型（尤其是尾随零），但是对于x86，unsigned在GNU C上始终为32位（尽管不是AVR或MSP430）。在我知道的所有GNU C目标上，unsigned long long始终为uint64_t。



在x86上，它将根据调整+目标选项编译为bsf或tzcnt。 tzcnt是现代Intel上具有3个周期延迟的单个uop，而在AMD上只有2个ups具有2个周期延迟（也许是反向的，以提供lzcnt uop？）https://agner.org/optimize/。无论哪种方式，它都直接由快速的硬件支持，并且比纯C ++所能做的任何事情都快得多。

对于未设置任何位的输入，内置函数具有未定义的行为，从而使其可以避免以bsf运行的方式进行任何额外的检查。



在其他编译器（尤其是MSVC）中，您可能想要TZCNT的内在函数，例如_mm_tzcnt_32中的immintrin.h。 （Intel intrinsics guide）。或者，对于非SIMD内部函数，可能需要包含intrin.h（MSVC）或x86intrin.h。



TZCNT在没有BMI1的CPU上解码为BSF，因为其机器代码编码为rep bsf。它们为非零输入给出相同的结果，因此编译器可以并且总是使用tzcnt，因为在AMD上这要快得多。 （它们在Intel上的速度相同，因此没有缺点。在Skylake及更高版本上，tzcnt没有虚假的输出依赖性。BSF这样做的原因是，对于输入= 0，它的输出保持不变）。

（这种情况对于bsr与lzcnt来说不太方便：bsr返回位索引，lzcnt返回前导零计数。因此，为了在AMD上获得最佳性能，您需要知道您的代码只能在CPU上运行支持BMI1 / TBM，因此编译器可以使用lzcnt）

请注意，设置为正好1位时，从任一方向进行扫描都会找到同一位。所以31 - lzcnt = bsr = bsf = tzcnt。如果移植到仅具有前导零计数且没有位反转指令的另一个ISA，则可能有用。



有关：


https://en.wikipedia.org/wiki/Find_first_set有关跨ISA的位扫描功能的更多信息。包括POSIX ffs()，该POSIX ffs()返回从1开始的索引，并且必须做更多的工作才能考虑输入为0的可能性。


编译器确实可以识别 并像内置函数一样内联（就像它们对memcpy或sqrt一样），但是当您实际上想要基于0的索引时，并不总是设法优化其固定序列来实现它的所有工作。告诉编译器只有1位设置特别困难。