从 unsigned int 中去除尾随零的最快方法

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);

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

从 unsigned int 中去除尾随零的最快方法

Fastest way to strip trailing zeroes from an unsigned int

c++

optimization

performance

bit-manipulation