C++ how to get length of bits of a variable?

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)?

That's a popular question. Have you ever tried google search? — Maxim Egorushkin, Apr 01 '15 at 10:44
relevant to http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer — ha9u63ar, Apr 01 '15 at 10:45
Are you trying to [count leading zeroes](http://stackoverflow.com/questions/2589096/find-most-significant-bit-left-most-that-is-set-in-a-bit-array)? — Dmitry Grigoryev, Apr 01 '15 at 10:47
Sorry, tried to google it, but couldn't find the answer. Thank you for the link ha9u63ar, I will read there! — qazerty23, Apr 01 '15 at 10:50
Note that counting the number of set bits and the highest set bit are two different things. The latter is much easier. — CompuChip, Apr 01 '15 at 10:51
Whats the length of `0` ? It's always important to consider the _edge cases_ of your problems.. — MSalters, Apr 01 '15 at 14:02
@LightnessRacesInOrbit - This may have been a premature close. This question is C++, and it could include template meta-programming techniques. The cited dup is also a slightly different question. — jww, Sep 24 '17 at 01:51
@jww: There are C++ answers, including those that provide template meta-programming techniques. No reason to ask again. — Lightness Races in Orbit, Sep 25 '17 at 21:55

score 8 · Answer 1 · edited Apr 01 '15 at 13:19

8

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

This should do it for you.

edited Apr 01 '15 at 13:19

CompuChip

8,620
4
22
46

answered Apr 01 '15 at 11:21

grimble

81
3

Excellent ! Short, simple, and fully portable ! Just a small issue in case of a negative number because of the sign bit – Christophe Apr 01 '15 at 11:50
... which can be fixed by writing `var = (x < 0) ? -x : x`. – CompuChip Apr 01 '15 at 13:15
1

I'd expect `-1` to have length 32 (or `sizeof(int)*CHAR_BIT)`), not 1. – MSalters Apr 01 '15 at 14:01
The result will be 32, if `-1` is converted to `unsigned`. (Assuming two's complement representation of signed numbers) – grimble Apr 01 '15 at 14:16
Explain? (the original solution was without the ternary operator, if that matters) – grimble Apr 01 '15 at 14:23

CompuChip · Answer 2 · 2015-04-01T11:07:00.460

6

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

edited Apr 01 '15 at 11:07

answered Apr 01 '15 at 10:57

CompuChip

8,620
4
22
46

6

Numerically correct and horribly inefficient. – MSalters Apr 01 '15 at 13:59
@MSalters Why inefficient ? – Hritik Oct 20 '18 at 10:39
2

@hritik: log2 is a floating point operation. It calculates many bits after the decimal point. Floor() then throws them away. – MSalters Oct 21 '18 at 09:21
What we want is a way to do this using integer-only bitwise operations. – BD107 Nov 15 '20 at 15:33

score 1 · Answer 3 · answered Apr 01 '15 at 14:15

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;

C++ how to get length of bits of a variable?

3 Answers3