Transcript CMPE 325 Computer Architecture II

CMPE 325 Computer
Architecture II
Cem Ergün
Eastern Mediterranean
University
Integer Representation and the ALU
Positive Binary Numbers


Computers use binary numbers (base 2)
Example (6 bit number)
0 1 0 1 1 0
= 0  25 + 1  24 + 0  23 + 1  22 + 1  21 + 0  20
= 0
+ 16
+ 0
+ 4
+ 2
+ 0
= 22


Each digit is d × Basei where i = 0 at the right
and increases going to the left (same process as
in base 10)
Does not make sense to store binary numbers in
ASCII since each character requires 1 byte
C. Ergun
CMPE325 CH #3
Slide #2
Converting to Binary


To convert a number to base 2, continue to
divide by 2, keeping the remainder at each step
Consider the example 22 going the other
direction
22
11
5
2
1
÷
÷
÷
÷
÷
2
2
2
2
2
= 11 remainder 0
= 5 remainder 1
= 2 remainder 1
= 1 remainder 0
= 0 remainder 1
LSB
MSB
So the binary number is 10110.
C. Ergun
CMPE325 CH #3
Slide #3
a
d
d
i
t
i
o
n
a
l
b
i
t
c
a
l
l
e
d
t
h
e
Two’s Complement
• Can represent positive and negative numbers by
first bit (MSB) as –231 position, then positive 2n:
d31 x -231 + d30 x 230 + ... + d2 x 22 + d1 x 21 + d0 x 20
• Example
1111 1111 1111 1111 1111 1111 1111 1100two
= 1x-231 +1x230 +1x229+... +1x22+0x21+0x20
= -231 + 230 + 229 + ... + 22 + 0 + 0
= -2,147,483,648ten + 2,147,483,644ten
= -4ten
• Note! Must specify width to find MSB => 32bits
is used in MIPS, so d31 is MSB
C. Ergun
CMPE325 CH #3
Slide #7
Two’s Complement Example

Consider the same example as before with a 1 in
the MSB
1 1 0 1 1 0
= -1  25 + 1  24 + 0  23 + 1  22 + 1  21 + 0  20
= -32
+ 16
+ 0
+ 4
+ 2
+ 0
= -10

Notice that the result was not- 22!
C. Ergun
CMPE325 CH #3
Slide #8
Two’s Complement Shortcut



A simpler way is to convert between positive and negative values
(goes both ways)
 Reverse every bit (01 and 10)
 Add 1 to the resulting number
Consider our previous example again
1 1 0 1 1 0  0 0 1 0 0 1
+
1
------------0 0 1 0 1 0
=
1 0ten
The original value was -10 and the new value is 10.
Explanation:
 x+x’ ≡ -1  x’+1 = -x
x=-4 : 1111 1111 1111 1111 1111 1111 1111 1100two
x’
: 0000 0000 0000 0000 0000 0000 0000 0011two
x’+1: 0000 0000 0000 0000 0000 0000 0000 0100two
invert: 1111 1111 1111 1111 1111 1111 1111 1011two
add 1 : 1111 1111 1111 1111 1111 1111 1111 1100two
C. Ergun
CMPE325 CH #3
Slide #9
Two’s Complement
0
0
1
1111
1110
0
10
0
-1
1
-2
2
0
11
1101
3
-3
1100
4
-4
5
-5
0
101
1011
6
-6
-7
1010
1001
C. Ergun
-8 -6
0
100
-4
7
-8
0
111
100
-2
0
0
110
2
4
6
CMPE325 CH #3
8
Slide #10
Two’s Complement in 8bits
More common: use of 2's complement negatives have one
additional number
0000 0000 = 0
0000 0001 = 1
…
0111 1110 = 126
0111 1111 = 127
1000 0000 = -128
1000 0001 = -127
...
1111 1101 = -3
All negative numbers
1111 1110 = -2
have a '1' in the
1111 1111 = -1
highest position
C. Ergun
CMPE325 CH #3
Slide #11
Two’s Complement in MIPS
0000 ... 0000 0000 0000 0000two =
0000 ... 0000 0000 0000 0001two =
0000 ... 0000 0000 0000 0010two =
...
0111 ... 1111 1111 1111 1101two =
0111 ... 1111 1111 1111 1110two =
0111 ... 1111 1111 1111 1111two =
1000 ... 0000 0000 0000 0000two =
1000 ... 0000 0000 0000 0001two =
1000 ... 0000 0000 0000 0010two =
...
1111 ... 1111 1111 1111 1101two =
1111 ... 1111 1111 1111 1110two =
1111 ... 1111 1111 1111 1111two =
C. Ergun
CMPE325 CH #3
0ten
1ten
2ten
2,147,483,645ten
2,147,483,646ten
2,147,483,647ten
–2,147,483,648ten
–2,147,483,647ten
–2,147,483,646ten
–3ten
–2ten
–1ten
Slide #12
Two’s Complement in MIPS
C. Ergun
CMPE325 CH #3
Slide #13
Understanding Signed Ops

