# Prove that the binary representation of a number n will use floor(lg(n)) + 1 bits.

I'm taking Computer Algorithms class and one of my problems is from Skiena's Algorithm Design Manual, 2-41:

Prove that the binary representation of $n \ge 1$ has $\lfloor \lg n \rfloor +1$ bits ($\lg$ is base 2)

Some base cases:

$n = 1, \lfloor \lg 1 \rfloor + 1 = 1$
$n = 2, \lfloor \lg 2 \rfloor + 1 = 2$
$n = 5, \lfloor \lg 5 \rfloor + 1 = 3$
$n = 15, \lfloor \lg 15 \rfloor + 1 = 4$

I don't know where to go from there though. Any help appreciated.

Let $$n \in \mathbb{N}$$, suppose $$n$$ requires $$d$$ digits in it's base 2 representation, we'd like to show that $$d = \lfloor \log_2(n) \rfloor+1$$.

At most we have $$n = 1 \ldots 1$$, that is $$d$$ 1's in a row. But we know that is $$\sum_{i=0}^{d-1} 2^i = 2^d - 1$$

At a minimum the first digit is a 1 and the rest are zeros (since the powers start at 0 right to left, this is $$2^{d - 1}$$).

We now have the following bound on $$n$$. $$2^{d-1 } \le n \le 2^d - 1$$

Taking log base 2 on on the above inequality yields: (Call this inequality $$\beta$$) $$d - 1 \le \log_2 (n) \le \log_2(2^d -1 )$$

Note: Taking the log respects the inequalities because $$\log_2(\cdot)$$ is a strictly increasing function (check it's derivative)

We will attempt to take the floor of $$\beta$$. Since $$d-1$$ is an integer $$\lfloor d-1 \rfloor = d-1$$, as for $$\log_2(2^d-1)$$, we must look a little closer. Since $$2^{d-1} \le 2^d - 1 < 2^d$$ and , we know that $$d-1 = \log_2(2^{d-1}) \le \log_2(2^d - 1) < log_2(2^d) = d$$

Therefore $$\lfloor \log_2(2^d - 1) \rfloor = d-1$$ and so the result of taking the floor of $$\beta$$ yields

$$d - 1 \le \lfloor \log_2 (n) \rfloor \le \lfloor \log_2(2^d -1 ) \rfloor = d-1$$

In other words

$$d - 1 \le \lfloor \log_2 (n) \rfloor \le d-1$$

So $$d - 1 = \lfloor \log_2 (n) \rfloor \Leftrightarrow d = \lfloor \log_2 (n) \rfloor + 1$$

Hint: For which numbers $n$ is $\lg n$ an integer?

Hint
Note that the binary representation of $2^n$ has $n+1$ bits.
Find then that the binary representation of a sum of $2^{k_i}$ with distinct $k_i$ has $\max_i k_i + 1$ bits.
Finally conclude that any integer in the interval $[2^n, 2^{n+1})$ has a binary representation of exactly $n+1$ bits.