Transcript 10/20/04

COMS 161
Introduction to Computing
Title: Numeric Processing
Date: October 20, 2004
Lecture Number: 23
1
Announcements
• Exam 2
– Monday 10/25/2004
– Covers
• LANs
• The Internet
• HTTP ands HTML
Chapter 4
Chapter 17
Chapter 18
• Today’s Material
– Chapter 6
2
Review
• LAN’s
• The Internet
• HTML and HTTP
3
Outline
• Numeric Processing
4
Digital Number Representations
• Integers
– Infinite discrete subset of the number line
– Represented with a limited range
• Decimal numbers (real numbers)
– Infinite and continuous
– Represented with limited range and limited
precision
5
Integer Storage
• Integer values can be exactly
represented
base10
conversion
base2
6
Integer Storage
• Integer values can be exactly
represented
base10
conversion
base2
1
1 = 20
0000 0001
7
Integer Storage
• Integer values can be exactly
represented
base10
conversion
base2
1
1 = 20
0000 0001
2
1 = 21
0000 0010
8
Integer Storage
• Integer values can be exactly
represented
base10
conversion
base2
1
1 = 20
0000 0001
2
2 = 21
0000 0010
4
4 = 22
0000 0100
9
Integer Storage
• Integer values can be exactly
represented
base10
conversion
base2
1
1 = 20
0000 0001
2
2 = 21
0000 0010
4
4 = 22
0000 0100
8
8 = 23
0000 1000
10
Integer Storage
• Integer values can be exactly
represented
base10
conversion
base2
1
1 = 20
0000 0001
2
2 = 21
0000 0010
4
4 = 22
0000 0100
8
8 = 23
0000 1000
9
9 = 8 + 1 = 23+20
0000 1001
11
Integer Storage
• Integer values can be exactly
represented
base10
conversion
base2
1
1 = 20
0000 0001
2
2 = 21
0000 0010
4
4 = 22
0000 0100
8
8 = 23
0000 1000
9
9 = 8 + 1 = 23+20
0000 1001
10
10 = 8 + 2 = 23 + 21
0000 1010
12
Integer Storage
• Integer values can be exactly
represented
base10
conversion
base2
1
1 = 20
0000 0001
2
2 = 21
0000 0010
4
4 = 22
0000 0100
8
8 = 23
0000 1000
9
9 = 8 + 1 = 23+20
0000 1001
10
10 = 8 + 2 = 23 + 21
0000 1010
27
27 = 16+8+2+1 = 24+23+21+20
0001 1011
most significant bit
least significant bit
13
Integer Storage
• Integers are typically 32 bits (word size)
• Number of unique items that can be
represented with 32 bits
232 = 4,294,967,296
• One-half of the symbols
– Represent positive numbers
– Represent negative numbers
– Sign bit distinguishes between + and - numbers
14
Integer Storage
• Positive numbers
0, 1, 2, …, 231 - 1
• Negative numbers
-231 + 1, -231 + 2, …, -2, -1, 0
• Two representations of zero
– Get rid of one of them
– Gives us one more number
– Add it to the negative numbers
15
Integer Storage
• Range of integer numbers
-231, -231 + 1, …, -2, -1 0, 1, 2, …, 231 - 1
-2,147,483,648 … 2,147,483,647
• Integer overflow error
– Trying to represent an integer that is larger
than the most positive allowable integer or
more negative than most negative integer
– Frequently occurs during math operations
16
Integer Overflow
• 3 bits
– Can represent 23 = 8 values
– { 0, 1, 2, 3, 4, 5, 6, 7 }
410 = 1002
+ 310 = 0112
410 =
+ 510 =
1002
1012
How do I add
two
binary
numbers?
111
710 =
910 = 1 0012
2
carry out
overflow
17
Negative Numbers
• The range of integer numbers is
-231, -231 + 1, …, -2, -1 0, 1, 2, …, 231 - 1
-2,147,483,648 … 2,147,483,647
– How do we represent negative numbers?
• Could use one bit as a sign bit, but …
– Two’s complement representation solves
• The problem of two zeros
• Mathematical operations giving incorrect results
18
Two’s Complement Numbers
• Two steps in determining a two’s
complement representation of a number
– Positive numbers are the same as the
positive sign-magnitude representation
– Negative numbers
• Invert the bits of the unsigned quantity
• Add 1 to the result
19
Two’s Complement Numbers
– Negative numbers
• Invert the bits of the unsigned quantity
• Add 1 to the result
Decimal
number
-4
-7
Binary
magnitude
Bit inverse
Add one
Two’s
complement
representation
0100
1011
1011
+ 1
1100
1000
1011
+ 1
1001
0111
11
1011
1
11 00
20