Number Systems
Computer circuits are bistate electronic devices. As a consequence of this all information in a computer is in bistate electronic form. To accomodate the examination of this information, we represent the (two) possible states by assigning one of the BInary digiTs (0 or 1) to each state and use "bit patterns" or "bit strings" as representations of the information.
When a bit pattern is interpreted as a numeric quantity, it often becomes necessary to convert from the binary (base 2) number system into decimal (base 10) in order to understand its magnitude. For example, if a typical bit pattern is written as 1011001, it could represent many different things (one of 2^7, or 128, different items since the bit pattern is 7 bits wide and there are 128 unique combinations of bit patterns possible). It may also be interpreted as an integer in the binary number system, equivalent to the decimal value 89.
How was this conversion from binary to decimal performed? Conversion is a simple task if certain facts about number systems, in general, are known.
Base 10: consider a quantity in the decimal number system represented by the following string of symbols:
Notation: since it is impossible to represent a subscript within an ASCII text file, the "(10)" above is used to define the number system, or base, in use. If this notation is missing, decimal should be assumed unless the context in which a value is used defines its base as well.123.45 (10)
Decimal utilizes 10 unique symbols "0" through "9" to represent quantities zero through nine. When a value is written using these symbols, each symbol represents some quantity of some "power of 10", with a fraction point used to define the position of the zero power (units). For example, the above set of symbols really represents a quantity evaluated as:
This defines the quantity that the symbol string "123.45" represents in the decimal number system (base 10). That is, one "hundred" (10**2), plus two "tens" (10**1), plus 3 "units" (10**0), plus four "tenths" (10**-1), plus five "hundredths" (10**-2).2 1 0 -1 -2 (1*10 ) + (2*10 ) + (3*10 ) + (4*10 ) + (5*10 )
When we count in decimal the sequence starts at zero and progresses, as, 1, 2, 3, 4, 5, 6, 7, 8, 9. At this point we run out of representative symbols and an additional increment causes a shift to the next power, resulting in the continuation 10, 11, 12, etc. The representation of a quantity in any other number system, or base, is similar, but the number of symbols used in each base is different and the "power" used for evaluation of a quantity is defined by the base in use.
Base 2: uses only two symbols to represent quantities, "0" and "1".
For example, consider a base 2 quantity represented by the symbols
1110.011(2). This would be evaluated by summing "powers of two"
in which the binary (fraction) point defines the zero power, as:
which yields a value of 14.375, in decimal. Thus, 1110.011(2) is equivalent to 14.375(10). Counting in binary produces the sequence 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, etc.3 2 1 0 -1 -2 -3 (1*2 ) + (1*2 ) + (1*2 ) + (0*2 ) + (0*2 ) + (1*2 ) + (1*2 ) or: 8 + 4 + 2 + 0 + 0.0 + 0.25 + 0.125
Base 5: has 5 unique symbols representing quantities of powers: "0"
through "4". Consider the base 5 quantity represented by the symbol string
123.4 (5) evaluated in decimal as:
which is equivalent to the decimal quantity 25 + 10 + 3 + 0.8, or 38.8(10). Counting in base 5 produces the sequence 0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21, 22, etc.2 1 0 -1 (1*5 ) + (2*5 ) + (3*5 ) + (4*5 )
Base 8: or the OCTAL number system, has 8 unique symbols "0"
through "7", that represent quantities of powers. Consider the octal
number 123.4 (8) evaluated in decimal as:
which in decimal is equivalent to the value 64 + 16 + 3 + 0.5 --> 83.5(10). Counting in octal produces the sequence 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, etc.2 1 0 -1 (1*8 ) + (2*8 ) + (3*8 ) + (4*8 )
Base 16: or the HEXADECIMAL system, has 16 symbols representing
quantities of powers, "0" through "9", and "A" through "F" (to represent
the quantities ten to fifteen). Consider the hexadecimal quantity
12.4 (16) evaluated in decimal as:
which is equivalent to the decimal value 16 + 2 + 0.25 --> 18.25(10). Counting in "hex" produces the sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1A, 1B, 1C, 1D, 1E, 1F, 20, 21, 22, etc.1 0 -1 (1*16 ) + (2*16 ) + (4*16 )
In fact, all number systems are similar in that quantities represented by strings of symbols are evaluated in the same manner. To illustrate this similarity and differences between systems, some general observations on number systems can be made:
For bases greater than 10, the number of symbols required exceeds the number of digits normally used to represent quantities. It is usually the case that (upper case) alphabetic characters are used to extend the set of digits such that numeric quantities in bases 11 through 36 can additionally be represented. The character A is always used to represent the quantity 10, B is 11, C is 12, ..., Y is 34, and Z is 35.Base 10 (decimal): 0 1 2 3 4 5 6 7 8 9 Base 2 (binary): 0 1 Base 5: 0 1 2 3 4 Base 8 (octal): 0 1 2 3 4 5 6 7 Base 16 (hexadecimal): 0 1 2 3 4 5 6 7 8 9 A B C D E F
the represented quantity is determined by evaluating the expression (in decimal):... S S S S . S S S ... (B) 1 2 3 4 5 6 7
3 2 1 0 -1 -2 -3 ... (S *B )+(S *B )+(S *B )+(S *B )+(S *B )+(S *B )+(S *B ) ... 1 2 3 4 5 6 7
123.4(5) * 5(10) ===> 123.4(5) * 10(5) ===> 1234.0(5) AC23.F4(16) * 16(10) ===> AC23.F4(16) * 10(16) ===> AC23F.4(16)
123.4(5) / 5(10) ===> 123.4(5) / 10(5) ===> 12.34(5) AC23.F4(16) / 16(10) ===> AC23.F4(16) / 10(16) ===> AC2.3F4(16)
Conversion of a number from one base, or number system, to another base, can at times be difficult, if neither of the bases is base 10. For example, to convert the base 5 number 342.32(5) to hexadecimal, if a direct conversion is attempted, all calculations must be performed in the hexadecimal system. It is easier to first convert the base 5 number into decimal, then convert the decimal value into hexadecimal using a 2-step process. This requires a mechanism whereby a number in any base can be converted to decimal and one whereby any decimal value can be converted to any other system.
Any Base B to DECIMAL: this is relatively simple. All one has to do is sum the symbols multiplied by the powers of the base, as defined in observation 3 above.
DECIMAL to Any Base B: to convert a real value, containing an integer and a fraction part, separated by a fraction point, it is easier to convert the integer and fraction parts separately, as demonstrated below.
INTEGER PART: using what is called the division method, repeatedly divide by B, the value of the target base. The REMAINDER after each division will be an extraction of the number of units of some power in the given base. All remainders are written down starting at the units position beside the fraction point and proceeding to the left defining greater and greater powers of the base.
The first remainder obtained will be the number of units in the original value, the second remainder is the number of the base to the power one, the third is the number of the base to the power two, etc. No remainder will be a quantity that equals or exceeds the base B (due to the nature of the "mod" function), hence every remainder used to represent the number of some power is representable in that base, i.e., a symbol equivalent to the value of any remainder exists in the base B.
For example, to convert the decimal integer 104 to base B=5,
start off by writing down a fraction point as -----------------------.
|
Then start the division procedure by dividing 104 by 5 to |
obtain a result of 20 and a remainder of 4. The 4 is the |
number of base 5 units and the 20 is the number of fives |
in the original quantity. We then write the 4 in the units |
position immediately to the left of the decimal point: |
|
104 / 5 = 20, remainder 4 -------------------------------------. |
| |
Next, we divide 20 by 5 obtaining the integer result 4 v v
and remander 0. The 0 represents the number of fives in 4 0 4 .
the original number and we write it in the next position: ^ ^
| |
20 / 5 = 4, remainder 0 -----------------------------------+-'
|
Finally, dividing 4 by 5 yields result 0 with a remainder |
of 4, the number of twenty-fives in the original number: |
|
4 / 5 = 0, remainder 4 ------------------------------------'
Any division from this point on yields both a result and remainder of zero,
and continuation of the algorithm will result in the writing down of leading
zeroes in the final answer. Consequently, the algorithm may be aborted when
the result becomes zero.
Repeatedly dividing the integer result by 5 serves to extract successive quantities of powers of 5. This works for any target number system if the 5 is changed to the desired target base (B).
FRACTION PART: the inverse of the above, a multiplication method is used to successively multiply the decimal fraction part by the desired base. After each multiplication, the integer part of the result is an extraction of some negative power written starting at the position to the immediate right of the fraction point, with successive integer parts of the result written proceeding to the right. The integer part after the first multiplication is the quantity of the target base to the power negative one, then the next is the number of the base to the power -2, etc. No integer part will be larger than the value of the base B because the fraction part used to obtain each product is always less than 1.0.
For example, to convert the decimal quantity 0.424 to base
B=5, we once again start with a fraction point as -------------.
|
Then we start the algorithm by multiplying 0.424 by 5 v
obtaining the result 2.120. The 2 is the number of fifths . 2 0 3
extracted from the original decimal value, so it is REMOVED ^ ^ ^
from the result and written to the right of the fraction: | | |
| | |
.------------------------------------------------' | |
| | |
0.424 * 5 = 2.120 | |
| |
Next we multiply the REMAINING fraction 0.120 by 5 obtaining | |
0.600. The integer part 0 is an extraction of the number of | |
twenty-fifths so we write it in the next position to right: | |
| |
.--------------------------------------------------' |
| |
0.120 * 5 = 0.600 |
|
Finally, multiplying 0.600 by 5 yields 3.000 with the 3 |
an extraction of the number of 125ths so it is written |
in the next position to the right: |
|
.----------------------------------------------------'
|
0.600 * 5 = 3.000
The remaining fraction is now zero and performing the algorithm further will
produce a result of 0.0 and a sequence of trailing zeros to be written down
in the fraction part of the answer. Note that the fraction becoming zero is
a peculiarity in this example which will not often occur in practice. When
it doesn't occur, the algorithm is aborted when enough significant precision
is obtained in the result, "enough" defined by the reason for or situation
in which the conversion is being performed.
Combining the integer and fraction parts in the two examples above, we can conclude that the decimal real value 104.424 must be equivalent to the base 5 value 404.203. To verify this, simply convert 404.203(5) back to decimal as follows:
To implement the algorithm in a computer program, start with a target base and a real value to convert. Use an integer divide operation to isolate the integer part, then subtract that from the original value to isolate the fraction part. The algorithms may be implemented in any language which supports the usual arithmetic operations for both integers and reals, with use of a "mod" operator or function a convenience for the division method.2 1 0 -1 -2 -3 404.203(5) = 4 * 5 + 0 * 5 + 4 * 5 + 2 * 5 + 0 * 5 + 3 * 5 = 100 + 0 + 4 0.4 + 0.0 + 0.024 = 104.424(10)
The integer part may be conveniently converted and printed using recursion, and the fraction part converted and printed using iteration to a predefined number of fractional places. A C program that implements this conversion algorithm is created in a file named "convert.c" below::
% cat > convert.c
/* Decimal to Any Base Conversion */
#include <stdio.h>
#include <string.h>
extern double atof(); /* this prototype declaration is necessary */
extern int atoi();
char Digit_Symbol (int value)
{ if ( value >= 0 && value <= 9 ) return('0'+value);
else if ( value >= 10 && value <= 35 ) return('A'+value-10);
else return('?');
}
void Convert_Integer(int I, int B)
{ int k, r;
r = I % B;
k = I / B;
if ( k > 0 ) Convert_Integer(k,B);
putc(Digit_Symbol(r),stdout);
}
void Convert_Fraction(double F, int B, int P)
{ int i, k; double t;
for ( i=1; i <= P; i++ )
{ t = F * (double) B;
k = (int) t;
putc(Digit_Symbol(k),stdout);
F = t - (double) k;
}
}
void main(int argc, char *argv[])
{ double value, fraction; int base, integer, precision; char *temp;
if (argc != 3)
{ fprintf(stderr,"%s: bad command line arguments.\n",argv[0]);
exit();
}
base = atoi(argv[2]);
if ( base < 2 || base > 36 )
{ fprintf(stderr,"Bad target base %s.\n",argv[2]);
exit();
}
value = atof(argv[1]);
if ( value <= 0.0 )
{ fprintf(stderr,"Bad or illegal decimal value %s.\n",argv[1]);
exit();
}
integer = value;
fraction = value - integer;
precision = ( 40 - base ) / 2;
putc('\n',stdout);
putc('\t',stdout);
Convert_Integer(integer,base);
putc('.',stdout);
Convert_Fraction(fraction,base,precision);
putc('\n',stdout);
putc('\n',stdout);
}
% gcc -o convert convert.c
The sample executions illustrated below show that the program has been designed
to extract the number to be converted and the target base (B) from the Unix
command line:
% convert 12345.678 16 3039.AD916872B000 % convert 12345.678 36 9IX.OE % convert 12345.678 2 11000000111001.1010110110010001011 %Further examples of manually converting the decimal value 197.561 into its own base (the algorithms should work for that), base 5, binary, octal, and hexadecimal should produce the following results:
The actual conversions are left as an exercise for the reader. Note that in the conversion of the fraction parts for these examples, things do not work out conveniently because the fraction to be multiplied in each step of the multiplication algorithm never becomes zero.197.561(10) --> base 10 (decimal) --> base 5, 1242.240030303... --> base 2 (binary), 11000101.10001111100111011011... --> base 8 (octal), 305.4371666... --> base 16 (hexadecimal), C5.8F9DB...
Conversion Between Powers of 2 Bases
Converting from a nondecimal base to another nondecimal base should be done through decimal as an intermediate base to avoid the necessity of performing arithmetic in a nondecimal base, with one exception. When BOTH bases are a power of two (e.g., 8 and 16, or 4 and 32, etc.) the intermediate base that is more convenient to use is binary. This is because conversions from binary to any "power of 2" base can be performed directly.
For example, conversions between binary and octal can be performed directly because 2 to the power 3 happens to be equivalent to the value 8. Therefore, 3 digits in binary should map directly into a single octal digit, and vice versa. This can be proven with some simple algebra. Consider the binary quantity 110101 and its subsequent conversion to octal. Evaluation in decimal is:
To convert directly from binary to octal, bits are collected in triples starting at the fraction point and proceeding in each direction. For example, to convert the binary value:5 4 3 2 1 0 110101(2) = 1 * 2 + 1 * 2 + 0 * 2 + 1 * 2 + 0 * 2 + 1 * 2 3 3 3 0 0 0 = 4 * 2 + 2 * 2 + 0 * 2 + 4 * 2 + 0 * 2 + 1 * 2 3 0 = (4 + 2 + 0) * 2 + (4 + 0 + 1) * 2 1 0 = 6 * 8 + 5 * 8 = 65(8)
to octal (base 8), binary digits are collected together in groups of three starting at the fraction point and proceeding in each direction, as in:11000101.10001111100111011011
Notice that an extra zero has been appended to each end, which does not alter the numeric value. Using 3 binary digits, there are only 8 (2**3) possible combinations which can occur. Each unique combination converts directly into a unique symbol (quantity) in base 8. These are:011 000 101 . 100 011 111 001 110 110 110
Notice that each 3-digit binary value is equivalent to the single-digit octal value beside it. Now each triple in the binary value to be converted can be replaced by an equivalent octal digit, as:000 ---> 0 010 ---> 2 100 ---> 4 110 ---> 6 001 ---> 1 011 ---> 3 101 ---> 5 111 ---> 7
yielding 305.4371666, in octal (base 8). To convert from binary to octal, the reverse procedure would be performed. That is, every octal digit in an octal value would be replaced by exactly three binary digits using the same transformation table above, but in the opposite direction.3 0 5 . 4 3 7 1 6 6 6
For example, 2353.734 octal is, converting into binary directly by using the table, is 010 011 101 011 . 111 011 100. Removing all leading and trailing zeroes, this is 10011101011.111011100 binary. The fact that these values are equivalent can be verified by converting each value into decimal. This exercise is left for the reader.
Another useful case in which direct conversions may be performed without using decimal as an intermediate system is conversion between binary (base 2) and hexadecimal (base 16), possible because 2 to the power 4 is sixteen. Starting at the fraction point, bits are collected together in groups of 4. For example, to convert the same binary value as we had in the previous octal example of 305.4371666, to hexadecimal, bits are collected as:
There sixteen possible combinations of 4 bits and each unique combination will translate directly into a unique hexadecimal digit, as:1100 0101 . 1000 1111 1001 1101 1011
Now each quadruple is replaced by an appropriate "hex" digit:0000 ---> 0 0100 ---> 4 1000 ---> 8 1100 ---> C 0001 ---> 1 0101 ---> 5 1001 ---> 9 1101 ---> D 0010 ---> 2 0110 ---> 6 1010 ---> A 1110 ---> E 0011 ---> 3 0111 ---> 7 1011 ---> B 1111 ---> F
yielding C5.8F9DB, in hexadecimal (base 16). To convert from "hex" to binary, the reverse procedure would be performed. Each hexadecimal digit would be replaced by exactly 4 binary digits using the above table, then leading and trailing zeroes may be removed.C 5 . 8 F 9 D B
Direct conversion from octal to hexadecimal should not be performed with an expectation of a high degree of reliability. To convert between these two number systems, the intermediate system should be base 2, instead of the decimal system. For example, to convert the octal value 7654.0123 into hex we first convert it into binary as:
then we collect bits in groups of 4:111 110 101 100 . 000 001 010 011
and finally convert this to the hexadecimal value FAC.053. For some other examples, return to the previous conversions from decimal to any base to verify that the hexadecimal value C5.8F9DB is the same as the octal value 305.4371666, by converting hex to octal through the binary equivalent of 11000101.10001111100111011011.1111 1010 1100 . 0000 0101 0011
Notice that many bits of binary precision are required to represent only a few digits of hexadecimal (or octal) precision, so performing the conversion algorithms from decimal to binary or vice versa may be inefficient. It may be easier to convert between decimal and hex or octal more rapidly and more accurately using a calculator for the arithmetic. An better alternative is to purchase a calculator that can perform accurate conversions between any of the 4 most important systems: decimal, binary, octal, and hex.
It is tedious to write quantities in binary. A binary number composed of many bits does not have a large (decimal) numeric value. It is simply more convenient to write numbers in octal or hexadecimal as a representation of binary. If all the information contained within a computer was displayed in binary it would be difficult to read and a lot of paper would have to be used. To overcome this problem of sheer volume, internal computer information is most often displayed using a "hex" or "octal" representation as a replacement for binary, illustrating the same amount of information but with fewer digits generated.
Octal and hexadecimal are used simply because they are more convenient than binary. That is, they are used as a "shorthand" for binary. Once one becomes accustomed to using these bases, conversion to and from binary becomes automatic.
The same principles hold for converting between any two systems when each base is a power of two. Simply, the intermediate base used for conversion should be binary. For example, the base 4 value 3231.312 can be converted into base 32 as follows:
assuming that the digit symbols used in base 32 are the characters '0' to '9' and 'A' to 'V'. Note that if either base is not a power of two, then the intermediate base for conversion should be decimal. For example, if the target base above is 30 and not 32, there no way to collect bits together so that the conversion may be performed directly.3231.312(4) = 11101101.110110(2) = 111 01101 . 11011 0 (2) = 7 D . R 0 (32) = 3D.R(32)