Building Blocks

Converting between decimal and binary

Binary-to-decimal conversion:

The basic algorithm: Use the above formula

x = d₀ + 2(d₁+2(d₂+.....+2(d_k-1+2d_k)...))
and using decimal arithmetic.

            1 x <- d_k (move leftmost digit to x)
            2 i <- k-1 (set index to next digit)
            3 while i > 0 do
            4     x <- d_i +2x (compute inner product)
            5     i <- i - 1 (decrement index, end while loop)
            6 stop[**]

NOTE: If this conversion algorithm were performed in some other number system (such as octal - base 8, or quinary - base 5) then the resulting representation would be IN THAT BASE system:

For base 5 (quinary) to decimal:

x = d₀ + 5(d₁+5(d₂+.....+5(d_k-1+5d_k)...))

Decimal-to-binary conversion:
is based on repeated division by 2 in decimal, so that the binary digits generated from right to left (using decimal arithmetic):
Assume representation to be converted is associated with the variable x:
        1 s <- 0 (starting from rightmost digit)
        2 while x != 0 do
        3     d_s<- x mod 2 (get remainder of divide by 2)
        4     x <- floor(x/2) (reset x to quotient)
        5     s <- s + 1 (set up for next digit)
        6 stop[**]
WHY DOES THIS WORK?
Because - the "mod" function gives us back the remainder of the division of the number by 2, and this is the low order digit. That is:

(d_k2^k + d_k-12^{k- 1}+....+d₁2¹+d₀2⁰) mod 2 =

(2 (d_k2^k-1 + d_k-12^{k- 2}+....+d₁2⁰) + d₀2⁰) mod 2 =
d₀2⁰

Through the repeated application of the mod function to the quotient of the previous step, we successively get the successive digits of the binary representation.

For more help on number conversions see:
A Base Converter
The Implementation of Base Conversion

CS1104 Main Page
Last Updated 2002/02/04
© L.Heath, 2000, modified by J.A.N. Lee