8
$\begingroup$

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.

$\endgroup$

3 Answers 3

5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.