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
}

Answer 4

For non-zero unsigned integral types, you can use for gcc/clang one of the following

sizeof(unsigned)           - __builtin_clz(x)
sizeof(unsigned long)      - __builtin_clzl(x)
sizeof(unsigned long long) - __builtin_clzll(x)

For and for 32-bit and 64-bit integers on MSVC++ you can define a variable index to store the result of

_BitScanReverse(&index, x)
_BitScanReverse64(&index, x)

Those compiler wrappers will delegate to hardware instructions if your computer supports it, or some optimized bit-twiddling algorithm otherwise. You can write your own semi-platform independent wrapper around it using some #ifdefs.

There is a related stdcxx-bitops GitHub repo by Matthew Fioravante that was floated to the std-proposals mailinglist as a preliminary proposal to add a constexpr bitwise operations library for C++. If and when that gets standardized, there will be something like a std::clz() function template that does what you are looking for.

Answer 5

You can't perform this with an algorithm that is "faster" than shifting.

But you can use the following algorithm (including <cmath>):

int bits_n(int x) {
    return (x != 0)
        ? std::ceil(std::log(x) / std::log(2))
        : 1;
}

which is likely fast enough for most applications.

The std::log(x) / std::log(2) is required to perform a logarithm in base 2 (because the standard library of both C and C++ does not have a function to perform it).

And here you can find a live example.

Answer 6

Let's rephrase the question (for unsigned integers anyway): where does the MSB of my integer fall?

(just making sure you know why)

Let's think about this in decimal for a second. How many digits do you need to store a number? If I have the number written out (as the computer will for any number) all I have to do is count the digits, and report the position of the largest digit.

Now people don't think in binary, so you gotta translate between your decimal digit and your binary digit... except the computer will do that for you in the parse. The input to your function will be a binary number, so all you have to do is find the location of the MSB.

The fastest way to get the MSB of an unsigned integer is (unfortunately) not super portable.

What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?

Goes into all the ways to find the MSB. Long story short, while C++ may not give you a hook for it directly, most compilers have this built in as a assembly command. So that would be the fastest way.

Answer 7

Likely the fastest way is by using a prepopulated lookup table.

const size_t bitsMap [] =
{
  0, // value 0 (0)
  1, // value 1 (1)
  2, // value 2 (10)
  2, // value 3 (11)
  3, // value 4 (100)
 // ...
};

You could also populate this array (or vector or similar) by computing it at startup using mathematical means, such as ceil(log2(n)).

You now have a number n which you want to know how many bits will be needed to represent. You simply index the array using n -- the value storesd there is the number of bits.

int main()
{
  for (int i = 0; i < 256; ++i)
  {
    const size_t bits = bitsMap [i];
    cout << "The number " << i << " would take " << bits << " to represent."
  }
}

Indexing the array is immediate. I don't see how you'll get any faster than that.

Answer 8

int num = number;
int count_bit =0;
while (num) {
  num = num>>1;
  count++;
}
std::cout << num << " needs " << count << " bits" << std::endl;  

Answer 9

At first Initialize bit=0. Then looping until the square of bit equal to the number.

    void bits(int x) 
    {
                int bit = 1;

                while(pow(2,bit) < x) 
                {
                     bit++;
                }
                printf("%d",bit);
    }

Another method :

 int bit = static_cast<int>(log2(x));