Minimum number of bits to represent a given `int`

Question

In C++, what's the fastest way to find out how many bits are needed to store a given int?

I can try dividing the number with 2 many times but divisions are pretty slow. Is there any fast way?

Edit:

Thanks a lot for the answers guys. When I say an int my post, I mean any 4-byte int. For example, if I store 30665, I want to get as a result 15 bits.

Answer 1

In C++20 you just need to use std::bit_width() or its equivalent

return std::numeric_limits<decltype(x)>::digits - std::countl_zero(x);

If you're on an older C++ standard then use boost::multiprecision::msb() which automatically maps to the appropriate intrinsic of the current compiler like __builtin_clz() or _BitScanReverse()... Or use #ifdef and manually switch the implementation depending on the current compiler

return boost::multiprecision::msb(x);               // Cross-platform

int index;
return _BitScanReverse(&index, n)) ? index + 1 : 1; // MSVC, ICC
return 32 - _lzcnt_u32(n);                          // ICC
return 32 - __builtin_clz(X));                      // GCC, Clang

Answer 2

You can break the value progressively by halves to narrow it down faster.

int bits_needed(uint32_t value)
{
    int bits = 0;
    if (value >= 0x10000)
    {
        bits += 16;
        value >>= 16;
    }
    if (value >= 0x100)
    {
        bits += 8;
        value >>= 8;
    }
    if (value >= 0x10)
    {
        bits += 4;
        value >>= 4;
    }
    if (value >= 0x4)
    {
        bits += 2;
        value >>= 2;
    }
    if (value >= 0x2)
    {
        bits += 1;
        value >>= 1;
    }
    return bits + value;
}

See it in action: http://ideone.com/1iH7hG

Edit: Sorry, the original version needed one additional term. It's fixed now.

Edit 2: In loop form as suggested in the comments.

int bits_needed(uint32_t value)
{
    int bits = 0;
    for (int bit_test = 16; bit_test > 0; bit_test >>= 1)
    {
        if (value >> bit_test != 0)
        {
            bits += bit_test;
            value >>= bit_test;
        }
    }
    return bits + value;
}

This algorithm returns 0 for an input of 0, meaning you don't need any bits at all to encode a value of 0. If you'd rather it return 1 instead, just change the return value to bits + 1.

Answer 3

Take a look at the famous Bit Twiddling Hacks page, if particular the section on counting bits.

For reference, here's the Brian Kernighan way to count the number of bits set:

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}