Determine the number of binary digits required to represent an integer $n$

Question

Let $r+1$ be the number of digits (bits) needed to represent the positive integer $n$ in binary as in:

For all $n \ge 1$ there exists a unique sequence $c_0, c_1, \dotsc , c_r$ such that $r$ is a non-negative integer, $c_k \in \{ 0, 1\}$ for all $k = 0, 1, \dotsc ,r$, $c_r = 1$, and $$n = c_r × 2^r + c_r−1 × 2^{r−1} + \dotsb + c_1 × 2^1 + c_0 × 2^0.$$

Prove that $r = [\log_2(n)]$.

I am trying to prove this without using induction

Answer 1

$n=1.2^r+...$. $\ $ So $n\ge 2^r$ and $log^{n}_{2}\geq log^{2^r}_{2}=r$. So $[log^{n}_{2}]\geq r $.

On the other hand $n\leq 2^r+2^{r-1}+...+2^0=\frac{2^0(1-2^{r+1})}{1-2}=2^{r+1}-1<2^{r+1} $. Therefore $\log n< \log^{2^{r+1}}_{2}=r+1$. Therefore $$\log ^{n}_{2}-1<r\le [\log ^{n}_{2}] $$ and $r\in \mathbb{N}$. So r=$[\log ^{n}_{2}]$.

Answer 2

By factoring out $2^r$ you can show that $2^r \le n < 2^{r+1}$. Taking base 2 logarithms you have the desired equality.

Answer 3

For a given $r$, the possible $n$ range from $2^r$ ($1$ followed by all zeroes) to $2^{r+1}-1$ (all ones). We have

$$2^r\le n<2^{r+1}$$ then $$r\le\log_2n<r+1$$ so that $$r=\lfloor\log_2n\rfloor.$$