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.1₂ =1 x 2⁴ + 0 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰ + 1 x 2^-1
            = 16 + 0 + 4 + 0 + 1 + 0.5
            = 21.5₁₀

But suppose we wish to go the other way. How would we convert 21.5₁₀ to binary? Writing 21.5₁₀ = 2 x 10¹ + 1 x 10⁰ + 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 (10₁₀ = 1010₂ and 5₁₀ = 101₂, of course):

        21.5₁₀ = (2 x 10¹ + 1 x 10⁰ + 5 x 10^-1)₁₀
            = (10 x 1010¹ + 1 x 1010⁰ + 101 x 1010^-1)₂
            = (10100 + 1 + 0.1) ₂
            = 10101.1₂

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, 13₁₀. It is easy to verify that 13₁₀ = 1101₂. 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 A_i be an integer. Let t be our target radix.  Let A_i+1 be the integer quotient of A_i and t, and let r_i be the integer remainder. Then

        A_i / t = A_i+1 + r_i / t

Of course, r_i is an integer between 0 and t-1, inclusive, as it must be, in the representation of a base-t integer. If A₀ is the integer to be converted to base-t, we may write the following equivalence, where the base-t representation of A₀ is b_mb_m-1 ... b₁b₀:

        A₀ = b_mt^m + b_m-1t^m-1 + ... + b₁t¹ + b₀t⁰

Consider the first division. We have:

        A₀ / t = (b_mt^m + b_m-1t^m-1 + ... + b₁t¹ + b₀t⁰) / t
        A₁ + r₀ / t = b_mt^m-1 + b_m-1t^m-2 + ... + b₁ + b₀ / t

But notice that b_mt^m-1 + b_m-1t^m-2 + ... + b₁ is an integer, and b₀ / t is a fraction (i.e., less than 1), since b₀ < t. This means we must have

        A₁ = b_mt^m-1 + b_m-1t^m-2 + ... + b₁  and   r₀ = b₀

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

        A_n = b_mt^m-n + b_m-1t^m-1-n + ... + b_n

Carrying out the next division gives

        A_n+1 + r_n / t = b_mt^m-(n+1) + b_m-1t^m-1-(n+1) + ... + b₊₁ + b_n / t

so that

        A_n+1 = b_mt^m-(n+1) + b_m-1t^m-1-(n+1) + ... + b₊₁  and  r_n = b_n

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.78125₁₀ = 0.11001₂.

        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.3₁₀ = 0.0100110011001 ... ₂. 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 16₁₀ to base-3 notation. We notice that 3² = 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 3² again. Since we cannot, 1 must be out leftmost base-3 digit. We now see if we can subtract 3¹. 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 3⁰ exactly once. Thus, we find that 16₁₀ = 121₃. 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:

Exercises

1. Convert 26.625₁₀ to binary using the three methods discussed above.
2. Convert 100100.001₂ to decimal using the three methods discussed.
3. Convert 2569₁₀ to base-9 notation.
4. Convert 2761₉ 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?

 
Send mail to lionel@deimel.org with questions or comments about Lionel Deimel’s Farrago.
Copyright © 2000-2008  All rights reserved.