查找 32 位数字中唯一设置位的位置

Question

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

例如

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

Answer 1

在 C++20 中，#include <bit>并使用std::countr_zero(x)( cppreference )。
使用允许或鼓励编译器使用的选项进行编译tzcnt，例如-march=x86-64-v3

对于早期的 C++ 以及 asm 中的高效之处，请参阅此答案的其余部分。

#ifdef __GNUC__，用于__builtin_ctz(unsigned)计算尾随零 （GCC 手册）。GCC、clang 和 ICC 在所有目标 ISA 上都支持它。（在没有本机指令的 ISA 上，它将调用 GCC 辅助函数。）

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

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

在 x86 上，它将编译为bsf或tzcnt取决于调整 + 目标选项。 tzcnt在现代 Intel 上是一个具有 3 个周期延迟的单个 uop，而在 AMD 上只有 2 个 uop，具有 2 个周期延迟（也许是一个位反转以提供 lzcnt uop？）https://agner.org/optimize/ / https:// uops.info/。无论哪种方式，它都直接由快速硬件支持，并且比纯 C++ 中可以执行的任何操作都要快得多。成本大约与x * 1234567（在 Intel CPU 上，bsf/与前端微指令、后端端口和延迟tzcnt方面的成本相同。）imul r, r, imm

该内置函数对于未设置位的输入具有未定义的行为，从而允许它避免任何额外的检查（如果它可能作为bsf.

在其他编译器（特别是 MSVC）中，您可能需要 TZCNT 的内在函数，例如_mm_tzcnt_32from immintrin.h。（英特尔内在函数指南）。或者您可能需要包含intrin.h(MSVC) 或x86intrin.h对于非 SIMD 内在函数。

与 GCC/clang 不同，MSVC 不会阻止您使用尚未启用编译器自行使用的 ISA 扩展的内部函数。

MSVC 也有_BitScanForward/_BitScanReverse来表示实际的 BSF/BSR，但是 AMD 保证（Intel 也实现）的离开目标未修改行为仍然没有被这些内在函数公开，尽管它们有指针输出 API。

• VS：_BitScanReverse64 内在的意外优化行为- 假定始终写入指针输出：/
• _BitScanForward _BitScanForward64 缺失 (VS2017) Snappy - 正确的标头
• 如何使用 MSVC 内在函数来获得与此 GCC 代码等效的内容？

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

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

请注意，如果设置了 1 位，则从任一方向扫描都会找到相同的位。所以31 - lzcnt = bsr在这种情况下与 相同bsf = tzcnt。如果移植到另一个只有前导零计数且没有位反转指令的 ISA，则可能有用。

有关的：

• 为什么打破 LZCNT 的“输出依赖”很重要？现代编译器通常知道打破 lzcnt/tzcnt/popcnt 的错误依赖关系。bsf/bsr 也有一个，我认为 GCC 在这方面也很聪明，但讽刺的是可能不是。
• x86 bsr/bsf 如何具有固定延迟，而不依赖于数据？它不会像伪代码所示那样循环遍历位吗？- 伪代码不是硬件实现。
• https://en.wikipedia.org/wiki/Find_first_set有更多关于跨 ISA 位扫描函数的信息。包括 POSIX ffs()，它返回一个从 1 开始的索引，并且必须做额外的工作来考虑输入为 0 的可能性。

编译器确实会ffs()像内置函数一样识别并内联它（就像它们对 memcpy 或 sqrt 所做的那样），但当您实际上想要一个基于 0 的索引时，并不总是能够优化掉它们的固定序列为实现它所做的所有工作。告诉编译器只有 1 位设置尤其困难。