Fastest way to strip trailing zeroes from an unsigned int

Question

Suppose we are trying to remove the trailing zeroes from some unsigned variable.

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.

I noticed that it's faster to manually count the bits and shift. (MSVC compiler with optimizations on)

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

Are there any further quick tricks that would make this even faster, assuming that the compiler intrinsic _BitScanForward64 is faster than any of the alternatives?

Answer 1

You can use std::countr_zero (c++20) and rely on the compiler to optimize it.

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

^{(bonus: you don't need to specify the width and it works with any unsigned integer type)}