3
$\begingroup$

This guide here tells how to base 10 number to binary. For example, for the first bit, you take $356_{10} \div 2 = 178 \, R \, 0$.

Because the remainder was 0, the first bit is $0$ and we recurse this procedure on $178$.

I would like to be able to explain why this works (why it returns the bits in least significant order)? Why should I believe the resulting bits are actually the number in base 2?

$\endgroup$
  • 2
    $\begingroup$ Try proving to yourself that this method works for converting base $10$ to base $10$. That might help you "get it". $\endgroup$ – Callus - Reinstate Monica Sep 2 '14 at 1:45
2
$\begingroup$

Maybe consider a simpler example to start with :

Convert $20$ from base $10$ to base $2$

If it helps think of this example as counting $20$ apples in base $2$ system


Step 1 : Count how many $2$-apple groups are there
$\color{red}{20 = 2\times 10 + }\color{green}{0} $
This division tells us that the number of $2$-apple groups is $10$ and $1$-apple groups is $0$

Step 2 : Count how many $4$-apple groups are there
$\color{red}{10 = 2\times 5+ }\color{green}{0}$
This division tells us that the number of $4$-apple groups is $5$, $2$-apple groups is $0$ and $1$-apple groups is $0$

Step 3 : Count how many $8$-apple groups are there
$\color{red}{5 = 2\times 2 + }\color{green}{1}$
This division tells us that the number of $8$-apple groups is $2$, $4$-apple groups is $1$, $2$-apple groups is $0$ and $1$-apple groups is $0$

Step 4 : Count how many $16$-apple groups are there
$\color{red}{2 = 2\times 1 +}\color{green}{0}$
This division tells us that the number of $16$-apple groups is $1$, $8$-apple groups is $0$, $4$-apple groups is $1$, $2$-apple groups is $0$ and $1$-apple groups is $0$

Step 5 : Count how many $32$-apple groups are there
$\color{red}{1 = 2\times 0 + }\color{green}{1}$
This division tells us that the number of $32$-apple groups is $0$, $16$-apple groups is $1$, $8$-apple groups is $0$, $4$-apple groups is $1$, $2$-apple groups is $0$ and $1$-apple groups is $0$


Overall : $$\left(20\right)_{10} = \left(\color{green}{10100}\right)_{2}$$

As you can see, changing base is like changing the size by which you group things. I hope you might be having some idea about the place value!

$\endgroup$
1
$\begingroup$

It employs the division algorithm to unwind the radix $\,b\,$ representation of $\,n = n_0,\,$ i.e.

$\qquad\qquad\qquad \qquad\, n_0 = d_0 + d_1 b + \cdots + d_k b^k\quad\ \Rightarrow\ d_0 =\, n_0\, {\rm mod}\ b$

$\qquad n_1 := (n_0\!-d_0)/b = d_1 + d_2 b + \cdots + d_k b^{k-1}\,\Rightarrow\ d_1 =\, n_1\ {\rm mod}\ b$

$\qquad n_2 := (n_1\!-d_1)/b = d_2 + d_3 b + \cdots + d_k b^{k-2}\,\Rightarrow\ d_2 =\, n_2\ {\rm mod}\ b$

$\qquad\ \vdots\qquad\qquad\vdots\qquad\qquad\quad \qquad\qquad \vdots\qquad\qquad\qquad\qquad\quad\vdots$

$\endgroup$
  • $\begingroup$ The vertical dots present a very confusing pattern, but maybe that's just the mobile representation... $\endgroup$ – abiessu Sep 2 '14 at 3:22
0
$\begingroup$

$$\begin{array}{ccl} 356&=&2\cdot 178\\ &=&4\cdot 89\\ &=& 4+4\cdot 88\\ &=& 4+8\cdot44\\ &=& 4+16\cdot 22\\ &=& 4+32\cdot 11\\ &=&4+32+32\cdot10\\ &=&4+32+64\cdot5\\ &=&4+32+64+64\cdot 4\\ &=&4+32+64+128\cdot 2\\ &=&4+32+64+256 \end{array}$$ And that is essentially the base 2 representation of 356.

$\endgroup$
0
$\begingroup$

For your example, the first division simply says that $356 = 178\cdot 2 + 0$, so that the low-order bit of $356_2$ must be zero. Then $178$ is the decimal representation of all bits but the low-order bit of $178$. Proceed by induction.

$\endgroup$
  • $\begingroup$ Off-by-one error with the $357$? $\endgroup$ – abiessu Sep 2 '14 at 3:20

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.