Minimum number of bits to represent a given `int`

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.


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

return std::numeric_limits<T>::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()...

return boost::multiprecision::msb(x);

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
}