What's the explanation behind logarithmic solution of count total bits in a number?

Question

There are many solutions to count the total no. of bits of a number and below is one of them:-

int total_bits=log2(num)+1;

Can you explain, what's the use of log2(num) and adding 1?

Thanks & Regards

Answer 1

Let n be a positive integer. Let k be its number of bits.

Then n and k are linked by this mathematical relation:

2^(k-1) ≤ n < 2^k

Where ^ represents exponentiation.

Now, logarithm is a strictly increasing function, so this relation is equivalent to:

log2(2^(k-1)) ≤ log2(n) < log2(2^k)

And since log2 is exactly the inverse function of 2^..., this is the same as:

k-1 ≤ log2(n) < k

Or equivalently:

k ≤ log2(n) + 1 < k+1

In other words, the integer k is the integer part of log2(n) + 1. We can write this as:

k = floor(log2(n) + 1)

Or in language C:

int k = log2(n) + 1;

Note: In this answer, I used ^ to represent exponentiation. In most programming languages, ^ represents bitwise-xor, which is completely unrelated to exponents. Be careful and avoid using ^ for exponents in your programs.