Computer Science

Home ] Up ] Next ]

      

Conversion of Number Representations
by Lionel E. Deimel

I have been fascinated by number representations ever since I was introduced to them in a formal way in junior high school. When I first began teaching in graduate school, I found myself having to think more deeply about working with number representations, in the context of computers. What follows is excerpted and adapted from a 30-page handout, “Notes on Number Systems,” I prepared for one of my classes in 1975. I was trying to give my students more insight into conversion from one base to another than they could get from most presentations of this topic. I assume the reader is familiar with positional number systems.
 

There are a number of ways to convert a number in one base (radix) to the equivalent number in another base. The standard techniques are all variations on three basic methods. The most straightforward  technique is perhaps the expansion method. Suppose we wish to convert the binary number 10101.1 to decimal. We may do so merely by using the definition of a number representation as an abbreviated polynomial, Thus, we may write

        10101.12 =1 x 24 + 0 x 23 + 1 x 22 + 0 x 21 + 1 x 20 + 1 x 2-1
            = 16 + 0 + 4 + 0 + 1 + 0.5
            = 21.510

But suppose we wish to go the other way. How would we convert 21.510 to binary? Writing 21.510 = 2 x 101 + 1 x 100 + 5 x 10-1 does not seem to be of much help. But look at what we get when we write this polynomial in binary notation (1010 = 10102 and 510 = 1012, of course):

        21.510 = (2 x 101 + 1 x 100 + 5 x 10-1)10
            = (10 x 10101 + 1 x 10100 + 101 x 1010-1)2
            = (10100 + 1 + 0.1) 2
            = 10101.12

The above examples illustrate an important fact about the conversion techniques that we will examine—namely, that they may be used to convert from any base to any other base. This is important to remember, particularly because many texts show conversion from radix-a to radix-b being done one way,  and conversion from radix-b to radix-a being done another, the implication being that the methods of conversion are fundamentally asymmetric. It is only fair to concede, however, that the expansion method is easier to use for converting binary (or, generally, non-decimal) numbers to decimal representations, than the reverse. The reason for this is that the calculations that must performed to convert from binary to decimal are done in decimal arithmetic, but those necessary to convert in the other direction must be done in binary arithmetic. If we refer to the number system in which the number to be converted is written as the source number system and the number system to which we want to convert as the target number system, then we may say that the expansion method requires the use of target number system arithmetic. Thus, all things being equal, we are likely to select the expansion method if we are converting from base-7 to base-10. Going the other way, we might look for some other method, one in which we may do the conversion using the source number system.

In fact, the two other conversion methods we will discuss do use source-number-system arithmetic. These are the multiplication/division method and the  subtraction method. Let us first consider the multiplication/division method.

Suppose we have a decimal integer we wish to convert to binary, say, 1310. It is easy to verify that 1310 = 11012. Now consider the following procedure: Divide the number to be converted (13) by the target radix (2). The result is an integer quotient (6) and an integer remainder (1). Repeat the procedure using the quotient in place of the original dividend. Continue in this fashion until the quotient is 0. The remainders so generated, when written beside one another make up the binary representation we desire. The arithmetic is carried out in the source base. In particular, we have

        13 / 2 = 6, r 1
        6 / 2 = 3, r 0
        3 / 2 = 1, r 1
        1 / 2 = 0, r 1

Notice that the digits of the answer are generated from right to left.

The above procedure appears to work. Why? A hint may be found by looking carefully at the first step in the example. The number to be converted is either even or odd. If it is even, the rightmost bit of the binary representation must be 0; if it is odd, that bit must be 1. (Why?) When an even number is divided by 2, the remainder is 0. When an odd number is divided by 2, the remainder is 1.

We can verify that this procedure works by looking at it more formally. For non-negative index i, let Ai be an integer. Let t be our target radix.  Let Ai+1 be the integer quotient of Ai and t, and let ri be the integer remainder. Then

        Ai / t = Ai+1 + ri / t

Of course, ri is an integer between 0 and t-1, inclusive, as it must be, in the representation of a base-t integer. If A0 is the integer to be converted to base-t, we may write the following equivalence, where the base-t representation of A0 is bmbm-1 ... b1b0:

        A0 = bmtm + bm-1tm-1 + ... + b1t1 + b0t0

Consider the first division. We have:

        A0 / t = (bmtm + bm-1tm-1 + ... + b1t1 + b0t0) / t
        A
1 + r0 / t = bmtm-1 + bm-1tm-2 + ... + b1 + b0 / t

But notice that bmtm-1 + bm-1tm-2 + ... + b1 is an integer, and b0 / t is a fraction (i.e., less than 1), since b0 < t. This means we must have

        A1 = bmtm-1 + bm-1tm-2 + ... + b1  and   r0 = b0

