E. Number Systems
Objectives
In this appendix, you’ll:
• Learn basic number systems concepts such as base, positional value and symbol value.
• Work with numbers represented in the binary, octal and hexadecimal number systems
• Abbreviate binary numbers as octal numbers or hexadecimal numbers.
• Convert octal numbers and hexadecimal numbers to binary numbers.
• Convert back and forth between decimal numbers and their binary, octal and hexadecimal equivalents.
• Learn binary arithmetic and how negative binary numbers are represented using two’s complement notation.
E.2 Abbreviating Binary Numbers as Octal and Hexadecimal Numbers
E.3 Converting Octal and Hexadecimal Numbers to Binary Numbers
E.4 Converting from Binary, Octal or Hexadecimal to Decimal
E.5 Converting from Decimal to Binary, Octal or Hexadecimal
E.6 Negative Binary Numbers: Two’s Complement Notation
Summary | Self-Review Exercises | Answers to Self-Review Exercises | Exercises
E.1. Introduction
In this appendix, we introduce the key number systems that JavaScript programmers use, especially when they are working on software projects that require close interaction with “machine-level” hardware. Projects like this include operating systems, computer networking software, compilers, database systems and applications requiring high performance.
When we write an integer such as 227 or –63 in a JavaScript program, the number is assumed to be in the decimal (base 10) number system. The digits in the decimal number system are 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. The lowest digit is 0 and the highest digit is 9—one less than the base of 10. Internally, computers use the binary (base 2) number system. The binary number system has only two digits, namely 0 and 1. Its lowest digit is 0 and its highest digit is 1—one less than the base of 2.
As we will see, binary numbers tend to be much longer than their decimal equivalents. Programmers who work in assembly languages that enable them to reach down to the “machine level” find it cumbersome to work with binary numbers. So two other number systems—the octal number system (base 8) and the hexadecimal number system (base 16)—are popular, primarily because they can easily be converted to and from binary (as we will see later) and represent these numbers in fewer digits.
In the octal number system, the digits range from 0 to 7. Because both the binary number system and the octal number system have fewer digits than the decimal number system, their digits are the same as the corresponding digits in decimal.
The hexadecimal number system poses a problem because it requires sixteen digits—a lowest digit of 0 and a highest digit with a value equivalent to decimal 15 (one less than the base of 16). By convention, we use the letters A through F to represent the hexadecimal digits corresponding to decimal values 10 through 15. Thus, in hexadecimal we can have numbers like 876 consisting solely of decimal-like digits, numbers like 8A55F consisting of digits and letters, and numbers like FFE consisting solely of letters. Occasionally, a hexadecimal number spells a common word such as FACE or FEED—this can appear strange to programmers accustomed to working with decimal numbers.
Each of these number systems uses positional notation—each position in which a digit is written has a different positional value. For example, in the decimal number 937 (the 9, the 3, and the 7 are referred to as symbol values), we say that the 7 is written in the ones position, the 3 is written in the tens position, and the 9 is written in the hundreds position. Notice that each of these positions is a power of the base (base 10), and that these powers begin at 0 and increase by 1 as we move left in the number. Figures E.1–E.3 compare the binary, octal, decimal and hexadecimal number systems.
Fig. E.1. Digits of the binary, octal, decimal and hexadecimal number systems.
Fig. E.2. Comparing the binary, octal, decimal and hexadecimal number systems.
Fig. E.3. Positional values in the decimal number system.
For longer decimal numbers, the next positions to the left would be the thousands position (10 to the 3rd power), the ten-thousands position (10 to the 4th power), the hundred-thousands position (10 to the 5th power), the millions position (10 to the 6th power), the ten-millions position (10 to the 7th power) and so on.
In the binary number 101, we say that the rightmost 1 is written in the ones position, the 0 is written in the twos position and the leftmost 1 is written in the fours position. Notice that each of these positions is a power of the base (base 2), and that these powers begin at 0 and increase by 1 as we move left in the number (Fig. E.4).
Fig. E.4. Positional values in the binary number system.
For longer binary numbers, the next positions to the left would be the eights position (2 to the 3rd power), the sixteens position (2 to the 4th power), the thirty-twos position (2 to the 5th power), the sixty-fours position (2 to the 6th power) and so on.
In the octal number 425, we say that the 5 is written in the ones position, the 2 is written in the eights position, and the 4 is written in the sixty-fours position. Notice that each of these positions is a power of the base (base 8), and that these powers begin at 0 and increase by 1 as we move left in the number (Fig. E.5).
Fig. E.5. Positional values in the octal number system.
For longer octal numbers, the next positions to the left would be the five-hundred-and-twelves position (8 to the 3rd power), the four-thousand-and-ninety-sixes position (8 to the 4th power), the thirty-two-thousand-seven-hundred-and-sixty eights position (8 to the 5th power) and so on.
In the hexadecimal number 3DA, we say that the A is written in the ones position, the D is written in the sixteens position and the 3 is written in the two-hundred-and-fifty-sixes position. Notice that each of these positions is a power of the base (base 16), and that these powers begin at 0 and increase by 1 as we move left in the number (Fig. E.6).
Fig. E.6. Positional values in the hexadecimal number system.
For longer hexadecimal numbers, the next positions to the left would be the four-thousand-and-ninety-sixes position (16 to the 3rd power), the sixty-five-thousand-five-hundred-and-thirty-sixes position (16 to the 4th power) and so on.
E.2. Abbreviating Binary Numbers as Octal and Hexadecimal Numbers
The main use for octal and hexadecimal numbers in computing is for abbreviating lengthy binary representations. Figure E.7 highlights the fact that lengthy binary numbers can be expressed concisely in number systems with bases higher than two.
Fig. E.7. Decimal, binary, octal and hexadecimal equivalents.
A particularly important relationship that both the octal number system and the hexadecimal number system have to the binary system is that the bases of octal and hexadecimal (8 and 16, respectively) are powers of the base of the binary number system (base 2). Consider the following 12-digit binary number and its octal and hexadecimal equivalents. See if you can determine how this relationship makes it convenient to abbreviate binary numbers in octal or hexadecimal. The answer follows the numbers.
To see how the binary number converts easily to octal, simply break the 12-digit binary number into groups of three consecutive bits each (note that 8 = 23), and write those groups over the corresponding digits of the octal number as follows:
100 011 010 001
4 3 2 1
Notice that the octal digit you have written under each group of three bits corresponds precisely to the octal equivalent of that 3-digit binary number as shown in Fig. E.7.
The same kind of relationship may be observed in converting numbers from binary to hexadecimal. In particular, break the 12-digit binary number into groups of four consecutive bits each (note that 16 = 24) and write those groups over the corresponding digits of the hexadecimal number as follows:
1000 1101 0001
8 D 1
Notice that the hexadecimal digit you wrote under each group of four bits corresponds precisely to the hexadecimal equivalent of that 4-digit binary number as shown in Fig. E.7.
E.3. Converting Octal and Hexadecimal Numbers to Binary Numbers
In the previous section, we saw how to convert binary numbers to their octal and hexadecimal equivalents by forming groups of binary digits and simply rewriting these groups as their equivalent octal digit values or hexadecimal digit values. This process may be used in reverse to produce the binary equivalent of a given octal or hexadecimal number.
For example, the octal number 653 is converted to binary simply by writing the 6 as its 3-digit binary equivalent 110, the 5 as its 3-digit binary equivalent 101 and the 3 as its 3-digit binary equivalent 011 to form the 9-digit binary number 110101011.
The hexadecimal number FAD5 is converted to binary simply by writing the F as its 4-digit binary equivalent 1111, the A as its 4-digit binary equivalent 1010, the D as its 4-digit binary equivalent 1101 and the 5 as its 4-digit binary equivalent 0101 to form the 16-digit 1111101011010101.
E.4. Converting from Binary, Octal or Hexadecimal to Decimal
Because we are accustomed to working in decimal, it is often convenient to convert a binary, octal or hexadecimal number to decimal to get a sense of what the number is “really” worth. Our diagrams in Section E.1 express the positional values in decimal. To convert a number to decimal from another base, multiply the decimal equivalent of each digit by its positional value, and sum these products. For example, the binary number 110101 is converted to decimal 53 as shown in Fig. E.8.
Fig. E.8. Converting a binary number to decimal.
To convert octal 7614 to decimal 3980, we use the same technique, this time using appropriate octal positional values as shown in Fig. E.9.
Fig. E.9. Converting an octal number to decimal.
To convert hexadecimal AD3B to decimal 44347, we use the same technique, this time using appropriate hexadecimal positional values as shown in Fig. E.10.
Fig. E.10. Converting a hexadecimal number to decimal.
E.5. Converting from Decimal to Binary, Octal or Hexadecimal
The conversions of the previous section follow naturally from the positional notation conventions. Converting from decimal to binary, octal or hexadecimal also follows these conventions.
Suppose we wish to convert decimal 57 to binary. We begin by writing the positional values of the columns right to left until we reach a column whose positional value is greater than the decimal number. We do not need that column, so we discard it. Thus, we first write:
Then we discard the column with positional value 64 leaving:
Next we work from the leftmost column to the right. We divide 32 into 57 and observe that there is one 32 in 57 with a remainder of 25, so we write 1 in the 32 column. We divide 16 into 25 and observe that there is one 16 in 25 with a remainder of 9 and write 1 in the 16 column. We divide 8 into 9 and observe that there is one 8 in 9 with a remainder of 1. The next two columns each produce quotients of zero when their positional values are divided into 1 so we write 0s in the 4 and 2 columns. Finally, 1 into 1 is 1 so we write 1 in the 1 column. This yields:
and thus decimal 57 is equivalent to binary 111001.
To convert decimal 103 to octal, we begin by writing the positional values of the columns until we reach a column whose positional value is greater than the decimal number. We do not need that column, so we discard it. Thus, we first write:
Then we discard the column with positional value 512, yielding:
Next we work from the leftmost column to the right. We divide 64 into 103 and observe that there is one 64 in 103 with a remainder of 39, so we write 1 in the 64 column. We divide 8 into 39 and observe that there are four 8s in 39 with a remainder of 7 and write 4 in the 8 column. Finally, we divide 1 into 7 and observe that there are seven 1s in 7 with no remainder so we write 7 in the 1 column. This yields:
and thus decimal 103 is equivalent to octal 147.
To convert decimal 375 to hexadecimal, we begin by writing the positional values of the columns until we reach a column whose positional value is greater than the decimal number. We do not need that column, so we discard it. Thus, we first write:
Then we discard the column with positional value 4096, yielding:
Next we work from the leftmost column to the right. We divide 256 into 375 and observe that there is one 256 in 375 with a remainder of 119, so we write 1 in the 256 column. We divide 16 into 119 and observe that there are seven 16s in 119 with a remainder of 7 and write 7 in the 16 column. Finally, we divide 1 into 7 and observe that there are seven 1s in 7 with no remainder so we write 7 in the 1 column. This yields:
and thus decimal 375 is equivalent to hexadecimal 177.
E.6. Negative Binary Numbers: Two’s Complement Notation
The discussion in this appendix has been focussed on positive numbers. In this section, we explain how computers represent negative numbers using two’s complement notation. First we explain how the two’s complement of a binary number is formed, and then we show why it represents the negative value of the given binary number.
Consider a machine with 32-bit integers. Suppose
var value = 13;
The 32-bit representation of value is
00000000 00000000 00000000 00001101
To form the negative of value we first form its one’s complement by applying JavaScript’s bitwise complement operator (~):
onesComplementOfValue = ~value;
Internally, ~value is now value with each of its bits reversed—ones become zeros and zeros become ones as follows:
value:
00000000 00000000 00000000 00001101
~value (i.e., value's ones complement):
11111111 11111111 11111111 11110010
To form the two’s complement of value we simply add 1 to value’s one’s complement. Thus
Two's complement of value:
11111111 11111111 11111111 11110011
Now if this is in fact equal to –13, we should be able to add it to binary 13 and obtain a result of 0. Let us try this:
00000000 00000000 00000000 00001101
+11111111 11111111 11111111 11110011
------------------------------------
00000000 00000000 00000000 00000000
The carry bit coming out of the leftmost column is ignored (because it is outside the range of our 32-bit integer), so we indeed get zero as a result. If we add the one’s complement of a number to the original number, the result would be all 1s. The key to getting a result of all zeros is that the twos complement is 1 more than the one’s complement. The addition of 1 causes each column to add to 0 with a carry of 1. The carry keeps moving leftward until it is discarded from the leftmost bit, and hence the resulting number is all zeros.
Computers actually perform a subtraction such as
x = a - value;
by adding the two’s complement of value to a as follows:
x = a + (~value + 1);
Suppose a is 27 and value is 13 as before. If the two’s complement of value is actually the negative of value, then adding the two’s complement of value to a should produce the result 14. Let us try this:
a (i.e., 27) 00000000 00000000 00000000 00011011
+(~value + 1) +11111111 11111111 11111111 11110011
------------------------------------
00000000 00000000 00000000 00001110
which is indeed equal to 14.
Summary
Section E.1 Introduction
• When we write an integer such as 19 or 227 or –63 in a JavaScript program, the number is automatically assumed to be in the decimal (base 10) number system. The digits in the decimal number system are 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The lowest digit is 0 and the highest digit is 9—one less than the base of 10.
• Internally, computers use the binary (base 2) number system. The binary number system has only two digits, namely 0 and 1. Its lowest digit is 0 and its highest digit is 1—one less than the base of 2.
• The octal number system (base 8) and the hexadecimal number system (base 16) are popular primarily because they can easily be converted to and from binary and represent these numbers in fewer digits.
• The digits of the octal number system range from 0 to 7.
• The hexadecimal number system poses a problem because it requires sixteen digits—a lowest digit of 0 and a highest digit with a value equivalent to decimal 15 (one less than the base of 16). By convention, we use the letters A through F to represent the hexadecimal digits corresponding to decimal values 10 through 15.
• Each number system uses positional notation—each position in which a digit is written has a different positional value.
Section E.2 Abbreviating Binary Numbers as Octal and Hexadecimal Numbers
• A particularly important relationship that both the octal number system and the hexadecimal number system have to the binary system is that the bases of octal and hexadecimal (8 and 16 respectively) are powers of the base of the binary number system (base 2).
Section E.3 Converting Octal and Hexadecimal Numbers to Binary Numbers
• To convert an octal number to a binary number, simply replace each octal digit with its three-digit binary equivalent.
• To convert a hexadecimal number to a binary number, simply replace each hexadecimal digit with its four-digit binary equivalent.
Section E.4 Converting from Binary, Octal or Hexadecimal to Decimal
• Because we are accustomed to working in decimal, it is convenient to convert a binary, octal or hexadecimal number to decimal to get a sense of the number’s “real” worth.
• To convert a number to decimal from another base, multiply the decimal equivalent of each digit by its positional value, and sum these products.
Section E.5 Converting from Decimal to Binary, Octal or Hexadecimal
• To convert a number from decimal to another base, write out the base’s positional values up to the largest one that is not greater than the number. Then, starting with the leftmost position, write down how many times the positional value can fit into the number, then repeat the process with the remainder of the number in the next position to the right until you’re left with no remainder.
Section E.6 Negative Binary Numbers: Two’s Complement Notation
• Computers represent negative numbers using two’s complement notation.
• To form the negative of a value in binary, first form its one’s complement by applying JavaScript’s bitwise complement operator (~). This reverses the bits of the value. To form the two’s complement of a value, simply add one to the value’s one’s complement.
Self-Review Exercises
E.1 The bases of the decimal, binary, octal, and hexadecimal number systems are ________, ________, ________ and ________, respectively.
E.2 In general, the decimal, octal and hexadecimal representations of a given binary number contain (more/fewer) digits than the binary number contains.
E.3 (True/False) A popular reason for using the decimal number system is that it forms a convenient notation for abbreviating binary numbers simply by substituting one decimal digit per group of four binary bits.
E.4 The (octal / hexadecimal / decimal) representation of a large binary value is the most concise (of the given alternatives).
E.5 (True/False) The highest digit in any base is one more than the base.
E.6 (True/False) The lowest digit in any base is one less than the base.
E.7 The positional value of the rightmost digit of any number in either binary, octal, decimal or hexadecimal is always ________.
E.8 The positional value of the digit to the left of the rightmost digit of any number in binary, octal, decimal or hexadecimal is always equal to ________.
E.9 Fill in the missing values in this chart of positional values for the rightmost four positions in each of the indicated number systems:
E.10 Convert binary 110101011000 to octal and to hexadecimal.
E.11 Convert hexadecimal FACE to binary.
E.12 Convert octal 7316 to binary.
E.13 Convert hexadecimal 4FEC to octal. [Hint: First convert 4FEC to binary then convert that binary number to octal.]
E.14 Convert binary 1101110 to decimal.
E.15 Convert octal 317 to decimal.
E.16 Convert hexadecimal EFD4 to decimal.
E.17 Convert decimal 177 to binary, to octal and to hexadecimal.
E.18 Show the binary representation of decimal 417. Then show the one’s complement of 417 and the two’s complement of 417.
E.19 What is the result when a number and its two’s complement are added to each other?
Answers to Self-Review Exercises
E.1 10, 2, 8, 16.
E.2 Fewer.
E.3 False.
E.4 Hexadecimal.
E.5 False. The highest digit in any base is one less than the base.
E.6 False. The lowest digit in any base is zero.
E.7 1 (the base raised to the zero power).
E.8 The base of the number system.
E.9 Fill in the missing values in this chart of positional values for the rightmost four positions in each of the indicated number systems:
E.10 Octal 6530; Hexadecimal D58.
E.11 Binary 1111 1010 1100 1110.
E.12 Binary 111 011 001 110.
E.13 Binary 0 100 111 111 101 100; Octal 47754.
E.14 Decimal 2+4+8+32+64=110.
E.15 Decimal 7+1*8+3*64=7+8+192=207.
E.16 Decimal 4+13*16+15*256+14*4096=61396.
E.17 Decimal 177 to binary:
256 128 64 32 16 8 4 2 1
128 64 32 16 8 4 2 1
(1*128)+(0*64)+(1*32)+(1*16)+(0*8)+(0*4)+(0*2)+(1*1)
10110001
to octal:
512 64 8 1
64 8 1
(2*64)+(6*8)+(1*1)
261
256 16 1
16 1
(11*16)+(1*1)
(B*16)+(1*1)
B1
E.18 Binary:
512 256 128 64 32 16 8 4 2 1
256 128 64 32 16 8 4 2 1
(1*256)+(1*128)+(0*64)+(1*32)+(0*16)+(0*8)+(0*4)+(0*2)+
(1*1)
110100001
One’s complement: 001011110
Two’s complement: 001011111
Check: Original binary number + its two’s complement
110100001
+001011111
----------
000000000
E.19 Zero.
Exercises
E.20 Some people argue that many of our calculations would be easier in the base 12 number system because 12 is divisible by so many more numbers than 10 (for base 10). What is the lowest digit in base 12? What might the highest symbol for the digit in base 12 be? What are the positional values of the rightmost four positions of any number in the base 12 number system?
E.21 How is the highest symbol value in the number systems we discussed related to the positional value of the first digit to the left of the rightmost digit of any number in these number systems?
E.22 Complete the following chart of positional values for the rightmost four positions in each of the indicated number systems:
E.23 Convert binary 100101111010 to octal and to hexadecimal.
E.24 Convert hexadecimal 3A7D to binary.
E.25 Convert hexadecimal 765F to octal. [Hint: First convert 765F to binary, then convert that binary number to octal.]
E.26 Convert binary 1011110 to decimal.
E.27 Convert octal 426 to decimal.
E.28 Convert hexadecimal FFFF to decimal.
E.29 Convert decimal 299 to binary, to octal, and to hexadecimal.
E.30 Show the binary representation of decimal 779. Then show the one’s complement of 779, and the two’s complement of 779.
E.31 What is the result when the two’s complement of a number is added to itself?
E.32 Show the two’s complement of integer value –1 on a machine with 32-bit integers.