(Last Mod: 27 November 2010 21:37:42 )
There are times when we need to convert the representation of a number in one base to a different base. It's important to understand that we are not changing the value of the number represented, only the representation itself. There are many conversion methods available and some lend themselves to certain situations better than others. For instance, some are better suited to a manual approach while others are better suited when implemented as a computer algorithm. Some are very streamlined if converting from base ten while others are very streamlined if converting to base ten. The more methods you are familiar with, the more likely you will choose an efficient method in a particular situation. Likewise, the more understanding you have of why each method works, the more likely you will be able to apply it without making the kinds of mistakes that are common when you are using a set of steps that you have merely memorized.
There are two obvious ways to accomplish base conversion that follow directly from the concept of what a positional number system is.
The first is to go through digit by digit and multiply it by the appropriate weight for that digit's position and sum up the result. If the arithmetic is performed in the target number base, then the final result will be in that base. Here the arithmetic is performed in the base of the number system being converted to and hence this is the most common way to convert from an arbitrary base to decimal because we are comfortable performing the math in base-10. It is not a common way to convert from decimal to another base for the simple reason that few people are comfortable performing arithmetic in any base other than base-10.
6357 = 6 x 72 + 3 x 71 + 5 x 70 = 6 x 49 + 3 x 7 + 5 x 1 = 32010
The second way to convert is to build up the number in the new base following exactly the steps introduced earlier - namely to figure out the weight of each position and figure out how many groupings of that weight can be removed from the number and proceed digit by digit until the units digit is reached (or further if something other than an integer is being converted). Here the arithmetic is performed in the base of the number system being converted from and hence this is the most common way to convert from decimal to an arbitrary base because, as above, we are comfortable performing the math in base-10. Similarly, it is not a common way to convert from another base to decimal.
70 = 1
71 = 7
72 = 49
73 = 343
Since 49 <= 320 < 343, the number in base-7 has three digits.
Dividing 320 by 49 yields 6.53 and so the there are six complete groupings of 49 in 320. The first digit is therefore '6'.
Subtracting off 6 x 49 = 294 leaves a remainder of 26 to be represented by the remaining two digits.
Dividing 26 by 7 yields 3.71 and so there are three complete groupings of 7 in 26. The second digit is therefore '3'.
Subtracting off 3 x 7 = 21 leaves a remainder of 5 which is the remaining digit.
So the result is 6357.
As indicated, the two methods described above are "brute force" methods and they always work - but they are not the only two methods. The fact that they are the most common is not a tribute to their efficiency, but merely to the fact that they are almost always the only two methods that are taught. As the saying goes, when the only tool you have is a hammer, everything looks suspiciously like a nail. So let's add a couple of tools to our toolkit - there are alternate methods that, with just a little bit of practice, enable much quicker conversions. These conversions, in the form presented, are limited to converting integers. But converting fixed-point and floating-point can be done by applying a bit of finesse, as we shall see later.
The first of these is repeated multiplication by the number base being converted from with the arithmetic being performed in the number base being converted to - hence this method lends itself to conversions to decimal from another base. The basis for this method becomes apparent by noting the following:
6357 = 6 x 72 + 3 x 71 + 5 x 70 = 6 x 7 x 7 + 3 x 7 + 5 = 7( 7(6) + 3 ) + 5 = 32010
To better see the systematic approach embodied by this method, consider the algorithm for using it:
To convert a number from an arbitrary base to decimal:
SET: result = 0
SET: present_digit = left-most digit
WHILE: present_digit exists
SET: result = result * old_base
SET: result = result + present_digit
SET: present_digit = the next digit to the right (if any)
If you walk through the above algorithm you will notice an inefficiency that is embedded in it. The first time through the loop you start with "result" equal to zero and you first multiply this by the number base - seven in our case - and then add the leftmost digit. Why not simply initialize "result" to the leftmost digit in the first place? You can and, when doing the conversion manually, you almost certainly will. But if you were encoding this algorithm into a computer program your algorithm has to be explicit about every step and the shortcut we would naturally use manually requires quite a bit more thought to explain it properly in a step-by-step algorithm. We could do it, and perhaps pick up some performance in the process, but it is generally better to keep your algorithms as simple as possible even if it is at the expense have having some steps whose effect is wasted from time to time.
Solution: Let's assume that it has been awhile since we've done a conversion and all we remember is that we walk across the number digit by digit and that we multiply our partial result by the number base each time we add one of the digits. But we don't remember if we go from right to left or from left to right. Also, we aren't sure when we start and stop multiplying by the number base. If our knowledge of how to use this method was based strictly on memorizing a bunch of steps, we would be stuck. But since our knowledge is based instead on understanding why the method works, we can quickly figure it out. For instance, we know that you can't multiply the result by the base after adding in the unit's digit because the unit's digit represents single quantities. Therefore we have just determined that we go from left to right and that we multiply by the base after adding in each digit except for the last one.
6
x8
--------
48
+3
========
51
x8
--------
408
+4
========
412
x8
--------
3296
+7
========
3303Result: 63478 = 330310
The second alternate method is basically the inverse of the method above and uses repeated division by the number base being converted to with the arithmetic performed in the number base being converted from - hence this method lends itself to conversions from decimal to another base.
Using the example above once more, to convert 32010 to base-7, we divide by the new number base, 7, and get
320 / 7 = 45 r 5 (45 with a remainder of 5), hence 5 is the last (i.e., rightmost) digit. Proceeding with just the whole part of the result, we have:
45 / 7 = 6 r 3, so 3 is the second digit from the right. Again proceeding with just the whole part of the result, we have:
6 / 7 = 0 r 6, and so 6 is the third digit from the right and since the whole part is now zero, we are finished.
A common way of writing this when converting by hand is:
7 | 320
7 | 45 r 5
7 | 6 r 3
7 | 0 r 6
The converted number is simply the remainders starting with the last one first, or 6357 in this example.
As with the previous method, this one also lends itself to a compact algorithm:
To convert a number from decimal to an arbitrary base:
SET: quotient = the original value being converted
SET: result (a string of characters) to be blank (no digits)
WHILE: quotient > 0
SET: quotient = quotient / new_base (integer portion i.e., integer division)
SET: remainder = quotient % new_base (modulo division)
TASK: Tack on "remainder" to front of "result" as the new MSD (Most Significant Digit or leftmost digit).
Use the above algorithm to make the conversion of 320 from base-10 to base-7.
Step 1: quotient = 320
Step 2: result = 0
Step 3: quotient > 0, so perform loop
Step 3.1: 320/7 = 45 r 5 so quotient = 45
Step 3.2: and remainder = 5
Step 3.3: result = 5
Step 3: quotient > 0, so perform loop
Step 3.1: 45/7 = 6 r 3 so quotient = 6
Step 3.2: and remainder = 3
Step 3.3: result = 35
Step 3: quotient > 0, so perform loop
Step 3.1: 6/7 = 0 r 6 so quotient = 0
Step 3.2: and remainder = 6
Step 3.3: result = 635
Step 3 Since (quotient = 0), we are finished.
Check the calculation of the exercise in the previous section by converting 3303 to base-8.
Solution: Again let's assume that it has been awhile since we've done this type of conversion and we want to make sure we do it right. Here the issue is whether our string of remainders are the digits in the result from left-to-right or right-to-left. If we ask what happens if we change the number by one, then we know that the result should only change by one. Now we ask which of the remainders is affected by a change of one and the answer is the first one. So the first remainder is the right most digit.
3303 / 8 = 412 r 7
412 / 8 = 51 r 4
51 / 8 = 6 r 3
6 / 8 = 0 r 6Result: 330310 = 63478
The method introduced above for converting decimal integers to another base using repeated division is, with practice, considerably quicker than using the brute force method and it is particularly well suited to purely manual use (pen and paper with no calculator). But it has two drawbacks if you are trying to speed up the process by using a calculator to perform the arithmetic. First, the division results are, on most calculators, presented only as a single number with a decimal fraction. So we must convert this decimal fraction to an integer numerator either mentally or by multiplying just the fractional part by the new number base. But this generally requires having to lose the whole number portion of the division result which is needed to continue the conversion. The result is that we have to store and retrieve intermediate results, either mentally, on paper, or in the calculator's memory, and the process is a bit cumbersome let alone affected by the individual and the capabilities of the calculator in use.
But there is another way to perform this task that uses repeated multiplication, albeit in a different fashion than is used to convert a value from another number base to decimal. To set the stage for how this method works, let's first look at a three digit decimal number and see how we could isolate the individual digits.
123
If we divide by the number base, ten in this case, enough times to get a result that is less than one, we would need to do so three times and end up with:
0.123 (after dividing by ten three times)
If we multiply by ten, we get
(0.123) x 10 = 1.23
The whole number part is the first digit. If we then remove the whole number part and multiply by ten again, we get:
(1.23 - 1) x 10 = 2.3
Now the whole number part is the second digit. If we repeat this process again, we get:
(2.3 - 2) x 10 = 3
If, instead of dividing by ten three times and then multiplying by ten three times we were to use a different base then the whole number parts that would have been revealed after each multiplication would have been the successive digits of the number as represented in the base used.
An informal proof that this is true is quite straightforward. Consider that we have a number x and we want to recover the digits of that number in an arbitrary base, b. Based on our definition of a positional numbering system, this string of digits (sticking with a three digit example) would be:
x = A x b2 + B x b1 + C x b0
By dividing by b three times (two is actually sufficient, but three is more systematic) we have:
x / b3 = A / b1 + B / b2 + C / b3
If we now multiply by b, we get:
A + (B / b1 + C / b2)
Keeping in mind that A, B, and C are all integers strictly less than b, we see that the above value, represented in any number base, will be have A as the whole number part and the term in parentheses as the fractional part. If we now subtract A (after recording it elsewhere as the first digit of our base-b representation) and multiply by b again we are left with
B + (C / b1)
Now B is the whole number portion and we repeat the same procedure as above, leaving use with:
C
From a practical standpoint, the benefit that this method has is that intermediate results don't need to be stored away and then recalled in order to determine the value of the current digit. The current digit is simply the whole number portion of the intermediate result (displayed in base ten, or more correctly, in the base of the original representation). This quantity is readily identifiable and can be recorded elsewhere as part of the new representation and then can be easily subtracted from the present result. Hence this method is extremely streamlined, especially for calculator-assisted conversions. It does have a drawback for hand-conversions - you must divide by the new number base N times and then multiply by the number base N times, hence it has about twice the number of multiplication/division operations as the repeated-division method above.
First, divide by eight enough times to yield a result that is less than one:
3303 / 8 = 412.875
412.875 / 8 = 51.609375
51.609375 / 8 = 6.451171875
6.451171875 / 8 = 0.806396484375
Since we had to divide by eight four times, we will need to multiply by eight four times and will end up with a four digit number in base-8. At each stage, we subtract off the whole number portion before proceding:
0.806396484375 * 8 = 6.451171875
0.451171875 * 8 = 3.609375
0.609375 * 8 = 4.875
0.875 * 8 = 7
Result: 330310 = 63478 (which agrees with our earlier example using repeated division)
Conversions between hexadecimal and binary are extremely simple - which is the primary reason that hexadecimal (and less so octal) is so widely used in fields related to digital technology. Each hexadecimal digit maps directly to four binary bits and each four binary bits map directly to one hex digit. This property can frequently be exploited to make conversions quicker and less prone to mistakes. For instance, when converting from decimal to binary (or vice-versa) it is generally easier to convert to hex first.
This same property applies to base-8 (known as "octal") as well, except here each octal digit maps directly to three binary digits.
Example: Convert 63478 (the result from a prior example) to hexadecimal
Solution: Normally when converting between two non-decimal bases, we would convert to decimal as an intermediate step so that our arithmetic can be performed in decimal. But here we can use binary as our intermediate step and avoid arithmetic altogether!
63478 = 110 011 100 111
Regrouping into groupings of four:
110 011 100 111 = 1100 1110 0111
Converting each group to hex:
1100 1110 0111 = 0xDE7
Final Result: 63478 = 0xDE7
Check: Converting this to decimal yields 3303 which agrees with the original example.
Most people are reasonably fast and accurate when multiplying and/or dividing by single digit values. This means that they can convert between base-10 and base-8 more readily than they can between base-10 and base-16. This ability can be exploited by converting base-10 to base-8 to base-2 to base-16 or the other way around. In many instances, it is quicker and more accurate to perform these three number base conversions than to perform the single direct one involving a multi-digit number base (multi-digit in base ten).
Although the above methods were developed for converting integers, we can use them to convert non-integer values by simply scaling the number to be converted appropriately before converting it, then scaling it back to its original value. We can even avoid this overhead if we use the method of repeated multiplication taking care to keep track of the radix point, which is the method we will develop first. Regardless of what method we use, we must be aware that we need to convert the proper number of digits beyond the radix point to preserve the level of accuracy contained in the original value.
For now, let's focus on the two repeated multiplication techniques. Converting from base-10 to another base is the simplest because we must do nothing extra beyond keeping track of when we reach the radix point. Other than that we can continue converting digits as long as we desire. When converting to base-10, we must hold off on dividing by the other number base until we have the value converted over to base-10 (since we want to perform the division in base-10 and not the original number base). So while we can continue converting digits beyond the radix point for as long as we chose, each one involves an extra multiplication by the original number base that we must eventually divide back out.
We must divide the original value by the new number base twice to get a value less than one:
13.14 / 5 = 2.628
2.628 / 5 = 0.5256
The first two multiplications we perform will therefore produce the whole number portion of the final result:
0.5256 * 5 = 2.628 (result = "2")
0.628 * 5 = 3.14 (result = "23")
Any subsequent multiplications will reveal successive digits to the right of the radix point:
(result = "23.")
0.14 * 5 = 0.7 (result = "23.0")
0.7 * 5 = 3.5 (result = "23.03")
0.5 * 5 = 2.5 (result = "23.032")
0.5 * 5 = 2.5 (result = "23.032")
We can continue this as far as we would like and, when we reach the point at which we wish to stop it is easy to see if the last digit should be rounded up or not. In this case, it should. So, to four radix places, our have:
Result: 13.1410 = 23.03235
2
x5
--------
10
+3
========
13 <-- Whole number portion
x5 (extra multipication)
--------
65
+0
========
65
x5 (extra multipication)
--------
325
+3
========
328
x5 (extra multipication)
--------
1640
+2
========
1642
x5 (extra multipication)
--------
8210
+3
========
8213Since we multiplied by 5 an extra four times, we must now divide by 5 four times:
8213 / 54 = 13.1408
Result: 23.03235 = 13.140810
Note that, in either technique, we could have separated out the original whole number and fractional parts and converted them separately before combining them back into a final result. Doing so would be particularly attractive if doing all the computations by hand.
Also note that we did not recover the exact value that we started with in the prior example. This should not be surprising since we had to round the result in the prior example and, since we rounded up, we could have anticipated that our result in the second example would end up a little larger than our original starting value. In general, the issue of rounding and how many digits should be converted is one that we must deal with, in some way, when we convert a non-integral value from one base to another.
Just as we could determine how many digits a certain integer requires when represented in a different number base, so to can we easily determine how many digits we need to have to the left of the radix point to correspond to a desired accuracy. Consider our original value in the prior examples, namely 13.14. One way to look at this number is to assume that it is accurate to within one-half of it's last digit since only values greater than or equal to 13.135 and less than 13.145 would have been expressed as 13.14. If we convert this value to another number base and then convert it back, we want to be assured that we at least get a value that falls somewhere within this range. We can do this as long as the least significant digit in the new base has a resolution smaller than this total range of 0.01.
Hence:
1 x b2-n < 1 x b1-m
Where:
b1 is the base we are converting from
b2 is the base we are converting to
m is the number of digits to the right of the radix point of the number in the old base
n is the number of digits to the right of the radix point of the number in the new base.
Solving for n yields:
n = m log(b1)/log(b2)
So to preserve the level of accuracy represented by the decimal value of 13.14, we need
n = 2 log(10)/log(5) = 2.86
We need to always round this value up to the next higher integer, so we need three digits beyond the radix point in our base-5 number.
A slightly different approach that some people might find more intuitive and, at least under some circumstances, easier to use is to scale the number being converted both before and after the conversion in such a way that the number that is actually converted is an integer. This permits us to use any of the techniques already developed for the conversion of integers without any modification at all.
The mathematical basis for this method is as follows:
x = (bn * x) / bn
Which simply recognizes that if we both multiply and divide one value by another that we have not changed the value. If x is a real value with a fractional component that we want to preserve in our conversion, then we only have to multiply by a sufficiently large value of bn to ensure that integer portion of it contains all of the significant information. For instance, if we want to convert 3.14 to some other base, then we can multiply it by 102 (since we want to preserve two base-10 radix places) and convert the integer 314 to the other base. We must then divide by one hundred and this might be difficult since it must be done in the other base - a base that we are almost certainly not comfortable performing arithmetic in.
The key to making this conversion technique convenient is to notice that it doesn't matter what the exact value is that we multiply by (since we will be dividing by that same value later) as long as it is large enough. In the above example of 3.14, this means that 102 is merely the smallest value we can use. In particular, notice that it doesn't matter which value of b we use - the base we are converting from or the base we are converting to. But, whichever one we choose, we must multiply/divide by that number in both bases - once before the conversion and once after. Doing so in base-10 is straight forward regardless of which value of b we choose, but doing so in the other base is only convenient if we do so in that number base. The reason for this is that multiplying and/or dividing a value by an integer power of the number base in which it is represented is accomplished by the simple act of shifting the radix point the appropriate number of places to the left or right. Hence, to make things simple, we will always use the non-base-10 value of b.
We want to preserve two decimal digits (to the right of the decimal point) so our scaling factor must be larger than 102. We can either use trial-and-error to find a value of n such that 6n>102 (and, most often, this can be done very quickly) or we can be explicit and solve for n:
n = 2 log(10)/log(6) = 2.57 (need n = 3)
The value we will convert will then be:
k = 63 * 3.14 = 678 (rounding to the nearest integer)
Converting this to base-6 by Repeated Multiplication:
678 / 6 = 113
113 / 6 = 18.83333
18.83333 / 6 = 3.1388889 (partial result: 3)
Taking the manual shortcut where we only divide until the whole number portion is easy to convert, we now work back:
0.1388889 * 6 = 0.83333333 (partial result: 30)
0.83333333 * 6 = 5 (partial result: 305)
0 * 6 = 0 (partial result: 3050)
Now all we must do is divide by 63 which is accomplished merely by moving the radix point three places to the left.
Result: 3.1410 = 3.0506
In this example we don't need to spend any time determining what our scaling factor will be - we want to multiply by at least 62 in order to preserve the two radix places (since the third happens to be zero) and so that is the value we will use.
The value we will convert will therefore be:
k = 62 * 3.056 = 3056
Converting this to base-10 by Repeated Multiplication:
((3 * 6) + 0)*6 + 5 = 113
Now all we must do is divide back out the factor of 62:
113 / 62 = 113 / 36 = 3.139
Result: 3.0506 = 3.13910
We are looking for an integer M such that
π = M / 164 => M = 164 x π = 205,887
Converting this to hex using any method of our choosing we get
M = 0x3243F
Result: π = M / 164 = 0x 3.243F
A similar approach can be used for working with numbers represented in an exponential format by first scaling the number to convert the exponent and then scaling the mantissa as above.
Solution: charge on one electron = 1.602 x 10-19 C, so it takes 6.242 x 1018 electrons to get 1 C of charge.
Our final value, in hex, is going to be of the form
value = A.BCD x 16EXP
Where A is a single non-zero hex digit in order for the value to be normalized. This means that:
A.000 x 16EXP <= (value = A.BCD x 16EXP) < 1.000 x 16EXP+1
Using the right-hand inequality, we can find the value of the exponent:
value < 1.000 x 16EXP+1
EXP + 1 > ln(value) / ln(16) = ln(6.242 x 1018) / ln(16) = 15.6
EXP = 15 = 0xF
We now use this to determine the mantissa that needs to be converted:
value = mantissa x 16E
mantissa = value / 16E = 6.242 x 1018 / 1615 = 5.4141
If we want to preserve this value to at least 0.1%, and since our method of conversion is to multiply by the new number base enough times to make this an integer, then we need to multiply by Bn such that:
1 < 5.4141 x 0.1% x Bn
Solving for n we get
n > ln [1/(5.414 x 0.1%)] / ln(16) = 1.9
n = 2
So the integer that we convert from decimal to hex is
M = 5.414 x 162 = 1386 = 0x56A
Dividing this by 162 and combining with the exponent yields a final result of:
0x 5.6A e F
As with the integer representations, moving between hex and binary is straightforward even when working with floating point values, although you must take care to make the necessary adjustments if you desire to keep the value normalized. We must recognize, however, that we can't just simply convert the exponent from hex to binary because what the relationship really means is that:
b.bbb x 2e1 = h.hhh x 16e = h.hhh x 2(4 x e)
So the exponent in the binary representation is four times the exponent in the hex representation. But this is easily accomplished by converting the hex representation's exponent to binary and shifting the result to the left two places.
Example: Convert the result from the previous example to a normalized binary exponential representation.
Solution: We can map from hex to binary directly, although the result may not be normalized.
0x 5.6A e F = 0101 . 0110 1010 e 11 1100 b
To normalize this, we must divide the mantissa by four (22) and add two to the exponent.
0x 5.6A e F = 1.0101 1010 10 e 11 1110 b
Converting from binary to hexadecimal is just as straightforward. First you multiply the mantissa by the power of two needed to make the exponent evenly divisible by four - meaning that the exponent's two least significant bits are zero. Then translate the result directly to hexadecimal.
Example: Convert the binary value 1.1001 0010 0001 1111 1011 01 e 1 to decimal.
Solution: First, we'll convert it to hex by multiplying the mantissa by two:
11.0010 0100 0011 1111 0110 1 e 0
Now we'll convert directly to hex:
value = 0x 3.243F68 e 0
To convert this to binary, we'll first make it an integer by multiplying by 166:
M = 166 x value = 0x 324 3F68
Converting this to decimal by the method of repeated multiplication yields
M = 52,707,176
To get the final value, we then divide this by 166:
value = 3.1415925
A lot of tools has been developed in this module, but like any set of tools, they provide significant flexibility and efficiency if a bit of effort is invested to gain competence with them. Even more importantly, the techniques developed are based on a fundamental understanding of the properties of numbers and how we represent them. An understanding of these concepts is critical to many engineering disciplines including computer hardware design, software engineering, embedded system design, encryption, information security, network design, and digital signal processing just to name a few.
The author would like to acknowledge the following individual(s) for their contributions to this module: