Why the ‘Divide By 2' Algorithm Works

I found myself struggling a bit to understand why the divide by 2 algorithm works for translating from base 10 to base 2. This site had a decent explanation (thanks, Carlos!)

Let’s start with 87 and translate both ways.

  • In base 10, this is equivalent to 8*10 + 7*1 or 8*10¹ + 7*10⁰.
  • To convert to binary, we do the divide by 2 algorithm:
  • Declare output holder with a little bracket for each digit [_][_][_][_]……[_]
  • ** 87/2 = 43 (rem 1 — means this base 10 number ‘87’ was odd, i.e. one more than a multiple of 2. We take this and put it in the right most column of our output digits) [_][_][_][_]……[1]
  • ** 43/2 = 21 (rem 1 — means 43 was odd) [_][_][_][_]…[1][1]
  • ** 21/2 = 10 (rem 1–-21 was odd) [_][_][_][_]…[1][1][1]
  • ** 10/2 = 5 (rem 0–-10 was even)[_][_][_][_]…[0][1][1][1]
  • ** 5/2 = 2(rem 1–-5 was odd) [_]…[1][0][1][1][1]
  • ** 2/2 = 1(rem 0–-2 was even) [_]…[0][1][0][1][1][1]
  • ** 1/2 = 0 (rem 1–-1 was odd) [1][0][1][0][1][1][1]

My Questions:

  • Why do that last step of 1 divided by 2? Why is 1 mod 2 = 1? I need to review some modulo algebra apparently.
  • Why do you put the numbers in reverse order? I need some more time to noodle on that.

Final Number = 1010111. I learned that it’s sometimes written with an extra 0 on the left to make it into a ‘byte’ which is 8 bits, i.e. 01010111. This is similar to adding a 0 on the left of a base 10 number, where ‘80’ is equivalent to ‘080,’ but we usually just write it 080. To be super explicit:

BASE 10

80 = __ +8*10¹ + 8*10⁰

080 = 0*10² + 8*10¹ + 8*10⁰

BASE 2

1010111 = __ + 1*²⁶ + 0*²⁵ + 1*²⁴ + 0*²³+1*²²+1*²¹+1*²⁰

01010111 = 0*2⁷ + 1*2⁶ + 0*2⁵ + 1*2⁴ + 0*2³+1*2²+1*2¹+1*2⁰

Raw Notes

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.