查找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

对于 asm、早期的 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 内置函数不采用固定宽度类型（尤其是 leading 零版本），但

unsigned

在 x86 的 GNU C 上始终是 32 位（尽管不适用于 AVR 或 MSP430）。在我所知道的所有 GNU C 目标上，

unsigned long long

始终是

uint64_t

。

---

在 x86 上，它将编译为

bsf

或

tzcnt

，具体取决于调整 + 目标选项。

tzcnt

是现代 Intel 上具有 3 个周期延迟的单个微指令，并且只有 2 个微指令具有 2 个周期AMD 上的延迟（也许是一个位反转来提供 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_32

 中的 

immintrin.h。 （英特尔内在函数指南）。或者，您可能需要包含

intrin.h

(MSVC) 或

x86intrin.h

（对于非 SIMD 内在函数）。

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

MSVC 还具有用于实际 BSF/BSR 的

_BitScanForward

/

_BitScanReverse

，但 AMD 保证（Intel 也实现）的离开目的地未修改行为仍然没有被这些内在函数公开，尽管它们具有指针输出 API。

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

---

TZCNT 在没有 BMI1 的 CPU 上解码 as 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 可能很有用。

---

相关：

• 为什么打破 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 位设置尤其困难。