Transcript EE 3760, Chapter 4 - Seattle Pacific University

Crunching Numbers
• Topics we need to explore
• Representing numbers on a computer
• Negatives, too
• Building hardware to do logic and math
•
•
•
•
And, Or
Hardware Alert!
Addition, Subtraction
Comparisons
Multiplication and Division
• Building hardware to work with Floating Point
numbers
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch3a- 2
Representation
• All data on a computer is represented in binary
• 32 bits of data may be:
•
•
•
•
32-bit unsigned integer
4 ASCII characters
Single-precision IEEE floating point number
Who knows...
data: 1000 1001 0100 0110 0000 0101 0010 1000
As 32-bit unsigned integer: 2,303,067,432
As 32-bit 2’s complement integer: -1,991,899,864
As 4 ASCII characters: ‘??’, ‘F’, ENQ, ‘(‘
Note: Limited ASCII chart on p. 142
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch3a- 3
ASCII Representation of Numbers
• Terminal I/O (keyboard, display) only deals with
ASCII characters
NULL Termination
• Typically, strings of characters
• “We’re #1” --> 87,101,44,114,101,32,35,49,0
• Note that the number ‘1’ is represented by 49
• Numbers in I/O consist of their ASCII representations
• To output 103, use ASCII values 49, 48, 51 (3 bytes)
• Outputting 103 (one byte) won’t work
code for ‘g’
Seattle Pacific University
‘1’, ‘0’, ‘3’
EE/CS/CPE 3760 - Computer Organization
Ch3a- 4
Number Systems- Negative Numbers
• What about negative numbers?
• We need to represent numbers less than zero as well
as zero or higher
• In n bits, we get 2n combinations
• Make half positive, half negative...
First method: use an extra bit for the sign
0 000 0000 0000 0000 0000 0000 0000 0101
1 000 0000 0000 0000 0000 0000 0000 0101
Sign bit: 0-->positive, 1-->negative
Seattle Pacific University
+5
-5
31 remaining bits for magnitude
EE/CS/CPE 3760 - Computer Organization
Ch3a- 5
Sign and Magnitude Representation
-7
Seven Negative
Numbers and
“Negative” Zero
-6
1111
+0
0001
1110
-5
+1
0000
1101
-4
1100
-3
1011
-2
0010
+2
Inner numbers: 0011 +3
Binary
representation 0100 +4
1010
0101
1001
-1
+5
Note: Example is shown
for 4-bit numbers
Seven Positive
Numbers and
“Positive” Zero
0110
1000
-0
0111
+6
+7
• High order bit is sign: 0 = positive (or zero), 1 = negative
• Three low order bits represent the magnitude: 0 (000) through 7 (111)
• Number range for n bits = +/- 2n-1 -1
• Two different representations for 0!
• Two discontinuities
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch3a- 6
Two’s Complement Representation
-1
Re-order
Negative
Numbers to
Eliminate
Discontinuities
-2
1111
+0
0001
1110
-3
+1
0000
1101
-4
1100
-5
1011
-6
0010
+2
Inner numbers: 0011 +3
Binary
representation 0100 +4
1010
0101
1001
-7
Eight Positive
Numbers
+5
0110
1000
-8
0111
+6
+7
• Only one discontinuity now
• Only one zero
• One extra negative number
Seattle Pacific University
Note: Example is shown
for 4-bit numbers
Note: Negative numbers
still have 1 for MSB
EE/CS/CPE 3760 - Computer Organization
Ch3a- 7
2’s Complement Negation Method #1
To calculate the negative of a 2’s complement number:
1. Complement the entire number
2. Add one
Examples:
n = 0110= 6
complement
1001
add 1
-n =1010 = -6
WARNING: This is for calculating
the negative of a number. There is
no such thing as “taking the 2’s
complement of a number”.
n = 01000100 = 68
complement
Seattle Pacific University
n = 10010000= -112
complement
10111011
add 1
01101111
add 1
-n =10111100 = -68
-n =01110000 = 112
EE/CS/CPE 3760 - Computer Organization
Ch3a- 8
2’s Complement Negation Method #2
To calculate the negative of a 2’s complement number:
1. Starting at LSB, search to the left for the first one
2. Copy (unchanged) all of the bits to the right of the first one and
the first one itself
3. Complement the remaining bits
Examples:
n = 0110= 6
complement
copy
n = 01000100 = 68
complement
copy
-n = 10111 100 = -68
-n = 1010 = -6
n = 10010000= -112
complement
copy
-n = 01110000 = 112
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch3a- 9
Adding Two’s Complement Numbers
Just add the complete
numbers together.
4
0100
-4
1100
+3
0011
+ (-3)
1101
7
0111
-7
11001
Sign taken care of
automatically.
4
0100
-4
1100
-3
1101
+3
0011
1
10001
-1
1111
Ignore carry-out (for now)
A carry out from sign bit does not necessarily mean overflow!
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch3a- 10
Overflow
Add two positive numbers to get a negative number
or two negative numbers to get a positive number
-1
Not a discontinuity No Overflow
-2
1111
+0
0001
1110
-3
1101
0010
+2
-4
1100
0011
+3 -7 - 2 = +7
-5
1011
0100
+4
-6
1010
0101
1001
A carryout from the
MSB could mean
crossing at either of
these places – One is
OK, one is Overflow
5 + 3 = -8
+1
0000
-7
Seattle Pacific University
0110
1000
-8
0111
+5
Overflow occurs when
crossing discontinuity
+6
+7
Overflow cannot occur when
adding a positive and negative
number together
EE/CS/CPE 3760 - Computer Organization
Ch3a- 11
Detecting Overflow
Overflow occurs when:
We add two positive numbers and obtain a negative
We add two negative numbers and obtain a positive
Looking at the sign bit (MSB):
+
+
+
Cout
0
0
+0
0
Cin
0
No overflow
+
+
-
Cout
0
0
+0
1
Cin
1
Overflow
+
Cout
1
1
+1
0
Cin
0
Overflow
Overflow when carry in to sign
bit does not equal carry out
Seattle Pacific University
-
Cout
1
1
+1
1
Cin
1
No Overflow
Cin
Cout
+
-
Cout
0
1
+0
1
Cin
0
No Overflow
+
+
Cout
1
1
+0
0
Cin
1
No Overflow
Overflow
EE/CS/CPE 3760 - Computer Organization
Ch3a- 12
Signed and Unsigned operations
Consider the following:
$t0 = 0000 0000 0000 0000 0000 0000 0000 0101
$t1 = 1111 1111 1111 1111 1111 1111 1111 1001
execute:
slt $s0, $t0, $t1
What’s the result?
If we mean for $t0 to be 5 and $t1 to be 4,294,967,289 (treat
as unsigned integers) then $s0 should get 1
If we mean for $t0 to be 5 and $t1 to be -7 (treat as signed
integers) then $s0 should get 0
The default is to treat as signed integers
Use sltu for unsigned integers
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch3a- 13
Using more bits
What’s different between 4-bit 2’s complement and 32-bit?
MSB has moved from bit 3 to bit 31!
Sign Extension
To convert from 4-bit 2’s complement to 32-bit:
Copy all 4 bits to 4 Least significant bits of the 32-bit number.
Copy MSB of original number into all remaining bits
4-bit
2’s comp.
0111
710
0000 0000 0000 0000 0000 0000 0000 0111
710 (32-bit 2’s comp.)
1010
-610
1111 1111 1111 1111 1111 1111 1111
-610 (32-bit 2’s comp.)
Seattle Pacific University
1010
EE/CS/CPE 3760 - Computer Organization
Ch3a- 14
Loading a single byte from memory
We can read a single 8-bit byte from memory location 3000 by using:
lb $t0, 3000($0)
# read byte at mem[3000]
assuming mem[3000] = 0xF3, we get...
$t0: 0xFFFFFFF3
(sign-extension for other 3 bytes)
0x prefix means Hex
If we only want the byte at 3000 (without extension), used an unsigned load:
lbu $t0, 3000($0)
# read byte a mem[3000]
$t0: 0x000000F3
(no sign-extension)
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch3a- 15