Computer Arithmetic

CS353 – Computer Architecture

Najeeb-Ur-Rehman
Assistant Professor
Department of Computer Science
Faculty of Computing & IT
University of Gujrat
1
 Limits of Computer Numbers
 Bits can represent anything!
 Characters?
 26 letter => 5 bits
 upper/lower case + punctuation => 7 bits (in 8)
 rest of the world’s languages => 16 bits (unicode)
 Logical values?
 0 -> False, 1 => True
 colors ?
 locations / addresses? commands?
 but N bits => only 2N things

2
 Arithmetic Operations
 Numbers represented in binary
 Positive & Negative numbers ?
 Largest Number ?
 Result larger than largest number?
 Fractions & real numbers representation?
 Hardware add, subtract, multiply, divide?

3
 Positive & Negative Numbers
 So far, unsigned numbers
 Obvious solution: define leftmost bit to be sign!
 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
 Arithmetic circuit more complicated
 Special steps depending whether signs are the same
or not

4
 2’s Complement Number line
11111 00000 00001  2 N-1 non-negatives
11100 00010  2 N-1 negatives
-1 0 1
-2 2  one zero
 how many
. . positives?
. .  comparison?
. .  overflow?

-15 -16 15
10001 10000 01111
5
 Two’s Complement Formula
 Can represent positive and negative numbers in terms of
the bit value times a power of 2:
 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: need to specify width: we use 32 bits

6
Sign extension
 Convert 2’s complement number using n bits to more
than n bits
 Simply replicate the most significant bit (sign bit) of
smaller to fill new bits
2’s comp. positive number has infinite 0s
2’s comp. negative number has infinite 1s
16-bit -4ten to 32-bit:

1111 1111 1111 1100two

1111 1111 1111 1111 1111 1111 1111 1100two

7
 Signed v. Unsigned Comparisons
 X = 1111 1111 1111 1111 1111 1111 1111 1100two
 Y = 0011 1011 1001 1010 1000 1010 0000 0000two
 Is X > Y?
 unsigned: YES
 signed: NO
 Converting to decimal to check
 Signed comparison:
-4ten < 1,000,000,000ten?
 Unsigned comparison:
4,294,967,292ten > 1,000,000,000ten?
 slt, slti and sltu, sltiu instructions

8
 Addition & Subtraction
 Addition: Binary Addition
 Subtraction: Binary 2’s comp. Addition
 Overflow
 Adding two positive numbers
 Adding two negative numbers
 add, addi, sub
 Cause exception on overflow
 addu, addiu, subu
 Cause no exception on overflow

9
 Determining Overflow
0111 (+7) 0111 (+7)
0101 (+5) 1011 (-5)
1100 (-4) 10010 (+2)

1001 (-7) 1001 (-7)

0101 (+5) 1011 (-5)
1110 (-2) 10100 (+4)

Overflow occurs when the signs of the values are the same,
and the sign of the result is different.
Overflow if Cin to MSB is different from Cout of MSB
10
 Arithmetic and Logic Unit
 The ALU is at the heart of the CPU
 Does math and logic
• The ALU is primarily involved in R-type
instructions
– Perform an operation on two registers and
produce a result
• Where is the operation specified?
– The instruction type specifies the operation
– The ALU will have to be controlled by the
instruction opcode
11
 Arithmetic Logic Unit (ALU)

12
 ALU - Logic Operations
Start out by supporting AND and OR operations
Operation
2-to-1 Mux
A
0
Result
1
B
If Operation = 0, Result = A • B
If Operation = 1, Result = A  B
Two operands, two results.
We need only one result...

The Operation input comes from logic that looks at the opcode

13
 Arithmetic Unit
cin
0 1
a b cin s cout ab
0 0 0 00
0 0 1
0 1 0 01
0 1 1
1 0 0 11
1 0 1
1 1 0 10
1 1 1

14
 Arithmetic Unit
Input Output
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

15
 Adding to our ALU Cin Op (2 bits)
(Op is now 2 bits)
A Cin
CarryIn Operation ALU Result
B Cout

A
0 Cout
Result
11

Operation Function
B + 2
00 A•B
01 AB
Add an Adder 10 A+B
CarryOut
Connect CarryIn (from previous bit) and CarryOut (to next bit)

Expand Mux to 3-to-1 (Op is now 2 bits)

16
 1-bit & 32-bit ALU
• Stack 32 of our 1-bit
ALU’s together
– Each one gets one bit
from A and one from B
• Connect to common
Operation controls
– Now we can do 32-bit
AND and OR operations
• Connect Cout’s to Cin’s
– Now, 32-bit adds will
work
– Note: Carry will ripple
through the stages, one
at a time
• Ripple-Carry Adder
17
 Subtracting Set to 1 for LSB
BInvert
• Our ALU can add now, but CarryIn Operation
what about subtraction?
• To compute A - B, we can A
0
instead compute A + (-B)
• In 2’s complement, 1 Result
-B = B + 1
• Add an inverter, and a B
B
0
+ 2
1
signal BInvert to get B
• Now, how about that
+1? CarryOut

– CarryIn to LSB is unused

(always zero) For subtraction:
Set CarryIn of LSB to 1,
– Set it to 1!
Set BInvert to 1
• Subtraction just sets
BInvert and Cin to 1
18
 Subtraction a b Cin output
input input input
A 0 0 A

0 B 0 B

A 0 1 A+1

A 0* 0 A–1

A B 1 A+B+1

A B* 1 A–B

A B 0 A+B

A B* 0 A – B -1

19