How do the steps of successive division get converted into binary numbers?

1. Sep 3, 2011

treehouse

So, I can see that it works by dividing a number by its base, recording the remainder, and then repeating until the answer is 0 (instead of a fraction, you wind up with an answer of 0 with a remainder). But how do I convert all the steps' answers&remainders into a binary number?

2. Sep 3, 2011

vk6kro

Do you mean converting decimal numbers to binary? I can show you a method of doing this.

Try an example.

Choose the number 42 decimal.

The highest power of 2 that will be less than 42 is 32 (ie 2^5).

So, write down a 1 and subtract 32 from 42 to get 10.
1

The next lower power of 2 is 16 (2^4) but this is greater than 10 and you can't subtract 16 from 10, so write down a 0.
10

The next lower power of 2 is 8 (2^3) and this is less than 10 so write down a 1 and subtract 8
from 10 to get 2.
101

The next lower power of 2 is 4 (2^2) but this is greater than 2 (so you can't subtract it from 2) so write down a 0.
1010

The next lower power of 2 is 2 (2^1) and this equals 2 so write down a 1 and subtract 2 to get 0.
10101.

The next lower power of 2 (ie 2^0) is 1, but you can't subtract 1 from 0 so write down another 0.
101010

You can check if this is right like this:
1 times 32, plus 0 times 16, plus 1 times 8, plus 0 times 4, plus 1 times 2, plus 0 times 1.
= 32 + 8 + 2
= 42

So, 101010 is the binary equivalent of 42 decimal.

Last edited: Sep 3, 2011
3. Sep 3, 2011

treehouse

My professor's answer: "You take all the remainders (ignore the quotients) and assemble them into your binary number. The first remainder is the rightmost bit and the last remainder is the leftmost bit."

So the way you'd do forty-two using successive division would be to divide forty-two by two. The answer is twenty-one, and the remainder is 0 (so the first digit to the right is 0). Then you'd divide twenty-one by two, and the remainder is 1 (so the second digit to the right is 1). Then you'd divide ten by two. The answer is five with a remainder of 0. Next divide five by two. The answer is two with a remainder of 1. Then divide two by two - the remainder is 0. Then one by two - you get a 1 (the answer is zero with a remainder of 1). So this gives you 101010.

4. Sep 3, 2011

vk6kro

That seems to work, although I can't immediately see why it should. Did your prof give a proof of this?

Try 31

Divide by 2 gives 15 and 1 remainder.
1
Divide by 2 gives 7 and 1 remainder
11
Divide by 2 gives 3 and 1 remainder
111
Divide by 2 gives 1 and 1 remainder
1111
Divide by 2 gives 0 and 1 remainder
11111

Which is correct. 16 + 8 + 4 + 2 + 1 = 31