Numeration and Representation of Numbers

To understand numeration systems, it is helpful to examine the decimal (or base 10 ) numeration system. Let´s first review some of the material in Chapter 2, "Metamorphosis of Information" from The Computer Continuum.

Figure 2.1 Figure illustrates the use of several important features of the decimal system.

Figure 2.1 Values for each of the decimal positions.

Notice that the decimal numeration system uses exactly 10 symbols, namely: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. To represent the various numbers, these symbols are placed in certain positions. For example, the 5 in the left most position indicates that there are 5 one-thousands in the number. Each position has a value associated with it, and these values are powers of a number called the base, which in decimal is 10 (e.g., 1000 is 10 to the 3rd power or 10³, and 10³ means 10x10x10; the 3 is called an exponent).

Using this exponent notation, the base 10 number in Figure 2.1 can be written as follows:

Figure 2.2 A table showing how a number can be broken down into parts.

Now that we have reviewed the base 10 numeration system, we can review another base that is less difficult. Rather than give a complete and formal mathematical definition, we will let our intuition guide us.

In the binary (or base 2) system, these two points seem to follow reasonably from our familiar decimal system of numeration:

1. Base 2 uses only two symbols, 0 and 1.

2. The place values of each position are powers of 2.

For example, the base 2 number 10110 can be written out in terms of the very familiar decimal numbers as shown in Figure 2.3:

Place values in Base 10

Figure 2.3 The place values for the binary number 10110.

Because the place values are given in base 10, we can add them to see what this number is in base 10. It´s actually quite deceiving. Suppose you were asked to go to the store and get 10110_two pounds of sugar. Would you need a truck to carry that much sugar? Certainly, if the number were interpreted as base 10, then ten-thousand one-hundred ten pounds of sugar is quite a lot. But it actually represents a relatively small amount in base 2, as we can see in Figure 2.4:

Figure 2.4 Converting 10110 _two to a decimal number.

Another example of a number whose size is equally deceiving is 100110_two. Suppose we consider the same digits as the decimal number 100,110 (or we would say "one hundred thousand, one hundred ten"). In binary, the size of the number is smaller than the same digits considered as decimal. This binary number is converted to decimal as shown below in Figure 2.5. The diagram shows the binary number 100110_two with all of the place values for each position given in the decimal number system that we know so well. When all of the parts are added, the result is a decimal (base 10) equivalent of 100110_two. We are so used to decimal numbers that the binary numbers seem confusing. However, with some study, the binary system seems somewhat simpler. For example, it has far fewer addition and multiplication facts to memorize.

Figure 2.5 Converting 100110_two to a decimal number.

To make sure we know how to obtain the decimal equivalent of a binary number, another example would be helpful. The purpose of this example is to again show how to take a binary number and obtain its decimal equivalent. In this case 1101_two is a smaller number than the previous example. But the principle is the same: find the decimal value for each binary position, and then add up all the decimal parts. The result, illustrated in Figure 2.6, is the same number expressed in decimal (base 10) rather than in binary.

Figure 2.6 Converting 1101_two to base 10 or decimal.

These principles can be carried over to other bases. For example, in base 16 we will have 16 symbols (i.e., 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F), and the place values will be in powers of 16. The letters are necessary because there is no single digit worth 10, 11, 12, 13, 14, or 15, and these are exactly what A,B,C,D,E,F represent. Otherwise, for example, using 13 as a place value would take up two positions in the number and push all the other digits to the left, changing the number. Be sure to note that any number in a base other than 10 will be indicated accordingly in The Computer Continuum book (e.g., 1A7sixteen indicates a base 16 number). Also note that when we add the base 10 pieces, we see that 1A7_sixteen is the same as 423 in decimal (see Figure 2.7).

Figure 2.7 Converting 1A7 _sixteen to base 10 or decimal.

Base 16 is often referred to as hexadecimal. Therefore, rather than using the sixteen for a subscript the word hex is used instead. In the next example (Figure 2.8), we convert a base 16 number 10AF_hex to base 10.

Figure 2.8 Converting 10AF_hex to base 10 or decimal

Note again that each position of the base 16 number has a value. But, unlike base 10, the position values are multiples of 16. For example, the leftmost digit is 1, and its value is 16x16x16 or 4096. Since there is only a 1 in this position, its contribution to the overall answer is 4096. Adding the contributions from all the place values, we see in Figure 2.8 that the total is 4271. Since all these contributions are given in decimal (base 10), then the total, 4271, is also in base 10.

So far, we have dealt only with conversions from any base to base 10. Now let's look at the problem of going in the opposite direction. For example, convert the decimal number 38 to base 2 (see Figure 2. 9).

