# 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.

0 | 1 | 2 | 4 | 8 | 17 | 35 | Number |

done | 1 | 0 | 0 | 0 | 1 | 1 | Remainder (n%2) |

- 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.
- 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.
- 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.
- 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.

Number | 0 | 1 | 3 | 6 |

Remainder | done | 1 | 1 | 0 |

## Estimating the number of bits

Approximately 3.3 bits are required per decimal digit (2^{3.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.