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

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.