Computers: Numbers: Decimal to Binary Conversion

Here is a simple algorithm for converting decimal numbers to binary using repeated division by 2.

Algorithm for converting decimal numbers to binary

The easiest way represent this algorithm is with a table. Start at the right and work left.

012481735Number
done100011Remainder (n%2)
  1. Put the number you want to convert (35 in this example) in the top-right box, and we're going to fill in the other columns going from right to left. The cell to the left becomes the number to the right divided by 2 using integer division. The cell below is 1 if the number is odd and zero if the number above is even. You can also think of this as the remainder after dividing by 2 (n%2 in C++ and Java). Because the remainder after dividing 35 by 2 is 1, we write the 1 below the 35.
  2. The second column from the right will have 17 in the top cell (the result of dividing the 35 by 2), and a 1 in the bottom cell because 17 is odd.
  3. Continue this process from right to left until the number becomes zero. You can continue, but it will soon be obvious that all further digits will be zeros.
  4. The resulting binary value is in the bottom row. The binary representation of 35 is 100011.

Another Example

Let's convert 6 to binary. Using the algorithm with this value gives a binary representation of 110.

Number0 136
Remainderdone110

Estimating the number of bits

Approximately 3.3 bits are required per decimal digit (23.3 is approximately 10). For example, 9,342,229,590 has 10 digits so it requires about 10*3.3 = 33 bits. The trick to making this work correctly is that 3.3 digits are required for all the decimal digits after the first. The first digit represents only a faction of the way thru the sequence of ten digits (eg, 6 only requires about 60% of those 3.3 bits. So the approximation for the same number as above, but with the first digit changed from 9 to 1 (1,342,229,590) is something around 30 bits.