Tuesday, February 24, 2009
NUMBER SYSTEMS
The Decimal System
In everyday life we use a system based on decimal digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) to represent
numbers and refer to the system as the decimal system. Consider what the number 83 means. It
means eight tens plus three:
83 = (8 ´ 10) + 3
The number 4728 means four thousands, seven hundreds, two tens, plus eight:
4728 = (4 ´ 1000) + (7 ´ 100) + (2 ´ 10) + 8
The decimal system is said to have a base, or radix, of 10. This means that each digit in the
number is multiplied by 10 raised to a power corresponding to that digit’s position:
83 = (8 ´ 101) + (3 ´ 100)
4728 = (4 ´ 103) + (7 ´ 102) + (2 ´ 101) + (8 ´ 100)
The same principle holds for decimal fractions but negative powers of 10 are used. Thus,
the decimal fraction 0.256 stands for 2 tenths plus 5 hundredths plus 6 thousandths:
0.256 = (2 ´ 10–1) + (5 ´ 10–2) + (6 ´ 10–3)
A number with both an integer and fractional part has digits raised to both positive and
negative powers of 10:
472. 256 = (4 ´ 102) + (7 ´ 101) + (2 ´ 100) + (2 ´ 10–1) + (5 ´ 10–2) + (6 ´ 10–3)
In general, for the decimal representation of X = { . . . d2d1d0.d–1d–2d–3 . . .}, the value of X is
X = di ´10i
i å
-3-
The Binary System
In the decimal system, 10 different digits are used to represent numbers with a base of 10. In the
binary system, we have only two digits, 1 and 0. Thus, numbers in the binary system are
represented to the base 2.
To avoid confusion, we will sometimes put a subscript on a number to indicate its base. For
example, 8310 and 472810 are numbers represented in decimal notation, or more briefly, decimal
numbers. The digits 1 and 0 in binary notation have the same meaning as in decimal notation:
02 = 010
12 = 110
To represent larger numbers, as with decimal notation, each digit in a binary number has a value
depending on its position:
102 = (1 ´ 21) + (0 ´ 20) = 210
112 = (1 ´ 21) + (1 ´ 20) = 310
1002 = (1 ´ 22) + (0 ´ 21) + (0 ´ 20) = 410
and so on. Again, fractional values are represented with negative powers of the radix:
1001.101 = 23 + 20 + 2–1 + 2–3 = 9.62510
In general, for the binary representation of Y = { . . . b2b1b0.b–1b–2b–3 . . .}, the value of Y is
Y = bi ´ 2i
i å
Converting between Binary and Decimal
It is a simple matter to convert a number from binary notation to decimal notation. In fact, we
showed several examples in the previous subsection. All that is required is to multiply each
binary digit by the appropriate power of 2 and add the results.
To convert from decimal to binary, the integer and fractional parts are handled separately.
-4-
Integers
For the integer part, recall that in binary notation, an integer represented by
bm–1bm–2…b2b1b0 bi = 0 or 1
has the value
(bm–1 ´ 2m–1) +(bm–2 ´ 2m–2) + … + (b1 ´ 21) + b0
Suppose it is required to convert a decimal integer N into binary form. If we divide N by 2,
in the decimal system, and obtain a quotient N1 and a remainder R0, we may write
N = 2 ´ N1 + R0 R0 = 0 or 1
Next, we divide the quotient N1 by 2. Assume that the new quotient is N2 and the new remainder
R1. Then
N1 = 2 ´ N2 + R1 R1 = 0 or 1
so that
N = 2(2N2 + R1) + R0 = (N2 ´ 22) + (R1 ´ 21) + R0
If next
N2 = 2N3 + R2
we have
N = (N3 ´ 23) + (R2 ´ 22) + (R1 ´ 21) + R0
Because N > N1 > N2 . . ., continuing this sequence will eventually produce a quotient Nm–1 = 1
(except for the decimal integers 0 and 1, whose binary equivalents are 0 and 1, respectively) and
a remainder Rm–2, which is 0 or 1. Then
N = (1 ´ 2m–1) + (Rm–2 ´ 2m–2) + . . . + (R2 ´ 22) + (R1 ´ 21) + R0
-5-
which is the binary form of N. Hence, we convert from base 10 to base 2 by repeated divisions
by 2. The remainders and the final quotient, 1, give us, in order of increasing significance, the
binary digits of N. Figure 1 shows two examples.
Fractions
For the fractional part, recall that in binary notation, a number with a value between 0 and 1
is represented by
0.b–1b–2b–3… bi = 0 or 1
has the value
(b–1 ´ 2–1) + (b–2 ´ 2–2) + (b–3 ´ 2–3) …
This can be rewritten as
2–1 ´ (b–1 + 2–1 ´ (b–2 + 2–1 ´ (b–3 + …
This expression suggests a technique for conversion. Suppose we want to convert the
number F (0 < F < 1) from decimal to binary notation. We know that F can be expressed in the
form
F = 2–1 ´ (b–1 + 2–1 ´ (b–2 + 2–1 ´ (b–3 + …
If we multiply F by 2, we obtain:
2 ´ F = b–1 + 2–1 ´ (b–2 + 2–1 ´ (b–3 + …
From this equation, we see that the integer part of (2 ´ F), which must be either 0 or 1
because 0 < F < 1, is simply b–1. So we can say (2 ´ F) = b–1 + F1, where 0 < F1 < 1 and where
F1 = 2–1 ´ (b–2 + 2–1 ´ (b–3 + 2–1 ´ (b–4 + …
To find b–2, we repeat the process. Therefore, the conversion algorithm involves repeated
multiplication by 2. At each step, the fractional part of the number from the previous step is
multiplied by 2. The digit to the left of the decimal point in the product will be 0 or 1 and
-6-
contributes to the binary representation, starting with the most significant digit. The fractional
part of the product is used as the multiplicand in the next step. Figure 2 shows two examples.
This process is not necessarily exact; that is, a decimal fraction with a finite number of
digits may require a binary fraction with an infinite number of digits. In such cases, the
conversion algorithm is usually halted after a prespecified number of steps, depending on the
desired accuracy.
Hexadecimal Notation
Because of the inherent binary nature of digital computer components, all forms of data within
computers are represented by various binary codes. However, no matter how convenient the
binary system is for computers, it is exceedingly cumbersome for human beings. Consequently,
most computer professionals who must spend time working with the actual raw data in the
computer prefer a more compact notation.
What notation to use? One possibility is the decimal notation. This is certainly more
compact than binary notation, but it is awkward because of the tediousness of converting
between base 2 and base 10.
Instead, a notation known as hexadecimal has been adopted. Binary digits are grouped into
sets of four. Each possible combination of four binary digits is given a symbol, as follows:
0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
1000 = 8
1001 = 9
1010 = A
1011 = B
1100 = C
1101 = D
1110 = E
1111 = F
Because 16 symbols are used, the notation is called hexadecimal, and the 16 symbols are the
hexadecimal digits.
A sequence of hexadecimal digits can be thought of as representing an integer in base 16.
Thus,
2C16 = (216 ´ 161) + (C16 ´ 160)
= (210 ´ 161) + (1210 ´ 160) = 44
-7-
Hexadecimal notation is used not only for representing integers. It is also used as a concise
notation for representing any sequence of binary digits, whether they represent text, numbers, or
some other type of data. The reasons for using hexadecimal notation are
1. It is more compact than binary notation.
2. In most computers, binary data occupy some multiple of 4 bits, and hence some multiple
of a single hexadecimal digit.
3. It is extremely easy to convert between binary and hexadecimal.
As an example of the last point, consider the binary string 110111100001. This is
equivalent to
1101 1110 0001 = DE116
D E 1
This process is performed so naturally that an experienced programmer can mentally
convert visual representations of binary data to their hexadecimal equivalent without written
effort
Quotient
Figure 1 Examples of Converting from Decimal
Notation to Binary Notation for Integers
= 5 1
Remainder
11
2
5 = 2 1
2
2 = 1 0
2
= 0 1
10112 = 1110
(a) 1110
1
2
Quotient
= 5 0
Remainder
10
2
5 = 2 1
2
2 = 1 0
2
= 0 1
101012 = 2110
(b) 2110
1
2
21 = 10 1
2
Product
Figure 2 Examples of Converting from Decimal
Notation to Binary Notation for Fractions
0.81 ´ 2 = 1.62 1
Integer Part
0.62 ´ 2 = 1.24 1
0.24 ´ 2 = 0.48 0
0.48 ´ 2 = 0.96
0.96 ´ 2 = 1.92
0.92 ´ 2 = 1.84
0
1
1
0.1100112
(a) 0.8110 = 0.110112 (approximately)
Product
0.25 ´ 2 = 0.5 0
Integer Part
0.5 ´ 2 = 1.0 1
0.012
(B) 0.2510 = 0.012 (exactly)
In everyday life we use a system based on decimal digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) to represent
numbers and refer to the system as the decimal system. Consider what the number 83 means. It
means eight tens plus three:
83 = (8 ´ 10) + 3
The number 4728 means four thousands, seven hundreds, two tens, plus eight:
4728 = (4 ´ 1000) + (7 ´ 100) + (2 ´ 10) + 8
The decimal system is said to have a base, or radix, of 10. This means that each digit in the
number is multiplied by 10 raised to a power corresponding to that digit’s position:
83 = (8 ´ 101) + (3 ´ 100)
4728 = (4 ´ 103) + (7 ´ 102) + (2 ´ 101) + (8 ´ 100)
The same principle holds for decimal fractions but negative powers of 10 are used. Thus,
the decimal fraction 0.256 stands for 2 tenths plus 5 hundredths plus 6 thousandths:
0.256 = (2 ´ 10–1) + (5 ´ 10–2) + (6 ´ 10–3)
A number with both an integer and fractional part has digits raised to both positive and
negative powers of 10:
472. 256 = (4 ´ 102) + (7 ´ 101) + (2 ´ 100) + (2 ´ 10–1) + (5 ´ 10–2) + (6 ´ 10–3)
In general, for the decimal representation of X = { . . . d2d1d0.d–1d–2d–3 . . .}, the value of X is
X = di ´10i
i å
-3-
The Binary System
In the decimal system, 10 different digits are used to represent numbers with a base of 10. In the
binary system, we have only two digits, 1 and 0. Thus, numbers in the binary system are
represented to the base 2.
To avoid confusion, we will sometimes put a subscript on a number to indicate its base. For
example, 8310 and 472810 are numbers represented in decimal notation, or more briefly, decimal
numbers. The digits 1 and 0 in binary notation have the same meaning as in decimal notation:
02 = 010
12 = 110
To represent larger numbers, as with decimal notation, each digit in a binary number has a value
depending on its position:
102 = (1 ´ 21) + (0 ´ 20) = 210
112 = (1 ´ 21) + (1 ´ 20) = 310
1002 = (1 ´ 22) + (0 ´ 21) + (0 ´ 20) = 410
and so on. Again, fractional values are represented with negative powers of the radix:
1001.101 = 23 + 20 + 2–1 + 2–3 = 9.62510
In general, for the binary representation of Y = { . . . b2b1b0.b–1b–2b–3 . . .}, the value of Y is
Y = bi ´ 2i
i å
Converting between Binary and Decimal
It is a simple matter to convert a number from binary notation to decimal notation. In fact, we
showed several examples in the previous subsection. All that is required is to multiply each
binary digit by the appropriate power of 2 and add the results.
To convert from decimal to binary, the integer and fractional parts are handled separately.
-4-
Integers
For the integer part, recall that in binary notation, an integer represented by
bm–1bm–2…b2b1b0 bi = 0 or 1
has the value
(bm–1 ´ 2m–1) +(bm–2 ´ 2m–2) + … + (b1 ´ 21) + b0
Suppose it is required to convert a decimal integer N into binary form. If we divide N by 2,
in the decimal system, and obtain a quotient N1 and a remainder R0, we may write
N = 2 ´ N1 + R0 R0 = 0 or 1
Next, we divide the quotient N1 by 2. Assume that the new quotient is N2 and the new remainder
R1. Then
N1 = 2 ´ N2 + R1 R1 = 0 or 1
so that
N = 2(2N2 + R1) + R0 = (N2 ´ 22) + (R1 ´ 21) + R0
If next
N2 = 2N3 + R2
we have
N = (N3 ´ 23) + (R2 ´ 22) + (R1 ´ 21) + R0
Because N > N1 > N2 . . ., continuing this sequence will eventually produce a quotient Nm–1 = 1
(except for the decimal integers 0 and 1, whose binary equivalents are 0 and 1, respectively) and
a remainder Rm–2, which is 0 or 1. Then
N = (1 ´ 2m–1) + (Rm–2 ´ 2m–2) + . . . + (R2 ´ 22) + (R1 ´ 21) + R0
-5-
which is the binary form of N. Hence, we convert from base 10 to base 2 by repeated divisions
by 2. The remainders and the final quotient, 1, give us, in order of increasing significance, the
binary digits of N. Figure 1 shows two examples.
Fractions
For the fractional part, recall that in binary notation, a number with a value between 0 and 1
is represented by
0.b–1b–2b–3… bi = 0 or 1
has the value
(b–1 ´ 2–1) + (b–2 ´ 2–2) + (b–3 ´ 2–3) …
This can be rewritten as
2–1 ´ (b–1 + 2–1 ´ (b–2 + 2–1 ´ (b–3 + …
This expression suggests a technique for conversion. Suppose we want to convert the
number F (0 < F < 1) from decimal to binary notation. We know that F can be expressed in the
form
F = 2–1 ´ (b–1 + 2–1 ´ (b–2 + 2–1 ´ (b–3 + …
If we multiply F by 2, we obtain:
2 ´ F = b–1 + 2–1 ´ (b–2 + 2–1 ´ (b–3 + …
From this equation, we see that the integer part of (2 ´ F), which must be either 0 or 1
because 0 < F < 1, is simply b–1. So we can say (2 ´ F) = b–1 + F1, where 0 < F1 < 1 and where
F1 = 2–1 ´ (b–2 + 2–1 ´ (b–3 + 2–1 ´ (b–4 + …
To find b–2, we repeat the process. Therefore, the conversion algorithm involves repeated
multiplication by 2. At each step, the fractional part of the number from the previous step is
multiplied by 2. The digit to the left of the decimal point in the product will be 0 or 1 and
-6-
contributes to the binary representation, starting with the most significant digit. The fractional
part of the product is used as the multiplicand in the next step. Figure 2 shows two examples.
This process is not necessarily exact; that is, a decimal fraction with a finite number of
digits may require a binary fraction with an infinite number of digits. In such cases, the
conversion algorithm is usually halted after a prespecified number of steps, depending on the
desired accuracy.
Hexadecimal Notation
Because of the inherent binary nature of digital computer components, all forms of data within
computers are represented by various binary codes. However, no matter how convenient the
binary system is for computers, it is exceedingly cumbersome for human beings. Consequently,
most computer professionals who must spend time working with the actual raw data in the
computer prefer a more compact notation.
What notation to use? One possibility is the decimal notation. This is certainly more
compact than binary notation, but it is awkward because of the tediousness of converting
between base 2 and base 10.
Instead, a notation known as hexadecimal has been adopted. Binary digits are grouped into
sets of four. Each possible combination of four binary digits is given a symbol, as follows:
0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
1000 = 8
1001 = 9
1010 = A
1011 = B
1100 = C
1101 = D
1110 = E
1111 = F
Because 16 symbols are used, the notation is called hexadecimal, and the 16 symbols are the
hexadecimal digits.
A sequence of hexadecimal digits can be thought of as representing an integer in base 16.
Thus,
2C16 = (216 ´ 161) + (C16 ´ 160)
= (210 ´ 161) + (1210 ´ 160) = 44
-7-
Hexadecimal notation is used not only for representing integers. It is also used as a concise
notation for representing any sequence of binary digits, whether they represent text, numbers, or
some other type of data. The reasons for using hexadecimal notation are
1. It is more compact than binary notation.
2. In most computers, binary data occupy some multiple of 4 bits, and hence some multiple
of a single hexadecimal digit.
3. It is extremely easy to convert between binary and hexadecimal.
As an example of the last point, consider the binary string 110111100001. This is
equivalent to
1101 1110 0001 = DE116
D E 1
This process is performed so naturally that an experienced programmer can mentally
convert visual representations of binary data to their hexadecimal equivalent without written
effort
Quotient
Figure 1 Examples of Converting from Decimal
Notation to Binary Notation for Integers
= 5 1
Remainder
11
2
5 = 2 1
2
2 = 1 0
2
= 0 1
10112 = 1110
(a) 1110
1
2
Quotient
= 5 0
Remainder
10
2
5 = 2 1
2
2 = 1 0
2
= 0 1
101012 = 2110
(b) 2110
1
2
21 = 10 1
2
Product
Figure 2 Examples of Converting from Decimal
Notation to Binary Notation for Fractions
0.81 ´ 2 = 1.62 1
Integer Part
0.62 ´ 2 = 1.24 1
0.24 ´ 2 = 0.48 0
0.48 ´ 2 = 0.96
0.96 ´ 2 = 1.92
0.92 ´ 2 = 1.84
0
1
1
0.1100112
(a) 0.8110 = 0.110112 (approximately)
Product
0.25 ´ 2 = 0.5 0
Integer Part
0.5 ´ 2 = 1.0 1
0.012
(B) 0.2510 = 0.012 (exactly)
Binary Numbers - how computer counts ?
Quick, what is 11?
9 and 2? or 6 and 5??
Which one???
We express numbers with numerals. The 10 numbers from zero to nine have their own numerals. But larger numbers don’t. To represent them, we re-use the ten numerals in special combinations where groupings of 10 are understood. If we want to talk about one-hundred twenty-three we write
123
where the 3 represents 3 ones, but the 2 represents 2 groupings of 10 ones (ten), while the 1 represents 1 grouping of 10 tens (one hundred). So
123
does not mean 6, even though what we write—1 and 2 and 3—suggests a total of 6. The understood implication of groupings gives this notation the meaning we intend. We regard one hundred twenty-three as being a single one-hundred and also two tens and also 3 ones.
The reason we use groupings of ten is that we have ten fingers, and counting originated on peoples’ fingers.
Other number systems differ. A race of people who had only one hand would have used groupings of 5 to represent numbers greater than five. They would choose to regard one hundred twenty-three as four twenty-fives and four fives and three ones, writing it as
443
A race of people with 4 fingers would regard it as being one sixty-four and three sixteens and two fours and three ones, writing it as
1323
The groupings used are always powers of the base number. If the base number is 10, we use groupings of 1, 10, 100, 1000, … which are 10 raised to the 0, 1, 2, 3, … power, respectively. If the base number is 5, we use groupings of 1, 5, 25, 125, … which are 5 raised to the 0, 1, 2, 3, … power, respectively. If the base number is 4, we use groupings of 1, 4, 16, 64, … which are 4 raised to the 0, 1, 2, 3, … power respectively.
Computers use 2 as the base number. (Maybe computers have only 2 fingers.) They use groupings of 1, 2, 4, 8, 16, 32, 64, 128, … to represent numbers. They regard one hundred twenty-three as one 64 and one 32 and one 16 and one 8 and one 2 and one 1. They write it as
1111011
So quick, what’s 123? Which is correct:
123= 100 + 20 + 3
123= 4x25 + 4x5 + 3
123= 64+ 3x16 + 2x4 +3
123= 64 + 32 + 16 + 8 + 2 + 1 ?
All are correct. So you can use any of the number systems correctly to describe the same set of numbers.
Here are the first 16 numbers, starting from 0, as represented using the base-2 or binary system used in computers:
| Decimal | Binary |
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
| 8 | 1000 |
| 9 | 1001 |
| 10 | 1010 |
| 11 | 1011 |
| 12 | 1100 |
| 13 | 1101 |
| 14 | 1110 |
| 15 | 1111 |
You should be able to convert back and forth.
Subscribe to:
Posts (Atom)