Two Bugs

The algorithm is easy enough: divide, divide, divide, ... collect the bits. But sometimes people mess up. The two most common ways to mess up are:

1. Putting the bits in the wrong order.
2. Stopping too soon.

1. To get the bits in the correct order, think about the first bit. The very first modulo division, N mod 2, results in a 1 bit if the number is odd, and a 0 bit if the number is even. This bit goes into the rightmost position (the one's place).

2. People seem to stop prematurely when they see 1 mod 2. But that is a legitimate operation (the result is 1). If you divide one by two, you get zero with a remainder of one.