查找32位数字中第一个（最低）设置位的位置

Question

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

例如

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

Answer 1

#ifdef__gnuc__，使用__builtin_ctz（无符号）计数尾随零（GCC手册）。GCC、clang和ICC都支持它的所有目标ISAS。（在没有本机指令的ISAs上，它将调用一个GCC帮助器函数。）

前导与后导是按照打印顺序写入时，MSB优先，就像8位二进制00000010一样，有6个前导零和1个后导零。（当转换为32位二进制时，将有24+6=30个前导零。）

对于64位整数，请使用__builtin_ctzll（无符号long long)。不幸的是，GNU C bitscan builtins不采用固定宽度类型（尤其是前导零版本），但是unsigned在GNU C for x86上始终是32位的（尽管不是用于AVR或MSP430)。无符号long long总是uint64_t在我所知道的所有GNU C目标上。

对于未设置位的输入，builtin具有未定义的行为，如果它可能以bsf运行，则可以避免任何额外的检查。

在其他编译器中（特别是MSVC)，您可能需要TZCNT的intrinsic，比如_mm_tzcnt_32fromimmintrin.h。（英特尔内部指南）。或者，您可能需要包含intrin.h(MSVC)或x86intrin.h来表示非SIMD的intrinsics。

与gcc/clang不同，MSVC并不阻止您对编译器自己没有启用的ISA扩展使用intrinsics。

MSVC对于实际的BSF/BSR也有_bitscanforward/_bitscanreverse，但是AMD保证的（以及Intel也实现的）离开目的地未修改的行为仍然没有被这些固有特性公开，尽管它们有指针输出API。

• vs:_bitscanReverse64 intrinsic-pointer-output的意外优化行为被假定始终被写入：/
• _bitscanforward_bitscanforward64缺少(VS2017)快速正确的标头
• 如何使用MSVC内部特性获得与此GCC代码等效的代码？

TZCNT在没有BMI1的CPU上解码为BSF，因为它的机器码编码是rep BSF。对于非零输入，它们会给出相同的结果，所以编译器可以并且总是使用tzcnt，因为这在AMD上要快得多。（它们在Intel上是相同的速度，所以没有缺点。在Skylake和以后的版本中，tzcnt没有错误的输出依赖关系。BSF有，因为它在输入=0时没有修改输出）。

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

请注意，如果设置了1位，从两个方向扫描都会发现相同的位。因此31-lzcnt=bsr在本例中与bsf=tzcnt相同。如果移植到另一个只有前导零计数而没有位反向指令的ISA可能会有用。

相关的：

null