Find most significant bit without bitshifts

Question

I am trying to find the most significant bit of unsigned number without using any bitshifts. This is what I have come up with, which looks very naive but it's very simple:

template<typename T>
constexpr uint8_t find_msb(const T& a_variable)
{
 static_assert(std::is_unsigned<T>::value, "Variable must be unsigned");
 constexpr uint8_t number_of_bits = std::numeric_limits<T>::digits;
 const std::bitset<number_of_bits> variable_bitset{a_variable};
 for (uint8_t msb = number_of_bits - 1; msb >= 0; msb--)
 {
 if (variable_bitset[msb] == 1)
 return msb + 1;
 } 
 return 0;
}

In C++17 this is a valid constexpr function and it appears it just vanishes into thin air with gcc, even with -O0: https://godbolt.org/z/pKI8fj.

But the non constexpr version is more involved: https://godbolt.org/z/eyj2bO.

In my use case I can use the constexpr version so it's not a big deal. How can I improve this code while maintaining readability and also without using any "smart" tricks and/or bitshifting?

• 200_success: Why don't you want to use bit-shifting?
• esote: If your goal is performance, have you done benchmarking to compare this function to bit shifting? Bit shifting is the usual way, and likely will be faster.
• Ali: @200_success, I have done some benchmarking here: quick-bench.com/s8V2LQQ8rgyD6E0PnX_7B7DquM8. Don't know if I've done it right or not. But if the no bit-shift version is as fast as the bit-shift one,as it appears to be, I'd prefer to have some code that can be read and understood by an average Joe like me. For some reason if you compile it with older versions of Clang the bitshift version(s) start to perform worse: quick-bench.com/o6IZaxnhAa_Zj2PGuIEDEWoqjaw
• Ali: @esote, see above please.
• Calak: For completeness, you can check this CR link about other ways.

Answer 1

• use std::uint8_t, to avoid relying on something that may or may not exist in the global namespace.

• An unsigned type will always be >= 0. So if a_variable is 0, this will result in undefined behaviour by accessing something out of bounds of the bitset (and either crash or loop forever).

• If we're finding the "most significant bit", I don't think avoiding bitshifts makes it more readable. (This requires understanding of both numeric_limits::digits, and std::bitset instead).