Transcript PPT

CSCI-365
Computer Organization
Lecture 10
Note: Some slides and/or pictures in the following are adapted from:
Computer Organization and Design, Patterson & Hennessy, ©2005
Some slides and/or pictures in the following are adapted from:
slides ©2008 UCB
How to Represent Negative Numbers?
• So far, unsigned numbers
• Obvious solution: define leftmost bit to be sign!
– 0  +, 1  –
– Rest of bits can be numerical value of number
• Representation called sign and magnitude
• MIPS uses 32-bit integers. +1ten would be:
0000 0000 0000 0000 0000 0000 0000 0001
• And –1ten in sign and magnitude would be:
1000 0000 0000 0000 0000 0000 0000 0001
Shortcomings of sign and magnitude?
• Arithmetic circuit complicated
– Special steps depending whether signs are the same or
not
• Also, two zeros
– 0x00000000 = +0ten
– 0x80000000 = –0ten
– What would two 0s mean for programming?
• Therefore sign and magnitude abandoned
Another try: complement the bits
• Example: 710 = 001112 –710 = 110002
• Called One’s Complement
• Note: positive numbers have leading 0s, negative
numbers have leadings 1s
00000 00001 ...
10000 ... 11110 11111
• What is -00000 ? Answer: 11111
• How many positive numbers in N bits?
• How many negative numbers?
01111
Shortcomings of One’s complement?
• Arithmetic still somewhat complicated
• Still two zeros
– 0x00000000 = +0ten
– 0xFFFFFFFF = -0ten
• Although used for awhile on some computer
products, one’s complement was eventually
abandoned because another solution was better
Negative Numbers
32 bits can only represent 232 numbers – if we wish to also represent
negative numbers, we can represent 231 positive numbers (incl zero)
and 231 negative numbers
0000 0000 0000 0000 0000 0000 0000 0000two = 0ten
0000 0000 0000 0000 0000 0000 0000 0001two = 1ten
…
0111 1111 1111 1111 1111 1111 1111 1111two = 231-1
1000 0000 0000 0000 0000 0000 0000 0000two = -231
1000 0000 0000 0000 0000 0000 0000 0001two = -(231 – 1)
1000 0000 0000 0000 0000 0000 0000 0010two = -(231 – 2)
…
1111 1111 1111 1111 1111 1111 1111 1110two = -2
1111 1111 1111 1111 1111 1111 1111 1111two = -1
2’s Complement
0000 0000 0000 0000 0000 0000 0000 0000two = 0ten
0000 0000 0000 0000 0000 0000 0000 0001two = 1ten
…
0111 1111 1111 1111 1111 1111 1111 1111two = 231-1
1000 0000 0000 0000 0000 0000 0000 0000two = -231
1000 0000 0000 0000 0000 0000 0000 0001two = -(231 – 1)
1000 0000 0000 0000 0000 0000 0000 0010two = -(231 – 2)
…
1111 1111 1111 1111 1111 1111 1111 1110two = -2
1111 1111 1111 1111 1111 1111 1111 1111two = -1
Why is this representation favorable?
Consider the sum of 1 and -2 …. we get -1
Consider the sum of 2 and -1 …. we get +1
This format can directly undergo addition without any conversions!
Each number represents the quantity
x31 -231 + x30 230 + x29 229 + … + x1 21 + x0 20
2’s Complement
0000 0000 0000 0000 0000 0000 0000 0000two = 0ten
0000 0000 0000 0000 0000 0000 0000 0001two = 1ten
…
0111 1111 1111 1111 1111 1111 1111 1111two = 231-1
1000 0000 0000 0000 0000 0000 0000 0000two = -231
1000 0000 0000 0000 0000 0000 0000 0001two = -(231 – 1)
1000 0000 0000 0000 0000 0000 0000 0010two = -(231 – 2)
…
1111 1111 1111 1111 1111 1111 1111 1110two = -2
1111 1111 1111 1111 1111 1111 1111 1111two = -1
Note that the sum of a number x and its inverted representation x’ always
equals a string of 1s (-1)
x + x’ = -1
x’ + 1 = -x
… hence, can compute the negative of a number by
-x = x’ + 1
inverting all bits and adding 1
Similarly, the sum of x and –x gives us all zeroes, with a carry of 1
In reality, x + (-x) = 2n … hence the name 2’s complement
2’s Complement Number “line”: N = 5
00000 00001
11111
11110
00010
-1 0 1
11101
2
-2
-3
11100
-4
.
.
.
.
.
.
• 2N-1 non-
negatives
• 2N-1 negatives
• one zero
• how many
positives?
-15 -16 15
10001 10000 01111
00000
10000 ... 11110 11111
00001 ...
01111
Example
Compute the 32-bit 2’s complement representations
for the following decimal numbers:
5, -5, -6
What if too big?
• Binary bit patterns above are simply representatives of
numbers. Strictly speaking they are called “numerals”
• Numbers really have an  number of digits
– with almost all being same (00…0 or 11…1) except for a few of
the rightmost digits
– Just don’t normally show leading digits
• If result of add (or -, *, / ) cannot be represented by these
rightmost HW bits, overflow is said to have occurred
00000 00001 00010
unsigned
11110 11111
Detecting Overflow
• No overflow when adding a positive and a negative
number
• No overflow when signs are the same for subtraction
• Overflow occurs when the value affects the sign:
– overflow when adding two positives yields a negative
– or, adding two negatives gives a positive
– or, subtract a negative from a positive and get a negative
– or, subtract a positive from a negative and get a positive
Detecting Overflow
• For an unsigned number, overflow happens when the
last carry (1) cannot be accommodated
• For a signed number, overflow happens when the most
significant bit is not the same as every bit to its left
– when the sum of two positive numbers is a negative result
– when the sum of two negative numbers is a positive result
– The sum of a positive and negative number will never overflow
• MIPS allows addu and subu instructions that work with
unsigned integers and never flag an overflow – to detect
the overflow, other instructions will have to be executed
Signed / Unsigned
• The hardware recognizes two formats:
unsigned (corresponding to the C declaration unsigned int)
-- all numbers are positive, a 1 in the most significant bit
just means it is a really large number
signed (C declaration is signed int or just int)
-- numbers can be +/-, a 1 in the MSB means the number
is negative
This distinction enables us to represent twice as many
numbers when we’re sure that we don’t need negatives
MIPS Instructions
Consider a comparison instruction:
slt $t0, $t1, $zero
and $t1 contains the 32-bit number 1111 01…01
What gets stored in $t0?
The result depends on whether $t1 is a signed or unsigned
number – the compiler/programmer must track this and
accordingly use either slt or sltu
slt $t0, $t1, $zero
sltu $t0, $t1, $zero
stores 1 in $t0
stores 0 in $t0
Sign Extension
• Occasionally, 16-bit signed numbers must be converted
into 32-bit signed numbers – for example, when doing an
add with an immediate operand
• The conversion is simple: take the most significant bit and
use it to fill up the additional bits on the left – known as
sign extension
So 210 goes from 0000 0000 0000 0010 to
0000 0000 0000 0000 0000 0000 0000 0010
and -210 goes from 1111 1111 1111 1110 to
1111 1111 1111 1111 1111 1111 1111 1110
Quiz
X = 1111 1111 1111 1111 1111 1111 1111 1100two
Y = 0011 1011 1001 1010 1000 1010 0000 0000two
A.
B.
X > Y (if signed)
X > Y (if unsigned)
1:
2:
3:
4:
AB
FF
FT
TF
TT
Review of Numbers
• Computers are made to deal with numbers
• What can we represent in N bits?
– 2N things, and no more! They could be…
– Unsigned integers:
0 to 2N - 1
(for N=32, 2N–1 = 4,294,967,295)
– Signed Integers (Two’s Complement)
-2(N-1)
to
2(N-1) - 1
(for N=32, 2(N-1) = 2,147,483,648)
What about other numbers?
1.
2.
3.
Very large numbers?
(seconds/millennium)
 31,556,926,00010 (3.155692610 x 1010)
Very small numbers? (Bohr radius)
 0.000000000052917710m (5.2917710 x 10-11)
Numbers with both integer & fractional parts?
 1.5
First consider #3
…our solution will also help with 1 and 2
Representation of Fractions
“Binary Point” like decimal point signifies
boundary between integer and fractional parts:
Example 6-bit
representation:
xx.yyyy
21
20
2-1
2-2
2-3
2-4
10.10102 = 1x21 + 1x2-1 + 1x2-3 = 2.62510
If we assume “fixed binary point”, range of 6-bit
representations with this format:
0 to 3.9375 (almost 4)