Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A friend of mine had a homework assignment where he needed to convert decimal(base 10) numbers to binary. I helped him out and explained one of the ways I was taught to do this.

The way I showed him was to repeatedly divide the number by 2 and then take the remainder, the binary number will be the remainders read from bottom to top.

ex:  Convert 22 to a binary representation

22 / 2 = 11 R 0
11 / 2 = 5  R 1 
5  / 2 = 2  R 1
2  / 2 = 1  R 0
1  / 2 = 0  R 1

answer = 10110

After I showed him the algorithm and an example, he set off to do the rest of his problems. Today he sent me an email and asked me why this method works. I was sort of shocked by that question, I have never given a second thought to why this works, I only did as I was told knowing that if I performed this algorithm I would always get the right answer in binary.

I thought about it for awhile and still can't seem to figure out WHY this method works, any help would be appreciated. This isn't for an assignment, merely my curiosity and frustration at not asking this question before.

Thanks

Edit

Do you mind explaining how you went from:

$$n=e_0\times 2^0 + e_1\times 2^1 + \cdots + e^k\times 2^k$$

to

$$n=e_0 + 2\Bigl(e_1 + e_2\times 2 + \cdots + e_k\times 2^{k-1}\Bigr),$$

I am not following the transition to the closed form.

share|improve this question
    
By "Decimal numbers", you mean base 10, right? –  Arturo Magidin Nov 28 '11 at 1:48
    
@ArturoMagidin Yes I mean base 10, I will revise above. Thanks. –  Hunter McMillen Nov 28 '11 at 1:53

2 Answers 2

up vote 8 down vote accepted

Remember the meaning of base 10 notation; when you write a number as $$d_nd_{n-1}\cdots d_2d_1d_0$$ where $d_i$ is the $i$th digit (from right to left), what you are saying is that the number is equal to: $$ d_0\times 10^0 + d_1\times 10^1 + d_2\times 10^2 + \cdots + d_n\times 10^n.$$ So, for example, $5381$ represents the number $$1\times 10^0 + 8\times 10^1 + 3\times 10^2 + 5\times 10^3 = 1 + 80 + 300 + 5000.$$

Writing a number in binary (base 2) is meant to represent the number in exactly the same way, but with powers of $2$ in stead of powers of 10: the expression $$e_k\cdots e_3e_2e_1e_0{}_{[2]}$$ represents the number $$n=e_0\times 2^0 + e_1\times 2^1 + e_2\times 2^2 + e_3\times 2^3 + \cdots + e_k\times 2^k.$$

Since every summand except the first one is a multiple of $2$, we can write: $$\begin{align*} n&=e_0\times 2^0 + e_1\times 2^1 + \cdots + e_k\times 2^k\\ &=e_0 + \left(e_1\times 2\right) + \left(e_2\times 4\right) + \cdots \left(e_k\times 2^{k}\right)\\ &= e_0 + \left( 2 \times e_1\right) + \left( 2\times (e_2\times 2)\right) + \cdots + \left(2\times(e_k\times 2^{k-1})\right)\\ &= e_0 + 2\Bigl(e_1 + (e_2\times 2) + \cdots + (e_k\times 2^{k-1})\Bigr). \end{align*}$$ That means that when you divide $n$ by $2$ you get a remainder of $e_0$ (the right-most digit of the base 2 expression of $n$), and a quotient of $$q_1=e_1\times 2^0 + e_2\times 2^1 + \cdots + e_k\times 2^{k-1}.$$ Now you can determine the next binary digit of $n$ by repeating the process with $q_1$: we write $$q_1 = e_1 + 2\Bigl(e_2 + e_3\times 2 + \cdots + e_k\times 2^{k-2}\Bigr),$$ so the remainder of dividing $q_1$ by $2$ is the penultimate digit of the binary expression of $n$, and the quotient is $q_3$, with $$q_3 = e_2 + e_3\times 2 + \cdots + e_k\times 2^{k-2}.$$

Lather, rinse, and repeat until the remainder quotient is $0$.

share|improve this answer
    
Please refer to my edit above, as the commenting system doesn't support latex. –  Hunter McMillen Nov 28 '11 at 2:10
    
@Hunter: Yes, it does supposet LaTeX; you just have to enclose it in dollar signs, like so: $ a_1 + 3$ produces $a_1+3$. Anyway: I've added some lines. Basically, every term except the first is a multiple of $2$, so you can factor $2$ from every summand except the first, and then "un-distribute" that factor of $2$ by pulling it out. –  Arturo Magidin Nov 28 '11 at 2:15
    
Thank you, that cleared up my confusion. –  Hunter McMillen Nov 28 '11 at 2:16

It becomes crystal clear if you rewrite it as follows

$\rm\qquad\qquad 22\ =\ {\color{red} 0}\ +\ 2\ (11)$

$\rm\qquad\qquad\quad\ \ = \ {\color{red} 0}\ +\ 2\ ({\color{green} 1}\ +\ 2\ (5))$

$\rm\qquad\qquad\quad\ \ = \ {\color{red} 0}\ +\ 2\ ({\color{green} 1}\ +\ 2\ ({\color{magenta} 1}\ +\ 2\ (2)))$

$\rm\qquad\qquad\quad\ \ = \ {\color{red} 0}\ +\ 2\ ({\color{green} 1}\ +\ 2\ ({\color{magenta} 1}\ +\ 2\ ({\color{brown} 0}\ +\ 2\ (1))))$

$\rm\qquad\qquad\quad\ \ = \ {\color{red} 0}\cdot 2^0 + {\color{green} 1}\cdot 2^1 + {\color{magenta} 1}\cdot 2^2 + {\color{brown} 0}\cdot 2^3 + 1\cdot 2^4\ $ expanded to normal form: polynomial in $2$

$\rm\qquad\qquad\quad\ \ = \ 1{\color{brown} 0}{\color{magenta} 1}{\color{green} 1}{\color{red} 0}\ $ in binary notation (reverse the above color-codified binary digits)

Therefore the binary digits arise simply by iterating the process of division by 2, with remainder. See also my posts on Horner's method.

share|improve this answer
    
thank you, this is very helpful –  Hunter McMillen Nov 28 '11 at 3:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.