Programmers can explicitly use unsigned data
values (such as unsigned int)


Require unsigned operations such as sltu and sltiu
Signed instructions help determine whether
values are considered to have a sign bit

For instance, lbu is for load byte unsigned
• One byte is copied from memory into a register
• The high order 24 bits are filled with the value 0

The lb instruction is signed
• The value is then s i g n
, meaning that the sign bit
from the first byte is repeated into the high order bits of
the word

Immediate values remain sign extended
C. Ergun
CMPE325 CH #3
Slide #14
Sign Extension

Sign extended value
0
00101010
8 bit s
8 bit s
8 bit s
1
10101010
8 bit s

8 bit s
8 bit s
8 bit s
8 bit s
No sign extension
00000000 00000000 00000000 00101010
8 bit s
8 bit s
8 bit s
8 bit s
00000000 00000000 00000000 10101010
8 bit s
C. Ergun
8 bit s
8 bit s
CMPE325 CH #3
8 bit s
Slide #15
Number formats
Different compare operations
required for both number types
 Signed integer
slt Set an less than
slti Set on less than immediate
 Unsigned integer
sltu Set an less than
sltiu Set on less than immediate

C. Ergun
CMPE325 CH #3
Slide #16
Number formats
C. Ergun
CMPE325 CH #3
Slide #17
Hexadecimal



Hexadecimal is base 16, so digits are -0 9, -A F
Since most values are multiples of 4 bits,
hexadecimal is a popular way of representing
numbers (commonly written 0xn n n) n n
Easy to convert binary to hexadecimal by
breaking to blocks of 4 bits (24 is 16 values)
C. Ergun
CMPE325 CH #3
Slide #18
Hexadecimal Table
Number
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
C. Ergun
Value
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CMPE325 CH #3
Slide #19
Hexadecimal Example

Consider the example
1111 0010 0110 1011
F
C. Ergun
2
6
B
CMPE325 CH #3
Slide #20
Octal



Octal is base 8 and appears occasionally, though
not used as frequently
Binary to octal is grouped into 3 bits
Example
111 100 100 110
7
C. Ergun
4
4
6
CMPE325 CH #3
Slide #21
Shifting Bits

The sll and srl instruction were mentioned
before in passing, but its purpose should now
make more sense
sll $t0, $t1, 2
srl $t0, $t1, 2

# Shift bits left twice
# Shift bits right twice
Shifting a value to the left twice is the same as
multiplying its value by 22 = 4
C. Ergun
0 0 0 1 1 0
=
6ten
0 1 1 0 0 0
= 24ten
CMPE325 CH #3
Slide #22
Addition & subtraction
C. Ergun
CMPE325 CH #3
Slide #23
Addition & subtraction
C. Ergun
CMPE325 CH #3
Slide #24
Overflow




Overflow is when a number gets too large to fit
The left most bit is not the same as the infinite
number of bits to the left of it
Can happen with both positive and negative
values
Handling overflow is the responsibility of the
programmer
C. Ergun
CMPE325 CH #3
Slide #25
Overflow
 The difference of two numbers can exceed any
representation
2's complement: Numbers change sign and size
C. Ergun
CMPE325 CH #3
Slide #26
Detecting Overflow



Overflow can not occur when adding numbers with
different signs or subtracting numbers of the same sign
(reverses of each other)
Adding numbers of the same sign or subtracting numbers
of different signs, however, can cause overflow
Addition overflow
Overflow conds



Sign of operands the same, and
Sign of result not the same
Subtraction overflow


Sign of operands different, and
Sign of result different from sign of A
• A–B=C
• A Posit iv
e a
n d Bn ega
t iv
e th
en C should b
e posit iv
e
• AN
e ga
t iv
e a
n d B posit iv
e te
hn C should b
e n ega
t iv
e
C. Ergun
CMPE325 CH #3
Slide #27
How to Overcome:
C. Ergun
CMPE325 CH #3
Slide #28
How to Overcome:
C. Ergun
CMPE325 CH #3
Slide #29
The sll/srl Instructions

When encoded, the sll is an arithmetic R
- format
instruction that uses the s h a field
m t
Bits
6
OP=0
5
0
5
rt
5
rd
5
6
shamt
func
First Second Result
Shift Function
Source Source Register Amount Code
Register Register
C. Ergun
CMPE325 CH #3
Slide #30
Shift Operations
C. Ergun
CMPE325 CH #3
Slide #31