Now suppose this process has been carried out times, and we have developed the rightmost n digits of our result, namely, bn-1bn-2 ... b0. Since we have divided the original integer n times, ignoring remainders), we have

        An = bmtm-n + bm-1tm-1-n + ... + bn

Carrying out the next division gives

        An+1 + rn / t = bmtm-(n+1) + bm-1tm-1-(n+1) + ... + b+1 + bn / t

so that

        An+1 = bmtm-(n+1) + bm-1tm-1-(n+1) + ... + b+1  and  rn = bn

This constitutes a recursive proof that the procedure works. An analogous method is used to convert fractions. In this case, however, we multiply by the radix (hence, multiplication/division method). We get our digits from the integer part of any product, and we continue multiplying using only the fractional part. It is easy to convince yourself that this procedure works as well. An example is given below. Note that 0.7812510 = 0.110012.

        0.78125 x 2 = 1.56250,  digit generated is 1
        0.5625 x 2 = 1.1250,  digit generated is 1
        0.125 x 2 = 0.250,  digit generated is 0
        0.25 x 2 = 0.50, digit generated is 0
        0.5 x 2 = 1.0,  digit generated is 1

Here is another example, using the decimal fraction 0.3. It illustrates a fraction that repeats, in binary, in any case.

        0.3 x 2 = 0.6,  digit generated is 0
        0.6 x 2 = 1.2,  digit generated is 1
        0.2 x 2 = 0.4,  digit generated is 0
        0.4 x 2 = 0.8,  digit generated is 0
        0.8 x 2 = 1.6,  digit generated is 1
        0.6 x 2 = 1.2,  digit generated is 1 (repeats second line)

Therefore, we have that 0.310 = 0.0100110011001 ... 2. Note that we generate digits from left to right when converting fractions. Generally, digits are generated by the multiplication/division method from the radix point out. We may summarize this conversion method as follows:

  1. Write a target radix point for the answer
  2. Take the integer (fraction) in source number system and divide (multiply) by the target radix.
  3. Write down the remainder (integer) generated to the left (right) of the last symbol written.
  4. Is the quotient (fraction) 0? If yes, stop. Otherwise, quotient is new integer (fraction is new fraction). Go to step 2.

The final fundamental conversion scheme to be examined here is the subtraction method. In general, it is not a particularly efficient technique. In certain special situations, however, it is both convenient and intuitively appealing.

Consider the conversion of a decimal integer to another base. For example, say we wish to convert 1610 to base-3 notation. We notice that 32 = 9 is the largest power of 3 less than or equal to 16. We tally 1 and subtract 9 from 16, leaving 7. We now ask if we can subtract 32 again. Since we cannot, 1 must be out leftmost base-3 digit. We now see if we can subtract 31. We can—twice, in fact. We do so, and establish 2 as out next base-3 digit. We now have a remainder of 1, from which we can subtract 30 exactly once. Thus, we find that 1610 = 1213. This method is particularly appealing when converting decimal integers to binary if we remember the powers of 2. For a conversion to binary, of course, we never have to worry about subtracting a power of the radix more than once. The subtraction method may also be used for converting fractions. Notice that, for converting both integers and fractions, digits in the target representation are generated from left to right. Notice also that by looking at the problem from a slightly different angle, the subtraction method could become an addition method. Instead of subtracting powers of the base, we could construct our result by adding powers of the base to 0, always attempting to form a sum less than or equal to the number being converted. The reader can easily work out the details.

In the foregoing discussion, we have illustrated three methods for converting numbers between bases, any of which, in principle, can be used for any conversion problem. When working on a particular problem, the conversion method selected is generally chosen on the basis of the number system in which it is most convenient to do arithmetic. Usually, we want to avoid arithmetic in unusual bases (e.g., 7). When doing conversions by hand, then, we try to select a method that allows the use of decimal arithmetic, though using binary computation is sometimes convenient. Conversions between inconvenient bases usually require an intermediate conversion. Converting from base-5 to base-7, for example, one might first convert to base-10. The table below provides a guide to selecting a conversion method:

CONVERSION METHOD

BASE ARITHMETIC USED

Expansion Target
Multiplication/Division Source
Subtraction Source

 

Exercises

  1. Convert 26.62510 to binary using the three methods discussed above.
  2. Convert 100100.0012 to decimal using the three methods discussed.
  3. Convert 256910 to base-9 notation.
  4. Convert 27619 to base-5 notation.
  5. One method of converting binary integers to decimal integers is the multiply and add method. In this scheme, the leftmost digit is multiplied by 2 and added to the digit to its right. That sum is then multiplied by 2 and added to the next digit to the right, and so forth. Explain why this system works. Of what technique is it a variation? Can you convert fractions in an analogous way?

 

Home Up Next

 
Send mail to Lionel Deimel with questions or comments about Lionel Deimel’s Farrago.
Copyright © 2000-2017 by Lionel Deimel. All rights reserved.