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
}