I have done with bit scan forward/reverse a 64bit using DeBruijn algorithm but cannot archive 128bit, __uint128_t. Is there any solution? Thanks in advance!
FYI code for bit scan forward/reverse a 64bit using DeBruijn algorithm:
constexpr std::uint32_t
bitScanForward<std::uint64_t>(std::uint64_t n) noexcept {
constexpr std::uint32_t seq[] = {
0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63};
return seq[((n ^ (n - 1)) * 0x03f79d71b4cb0a89ULL) >> 58];
}
constexpr std::uint32_t
bitScanReverse<std::uint64_t>(std::uint64_t n) noexcept {
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
constexpr std::uint32_t seq[] = {
0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63};
return seq[(n * 0x03f79d71b4cb0a89ULL) >> 58];
}
It is possible to adapt the 64-bit
BitScanReverse
to the 128-bit case, but that won't be very efficient, because 128-bit multiply and arithmetic is relatively expensive, as already pointed out by @Marc Glisse in his comment.Nevertheless, you can use your 64-bit
BitScanReverse
/BitScanForward
as a building block for a portable 128-bitbsf
/bsr
:On x86 this leads to reasonably efficient code, for example (gcc -O3 -m64 -march=nehalem):
To test the code, a single bit is set at different positions. The output is:
Another solution for efficient 128-bit
bsf
/bsr
is to recycle the ideas discussed in this question: Counting the number of leading zeros in a 128-bit integer