C++ how to get length of bits of a variable? [duplicate]

Question

Let's say there is a variable int x. It size is 4 bytes, that is 32 bits.

Then I assign a value to this var, x = 4567 (in binary 10001 11010111); So now, in memory it should look like this:

00000000 00000000 00010001 11010111

Is there a way to get the length of the bits which matter. In my excample, length of bits would be 13 (I marked them with bold). If I use sizeof (x) it returns me 4 bytes, which the size of int. How do I get only the size of bits that represent the number (without the unnecessarily zero's that follow after)?

Answer 1

unsigned bits, var = (x < 0) ? -x : x;
for(bits = 0; var != 0; ++bits) var >>= 1;

This should do it for you.

Answer 2

Warning: math ahead. If you are squeamish, skip ahead to the TL;DR.

What you are really looking for is the highest bit that is set. Let's write out what the binary number 10001 11010111 actually means:

x = 1 * 2^(12) + 0 * 2^(11) + 0 * 2^(10) + ... + 1 * 2^1 + 1 * 2^0

where * denotes multiplication and ^ is exponentiation.

You can write this as

2^12 * (1 + a)

where 0 < a < 1 (to be precise, a = 0/2 + 0/2^2 + ... + 1/2^11 + 1/2^12).

If you take the logarithm (base 2), let's denote it by log2, of this number you get

log2(2^12 * (1 + a)) = log2(2^12) + log2(1 + a) = 12 + b.

Since a < 1 we can conclude that 1 + a < 2 and therefore b < 1.

In other words, if you take the log2(x) and round it down you will get the most significant power of 2 (in this case, 12). Since the powers start counting at 0, the number of bits is one more than this power, namely 13. So:

TL;DR:

The minimum number of bits needed to represent the number x is given by

numberOfBits = floor(log2(x)) + 1

Answer 3

You're looking for the most significant bit that's set in the number. Let's ignore negative numbers for a second. How can we find it? Well, let's see how many bits we need to set to zero before the whole number is zero.

00000000 00000000 00010001 11010111
00000000 00000000 00010001 11010110
                                  ^
00000000 00000000 00010001 11010100
                                 ^
00000000 00000000 00010001 11010000
                                ^
00000000 00000000 00010001 11010000
                               ^
00000000 00000000 00010001 11000000
                              ^
00000000 00000000 00010001 11000000
                             ^
00000000 00000000 00010001 10000000
                            ^
...
                       ^
00000000 00000000 00010000 00000000
                      ^
00000000 00000000 00000000 00000000
                     ^

Done! After 13 bits, we've cleared them all. Now how do we do this? Well, the expression 1<< pos is the 1 bit shifted over pos positions. So we can check if (x & (1<<pos)) and if true, remove it: x -= (1<<pos). We can also do this in one operation: x &= ~(1<<pos). ~ gets us the complement: all ones with the pos bit set to zero instead of the other way around. x &= y copies the zero bits of y into x.

Now how do we deal with signed numbers? The easiest is to just ignore it: unsigned xu = x;