1

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$)? enter image description here

Hans Hüttel
  • 4,271
Claire
  • 431
  • 1
    I don't understand your confusion. If we were talking about in base 10... how many digits are needed to write $10^5$? What is the largest $6$-digit number in base 10? – JMoravitz Aug 09 '21 at 19:37
  • 1
    Recall that arithmetic and properties such as this work just as well in one base as in any other... in base two we have properties related to $2^n$ appearing a lot... in base ten we have properties relating to $10^n$ a lot... You should be very well familiar with facts like $999$ being the largest three-digit number and $999$ being equal to $1000-1$ which is... strictly less than $1000$... – JMoravitz Aug 09 '21 at 19:39
  • 2
    $2^n$ is represent by one $1$ followed by $n$ zeros, so $n+1$ bits. As JMoravitz has pointed out, it's just like base $10$. – saulspatz Aug 09 '21 at 19:48
  • I think you are (rightly) a little confused by the wording of the example in your textbook. The example is interpreting the question "how many bits do you need to represent $48$?" to mean "what is the minimum number of bits needed to represent $48$?". The lower bound $31 < 48$ is then relevant: and it should be a strict inequality: $<$ not $\le$. So -2 to your textbook! – Rob Arthan Aug 09 '21 at 20:28
  • When analogizing to the case of base 10 considerations, as other comments have suggested, I find it helpful to presume that the smallest integer under consideration is $0$, rather than $1$, and that when considering (for example) 3 digit base 10 numbers, numbers $< 100$ are zero filled on the left so that the number has exactly 3 digits. Then, it is easy to see that there are exactly $(10)^3$ numbers between $0$ and $999$ inclusive, and that the leftmost digit of these 3-digit numbers runs from $0$ through $9$ inclusive. – user2661923 Aug 09 '21 at 20:30

2 Answers2

0

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

Godfather
  • 2,355
0

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

David K
  • 98,388