0

I started reading the book Concrete Mathematics 2nd edition and there is a conversion I don't understand(is in page 11 of the book), it says:

Powers of 2 played an important role in our nding the solution, so it's natural to look at the radix 2 representations of $n$ and $J(n)$. Suppose $n$'s binary expansion is

$n = (b_m b_{m-1} ... b_1 b_0)_2$;

that is,

$n = b_m2^m + b_{m-1}2^{m-1} + · · · + b_{1}2 + b_0;$

So far this part is clear to me, is the classic binary notation: $1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+\cdots$

where each $b_i$ is either $0$ or $1$ and where the leading bit $b_m$ is 1. Recalling that $n = 2^m + l$, we have, successively,

$n = (1 b_{m-1} b_{m-2} ... b_1 b_0)_2 ;$

$l = (0 b_{m-1} b_{m-2} ... b_1 b_0)_2 ;$

$2l = (b_{m-1} b_{m-2} ... b_1 b_0 0)_2 ;$

$2l + 1 = (b_{m-1} b_{m-2} ... b_1 b_0 1)_2 ;$

$J(n) = (b_{m-1} b_{m-2} ... b_1 b_0 b_m)_2 :$

These are the inductions I just don't get, I don't see the explanation to those ones and zero values $n$, $L$, $2L$ and $2L+1$

Eduardo
  • 127

3 Answers3

2
  • $n = (1 b_{m-1} b_{m-2} ... b_1 b_0)_2$: the hypothesis is that the leading bit is $1$.
  • $l = (0 b_{m-1} b_{m-2} ... b_1 b_0)_2$: by definition $n=b^m+l$, and, writing this in base $2$, we have $$(1 b_{m-1} b_{m-2} ... b_1 b_0)_2=\underbrace{(1 0 0 ... 0 0)_2}_{=b^m}+\underbrace{(0 b_{m-1} b_{m-2} ... b_1 b_0)_2}_{\text{so this is }\: l}$$
  • $2l = (b_{m-1} b_{m-2} ... b_1 b_0 0)_2$: multipliying by the base amounts so shifting the bits one step on the left (just like multiplying by $10$ in the decimal system is done by adding a final $0$.
  • $2l + 1 = (b_{m-1} b_{m-2} ... b_1 b_0 1)_2$: $$2l+1=(b_{m-1} b_{m-2} ... b_1 b_0 0)_2+ (00 ... 0 01)_2.$$

Is it clearer?

Bernard
  • 175,478
  • the hypothesis is that the leading bit is 1. But is not, the leading bit is $m$ and what the equation is saying is that $m-1$ contains a bit with value 1, which is not true, because for example:

    when $n=10$ then $1*2^{m-1}=4$ which is not true, as the matter fact, for m-1 the bit should be zero.

     – Eduardo Sep 05 '18 at 17:37
  • The leading bit is $b_m$, and $m$ is just an ordinal, used to denote the rank of the bit. – Bernard Sep 05 '18 at 17:47
1

The bits for $n$ reflect the fact that the leading bit must be a $1$ or we would have a shorter number. It is like not writing $2$ in base $10$ as $02$. That $1$ is in the $2^m$ place, so we can subtract $2^m$ from $n$ to get $l$ and have $l$ look just like $n$ except the leading $1$ is deleted. That can result in leading zeros in $l$. Multiplying by $2$ in base $2$ just appends a zero on the right, which is the source of the $2l$ equation. As $2l$ is even, it has a $0$ in the ones bit so we can add $1$ without carrying, which is the source of the $2l+1$ equation. You have not defined $J(n)$ so I can't help there.

Ross Millikan
  • 374,822
  • The bits for n reflect the fact that the leading bit must be a 1 or we would have a shorter number.

    Not true, if $n = 10$ then "m = 3" and $m - 1$($2^2$) with the bit one should in reality be zero

     – Eduardo Sep 05 '18 at 17:25
  • @Eduardo: I added a note that $l$ could have leading zeros, which I think is what you were getting at. If $n=10_{10}=1010_2$ then $m=3$ and $l=010_2$, $2l=100_2, 2l+1=101_2$ – Ross Millikan Sep 05 '18 at 17:37
0

$$n = 2^m+l\tag{1}$$ where $2^m$ is the largest power of $2$ not exceeding $n$.

It results then $$l<2^m$$ Now, from $(1)$ and $n=b_m2^m+b_{m-1}2^{m-1} + \dots+b_0$, it follows that $$b_m2^m+b_{m-1}2^{m-1} + \dots+b_0=2^m+l$$ that splits into: \begin{equation} \begin{cases} b_m2^m=2^m\\ b_{m-1}2^{m-1} + \dots+b_0=l \end{cases} \implies\\\implies\begin{cases} b_m=1\\ 2l+1=\color{blue}2(b_{m-1}2^{m-1} + \dots+b_0)\color{blue}{+1}=b_{m-1}2^m + \dots+b_02+1 \end{cases} \end{equation} that joins into $$2l+1=b_{m-1}2^m + \dots+b_02+b_m$$

But $J(n)=2l+1$, then $$J(n)=b_{m-1}2^m + \dots+b_02+b_m$$

trying
  • 4,756
  • 1
  • 13
  • 23
  • How did you split the equation into two parts? (that splits into:) How did you join the equation? (that joins into:) – Eduardo Sep 05 '18 at 17:33