Figure 2.9 Converting 38 to a binary number.

In this example, we reverse the process already shown. Start with the largest place value that is smaller than 38. This place value is 32. So put the number one in that leftmost position. Now only 6 of the original number 38 remain. This means that there are no sixteens or eights. Exactly one of the fours places fits, leaving 2 to take care of. Finally, this last two can be taken care of by having one of the twos.

Another example of converting from decimal to base 16 is shown below in Figure 2.10.

Figure 2.10 Converting the decimal number 429 to base sixteen.

In this case, suppose we are given 429 and asked to convert it to base 16. We start by finding the largest place value that is smaller than 429. This is the 256s place. We only need one of them, which leaves 173 to take care of. The next step is to determine how many 16s fit into 173. Ten of the 16s will give 160, which are as many 16s as will fit into 173. This takes care of 160 of the 173, leaving 13. Finally, the last 13 that must be accounted for is taken care of by 13 ones.

To get more experience with different numeration systems, let´s try counting in both base 2 (binary) and base 16 (hexadecimal). First, note that in base 10 when we reach 9, we have run out of symbols, so we put a 0 in the ones place and make the tens place one bigger. In another example, what comes after 99 in base 10? We have all memorized that answer and immediately say 100! If we didn't know the answer to this question, we would try to make the ones place one bigger (see Figure 2.11). It is already at its largest value, so make it a zero and then try to make the tens place one bigger. The tens place already has a 9, so make it a 0 and then make the hundreds place one bigger. The result is 100!

Figure 2.11 Counting in decimal, binary and hexadecimal.

Treating fractions isn´t much different than treating whole numbers. Looking back, the example of the number 5207.89 in its expanded form (in Figure 2.2) shows that the 8 represents 8 things each worth one-tenth. Similarly, the 9 represents 9 things each worth one-hundredth. It is also shown that one-hundredth can be written as 10^-2. Since it isn´t appropriate to go into the detailed mathematics of negative exponents, just think of a negative exponent as shorthand for writing the same number in the denominator of a fraction with a positive exponent and a numerator of 1, as shown in the examples below:

Now it´s time to look at some examples of numbers with fractions. The important thing to remember is that the values of all places are written in decimal. This means that if the parts shown in decimal (i.e., base 10) are added , then the result is the number represented in decimal. The following two examples (Figures 2.11 and 2.12) show how to convert a fraction in any base to the equivalent decimal or base 10 form.

Figure 2.11 Converting 11.10 to a decimal fraction.

Figure 2.12 Converting 2F.C8 to a decimal fraction.

One of the major reasons for talking about fractions is to show an important imperfection in the binary representations of decimal numbers. It is quite obvious that numbers containing 0.1 decimal are quite important (e.g., 1/10th, the zero before the decimal point is just for readability). For example, when representing money, 10 cents is commonly written $0.10, or one-tenth of a dollar. The problem occurs in the end result of the conversion from 0.1 decimal to its binary form. Without showing how to do the conversion from decimal fractions to binary fractions, just examine the following result:

0.1 = .000110011001100110011001100110011 . . ._two

The simple 0.1 decimal becomes an infinite repeating binary fraction. How is this possible? It´s just a fact! Just so you don´t think this is unusual, remember that in the decimal world fractions like 1/3 and 2/3 become 0.33333 . . . and 0.66666, which are also infinite repeating fractions.

A programmer not familiar with this problem might write an accounting program for a bank that does millions of arithmetic operations using 0.1 every day. The fact is that every time a 0.1 is added or subtracted in binary, a tiny part of the binary form of 0.1 must be disregarded. For example, using the first 13 bits of the binary form of 0.1 would give 0.0001100110011_two. This is not exactly 0.1, because 0.0000000000000001100110011 . . ._two is being ignored.

This problem with 0.1 is not really insurmountable, it just has to be taken into account. One of the many ways of handling the problem is the BCD (i.e.,Binary Coded Decimal) representation of numbers. The details of this code aren´t of interest here. Let it be sufficient to say that BCD allows exact arithmetic when using 0.1.

You may begin to wonder why we bothered to discuss base 16 (hexadecimal). It´s because the computer can easily convert between its natural base 2 and base 16. To go from base 2 to base 16, just group the binary digits in groups of four starting from the point. Think of each group of four binary digits as a mini problem and convert them to base 10; for any group of four binary digits which is 10 or greater just substitute the appropriate letter (if there aren't enough digits on the end, just add zeros). See Figure 2.13 below:

Figure 2.13 A quick way to convert between binary and hexadecimal numbers.

Notice that a zero was added to the left of the string of binary digits to make a complete set of four digits.

Exercises