determining the number of bits required to represent a number in binary

Question

In the example in the following slide, we follow the highlighted formula. With regard to the highlight, I'm confused why the number is greater or equal to $2^{n-1}$, while only need to be less than $2^n$ (not less than or equal to $2^n$)?

Answer 1

Think of a number with $n$ bits. Each bit can be 0 or 1, so you have $2^n$ combinations. However one of the combinations is the number 0 (i.e. all $n$ bits are 0). So you can only count up to $2^n-1$ with $n$ bits and not all the way up to $2^n$. That's why you see $<2^n$ in your example and not $\leq 2^n$.

Answer 2

What the example is illustrating is a general rule: if you have a positive whole number $x$ that you want to write in binary, and if

$$ 2^{n-1} \leq x < 2^n $$

where $n$ is a whole number, you need exactly $n$ bits to write $x.$

I hope you will agree that since the number $48$ is not a power of two, it really does not matter (for a number like that) whether we write $\leq$ or $<.$

But what if we want to write $64$ in binary? If the rule were

$$ 2^{n-1} \leq x \leq 2^n $$

then $64$ (which is equal to $2^6$) would fit the rule in two ways: it would fit with $n=6,$ because $2^(6-1)\leq 64\leq 2^6,$ and it would fit with $n=7,$ because $2^{7-1}\leq 64\leq 2^7.$

But it cannot be true both that it takes exactly $6$ binary bits to write $64$ and that it takes exactly $7.$ So this is not a good rule.

In fact you need $7$ bits to write $64.$ Notice that this is the answer you get if you write $\leq$ for $2^{n-1}$ but $<$ for $2^n.$

Another way to describe the rule with fewer symbols and more words is that you need exactly $n$ binary bits to write $x$ if $x$ is less than $2^n$ but not less than $2^{n-1}.$