Prove that the binary representation of a number $n$ will use $\lfloor\lg n\rfloor+1$ bits.

Question

I'm taking a 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.

Answer 1

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$$

Answer 2

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

Answer 3

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.