从无符号整数中去除尾随零的最快方法

Question

假设我们试图从某些无符号变量中删除尾随零。

uint64_t a = ...
uint64_t last_bit = a & -a; // Two's complement trick: last_bit holds the trailing bit of a
a /= last_bit; // Removing all trailing zeroes from a.

我注意到手动计算位数和移位速度更快。 （启用优化的 MSVC 编译器）

uint64_t a = ...
uint64_t last_bit = a & -a;
size_t last_bit_index = _BitScanForward64( last_bit );
a >>= last_bit_index

假设编译器内在

_BitScanForward64

比任何替代方案都快，是否有任何进一步的快速技巧可以使其更快？

Answer 1

在 x86 上，

_tzcnt_u64

是

_BitScanForward64

的更快替代品（如果可用）（可通过 BMI 指令集使用）。

此外，您可以直接在输入上使用它，不需要隔离最低位集，正如@AlanBirtles 在评论中指出的那样。

除此之外，还可以对单个变量进行标注。对于它们的数组，可能有一个 SIMD 解决方案。

Answer 2

您可以使用

std::countr_zero

(c++20) 并依靠编译器来优化它。

a >>= std::countr_zero(a);

^{（奖励：您不需要指定宽度，它适用于任何无符号整数类型）}

Answer 3

tz = (int)(log2((n & (n - 1)) ^ n)