 CSC 133 - Discrete Mathematical Structures
 Complements in Radix r Number Systems Java Primitive Data Types: Integers Reals Practice

Conversion of Bases

In the decimal system we can represent a real number as .

If we use another base say b then .

We want to convert a decimal number to binary with the arithmetic calculations done in binary. We can use nested multiplication as in Horner's Algorithm to represent a number:

N = (…(an× 10 + an - 1)10 +… + a2)10 + a1)10 + a0.

The 10 is converted to b = 10102 and each of the ai must be replaced by (ai)b = a i (here the computer does a table lookup).

N2 = (…(a n× b + a n - 1) b +… + a 2) b + a 1) b + a 0.

Now the binary arithmetic is very easy for the computer.

Example

 25,431 = (((2× 10 + 5)10 + 4)10 + 3)10 + 1, = (((10× 1010 + 101)1010 + 100)1010 + 11)1010 + 1, table lookups, binary arithmetic, = 110001101010111, base 2.

As binary arithmetic is very tedious for us we would prefer to utilize the division algorithm and perform repeated division by the base recording the remainder each time.
Consider N = (…(a n× b + a n - 1) b +… + a 2) b + a 1) b + a 0. Divide both sides of this equation by b , the remainder is then a 0, repeat and the remainder is a 1, then a 2, etc., until the quotient is 0 and we have recovered Nb in the remainders as

a na 3a 2a 1a 0.

Example Convert 25,431 to binary using the division algorithm.

 2)25431 2)99 a 7 = 0 2)12715 a 0 = 1 2)49 a 8 = 1 2)6357 a 1 = 1 2)24 a 9 = 1 2)3178 a 2 = 1 2)12 a 10 = 0 2)1589 a 3 = 0 2)6 a 11 = 0 2)794 a 4 = 1 2)3 a 12 = 0 2)397 a 5 = 0 2)1 a 13 = 1 2)198 a 6 = 1 0 a 14 = 1

25,431 = 110001101010111

Converting a fraction to base b is as simple, just use repeated multiplication and recover the integer part each time until the desired accuracy is achieved.

Example Convert 0.1234 to binary.

 0.1234 x 2 0.2468 b1 = 0 . 9488 x 2 1.8976 b6 = 1 .2468 x 2 0.4936 b2 = 0 . 8976 x 2 1.7952 b7 = 1 .4936 x 2 0.9872 b3 = 0 . 7952 x 2 1.5904 b8 = 1 . 9872 x 2 1.9744 b4 = 1 . 5904 x 2 1.1808 b9 = 1 . 9744 x 2 1.9488 b5 = 1 . 1808 x 2 0.3616 b10 = 0, etc.

0.1234 = .0001111110

Now the computer saves a lot of calculation time by using a table lookup. We can do the same thing in our math. Most of us have the binary numbers through 8 memorized. Converting from base 8 to base 2 is just a 3 digit lookup (converting from hexadecimal to binary is just a 4 digit lookup).

Example Covert 25431.1234 to binary by first converting to octal then "looking up" the octal to binary conversion. We will treat the integer and fraction parts separately for now.

 8)25431 .1234 x 8 0.9872 b1 = 0 8)3178 a0 = 7 . 9872 x 8 7.8976 b2 = 7 8)397 a1 = 2 . 8976 x 8 7.1808 b3 = 7 8)49 a2 = 5 . 1808 x 8 1.4464 b4 = 1 8)6 a3 = 1 . 4464 x 8 3.5712 b5 = 3 0 a4 = 6

 6 1 5 2 7 . 0 7 7 1 3 110 001 101 010 111 . 000 111 111 001 011

 Complements in Radix r Number Systems Primitive Data Types: Integers Reals Practice by J. A. Tompkins tompkinsj@uncw.edu