# Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$?

I've stumbled on this definition on Wikipedia, and I can't figure out why.

I could probably start the demonstration by saying that, with $n$ bits, you can create $2^n$ possible different numbers, so $2^n=x$. If I rewrite the expression with logarithms, I find $\log_2x = n$, so the base-2-log of the total number of possible combinations of 0 and 1 is $x$.

And I'm stuck here. I'm probably seeing this from the wrong angle. Also, I wonder what is that $+1$ for?

Sorry if it's a dumb question, but the only way I can memorize a formula is to give a meaning to its numbers.

## 2 Answers

If you have $n$ bits available you can represent the numbers $0$ to $2^n-1$ in binary. Therefore, if you want to represent a number $x$ in binary, you need a number of bits $n$ that is large enough so that

$$\begin{split} 2^n - 1 & \geq x\\ n & \geq \log_2(x+1)\,. \end{split}$$

Now there are two cases for $\log_2(x+1)$:

• It is an integer. Then $\log_2(x)$ won't be. It'll be slightly less. So $\lfloor\log_2(x)\rfloor + 1$ will yield the same value. (The exception where $x=1$ can be checked separately.)
• It isn't an integer. In this case $\lfloor\log_2(x)\rfloor + 1$ yields the next largest integer just as $\lfloor\log_2(x+1)\rfloor + 1$ would.

In either case, because $n$ is always an integer we can write

$$n \geq \lfloor\log_2(x)\rfloor + 1\,.$$

Here is a more general results:

The base $b$ expansion of the positive integer $n$ uses $\lfloor \log_b n \rfloor + 1$ digits.

To prove this, note that the minimal integer whose base $b$ expansion requires $d$ digits is $b^{d-1}$, and the maximal integer whose base $b$ expansion required $d$ digits is $b^d-1$.

Let us compare this to the set of values satisfying $\lfloor \log_b n \rfloor + 1 = d$, or rather $\lfloor \log_b n \rfloor = d-1$. These are the values for which $d-1 \leq \log_b n < d$, or equivalently, $b^{d-1} \leq n < b^d$. This is exactly the same condition as above.