1
$\begingroup$

I don't know if this board would be an appropriate place for this question, but I have been trying to figure out how the divide-by-2 decimal to binary conversion trick works: in which you divide the number by 2, record its remainder and in the end write out the remainders in reverse to the get the final binary string. I have been using this for a long time but have never really considered why this works. Is there any explanation that could serve as a "proof" or even a basis for how people came up with this in the first place ? Thanks!

$\endgroup$
1
  • 3
    $\begingroup$ The "Divide by 2"-algorithm works for any numeral system, not just binary. To write a number in decimal, you repeatedly divide by 10 and write down the remainders. The algorithm basically is the definition of the numeral system. $\endgroup$ – Tom van der Zanden Feb 10 at 20:10
1
$\begingroup$

The algorithm follows fairly directly from our usual representation of numbers. Since most of us are more familiar with decimal, let's start there. Let's pick a number--say, 937. Since this is decimal, this means 9 * 102 + 3 * 101 + 7 * 100. So, repeatedly taking the remainder after dividing by 10 gives us the digits.

If we convert to binary, that's 11'1010'1001, because 937 is 1 * 29 + 1 * 28 + 1 * 27 + 0 * 26 + [...] + 1 * 20.

Just like in decimal, taking the remainder with repeated division by the number base we care about (2 in this case) gives us the digits of the number, starting from the least significant and progressing to the most significant, because that's pretty much how we define the representation of a number in a particular base.

$\endgroup$

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.