Arithmetic for Computers

Topics
 Arithmetic
 Signed and unsigned numbers
 Addition and Subtraction
 Logical operations
 ALU: arithmetic and logic unit
 Multiply
 Divide
 Floating Point
 notation
 add
 multiply

TU/e Processor Design 5Z032 2

Arithmetic
 Where we've been:
 Performance (seconds, cycles, instructions)
 Abstractions:
Instruction Set Architecture
Assembly Language and Machine Language
 What's up ahead:
 Implementing the Architecture
operation

32 ALU
result

32

32
TU/e Processor Design 5Z032 3
 Binary numbers (1)
 Bits have no inherent meaning (no semantics)
 Decimal number system, e.g.:
4382 = 4x103 + 3x102 + 8x101 + 2x100
 Can use arbitrary base g; value of digit c at position i:
c x gi
 Binary numbers (base 2)
n-1 n-2 … 1 0 position

an-1 an-2 … a1 a0 digit

2n-1 2n-2 … 21 20 weight

 (an-1 an-2... a1 a0) two = an-1 x 2n-1 + an-2 x 2n-2 + … + a0 x 20

TU/e Processor Design 5Z032 4

 Binary numbers (2)
 So far numbers are unsigned
 With n bits 2n possible combinations

1 bit 2 bits 3 bits 4 bits decimal value

0 00 000 0000 0
1 01 001 0001 1
10 010 0010 2
11 011 0011 3
100 0100 4
101 0101 5
110 0110 6
111 0111 7
1000 8
1001 9

 a0 : least significant bit (lsb)

 an-1: most significant bit (msb)

TU/e Processor Design 5Z032 5

 Binary numbers (3)
 Binary numbers (base 2)
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001...
decimal: 0...2n-1

 Of course it gets more complicated:

- numbers are finite (overflow)
- fractions and real numbers
- negative numbers
 e.g., no MIPS subi instruction;
 however, addi can add a negative number

How do we represent negative numbers?

i.e., which bit patterns will represent which numbers?

TU/e Processor Design 5Z032 6

Conversion
 Decimal -> binary
Divide by 2 Remainder
4382
2191 0
1095 1
4382ten =
547 1 1 0001 0001 1110two
273 1
136 1
68 0
34 0
17 0
8 1
4 0
2 0
1 0
0 1

 Hexadecimal: base 16. Octal: base 8

1010 1011 0011 1111two = ab3fhex

TU/e Processor Design 5Z032 7

Signed binary numbers
Possible representations:
 Sign Magnitude: One's Complement Two's Complement
000 = +0 000 = +0 000 = +0
001 = +1 001 = +1 001 = +1
010 = +2 010 = +2 010 = +2
011 = +3 011 = +3 011 = +3
100 = -0 100 = -3 100 = -4
101 = -1 101 = -2 101 = -3
110 = -2 110 = -1 110 = -2
111 = -3 111 = -0 111 = -1

 Issues: balance, number of zeros, ease of operations

 Which one is best? Why?

TU/e Processor Design 5Z032 8

Two’s complement
(let’s restrict to 4 bits)
0000
1111 0001
-1 0
1 0010
1110 15
-2 2
14
1101 -3 0011
13 3

1100 -4 12 positive
4 0100
negative
11
-5 5
1011 0101
10
-6 9 6
1010 8 0110
-7 7
-8
1001 0111
1000

TU/e Processor Design 5Z032 9

Two’s complement
0000 3+2=5
1111 0001
-1 0
1 0010
1110 15
-2 2
14
1101 -3 0011
13 3

1100 -4 12 positive
4 0100
negative
11
-5 5
1011 0101
10
-6 9 6
1010 8 0110
-7 7
-8
1001 0111
1000

TU/e Processor Design 5Z032 10

Two’s complement
3+ (-5) = -2
0000
1111 0001
-1 0
1 0010
1110 15
-2 2
14
1101 -3 0011
13 3

1100 -4 12 positive
4 0100
negative
11
-5 5
1011 0101
10
-6 9 6
1010 8 0110
-7 7
-8
1001 0111
1000

TU/e Processor Design 5Z032 11

Two’s complement
3+6 = -7 !!
0000 overflow
1111 0001
-1 0
1 0010
1110 15
-2 2
14
1101 -3 0011
13 3

1100 -4 12 positive
4 0100
negative
11
-5 5
1011 0101
10
-6 9 6
1010 8 0110
-7 7
-8
1001 0111
1000

TU/e Processor Design 5Z032 12

Two’s complement
-3 + (-6) = 7 !!
0000
underflow
1111 0001
-1 0
1 0010
1110 15
-2 2
14
1101 -3 0011
13 3

1100 -4 12 positive
4 0100
negative
11
-5 5
1011 0101
10
-6 9 6
1010 8 0110
-7 7
-8
1001 0111
1000

TU/e Processor Design 5Z032 13

Two's Complement Operations
 Negating a two's complement number: invert all bits
and add 1
 remember: “negate” and “invert” are quite different!

 Proof:
a + a = 1111.1111b = -1 d =>
-a = a + 1

TU/e Processor Design 5Z032 14

 Two's Complement Operations
Converting n bit numbers into numbers with more than n bits:
 MIPS 8 bit, 16 bit values / immediates converted to 32 bits
 Copy the most significant bit (the sign bit) into the other bits
0010 -> 0000 0010
1010 -> 1111 1010
 MIPS "sign extension" example instructions:
lb load byte (signed)
lbu load byte (unsigned)
slti set less than immediate (signed)
sltiu set less than immediate (unsigned)

TU/e Processor Design 5Z032 15

Addition & Subtraction
 Just like in grade school (carry/borrow 1s)
0111 0111 0110
+ 0110 - 0110 - 0101

 Two's complement operations easy

 subtraction using addition of negative numbers
0110 0110
- 0101 + 1010

 Overflow (result too large for finite computer word):

 e.g., adding two n-bit numbers does not yield an n-bit number
0111
+ 0001 note that overflow term is somewhat misleading,
1000 it does not mean a carry “overflowed”

TU/e Processor Design 5Z032 16

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

 Consider the operations A + B, and A – B

 Can overflow occur if B is 0 ?
 Can overflow occur if A is 0 ?

TU/e Processor Design 5Z032 17

Effects of Overflow
 When an exception (interrupt) occurs:
 Control jumps to predefined address for exception
(interrupt vector)
 Interrupted address is saved for possible resumption in
exception program counter (EPC); new instruction: mfc0
(move from coprocessor0)
 Interrupt handler handles exception (part of OS).
registers $k0 and $k1 reserved for OS

 Details based on software system / language

 C ignores integer overflow; FORTRAN not

 Don't always want to detect overflow

— new MIPS instructions: addu, addiu, subu
note: addiu and sltiu still sign-extends!
TU/e Processor Design 5Z032 18
 Logic operations
 Sometimes operations on individual bits needed:

Logic operation C operation MIPS instruction

Shift left logical << sll
Shift right logical >> srl
Bit-by-bit AND & and, andi
Bit-by-bit OR | or, ori

 and and andi can be used to turn off some bits;

or and ori turn on certain bits
 Of course, AND en OR can be used for logic operations.
 Note: Language C’s logical AND (&&) and OR (||) are conditional
 andi and ori perform no sign extension !

TU/e Processor Design 5Z032 19

Exercise: gates
Given: 3-input logic function of A, B and C, 2-outputs

Output D is true if at least 2 inputs are true

Output E is true if odd number of inputs true

 Give truth-table

 Give logic equations

 Give implementation with AND and OR gates, and

Inverters.

TU/e Processor Design 5Z032 20

An ALU (arithmetic logic unit)
 Let's build an ALU to support the andi and ori
instructions
 we'll just build a 1 bit ALU, and use 32 of them

operation

a result
b

TU/e Processor Design 5Z032 21

Review: The Multiplexer
 Selects one of the inputs to be the output, based on a
control input
S note: we call this a 2-input mux
even though it has 3 inputs!
A 0
C
B 1

 Lets build our ALU and use a MUX to select the

outcome for the chosen operation

TU/e Processor Design 5Z032 22

Different Implementations
 Not easy to decide the “best” way to build something
 Don't want too many inputs to a single gate
 Don’t want to have to go through too many gates
 For our purposes, ease of comprehension is important
 Let's look at a 1-bit ALU for addition (= full-adder):
CarryIn
cout = a b + a cin + b cin
a sum = a xor b xor cin
+ Sum
b

CarryOut

 How could we build a 1-bit ALU for add, and, and or?
 How could we build a 32-bit ALU?
TU/e Processor Design 5Z032 23
 Building a 32 bit ALU
CarryIn Operation

a0 CarryIn
Operation ALU0
Result0
b0
CarryIn CarryOut

a a1 CarryIn
0 ALU1
Result1
b1
CarryOut

1
Result
a2 CarryIn
Result2
ALU2
b2
2 CarryOut
b

CarryOut
a31 CarryIn
Result31
ALU31
b31

TU/e Processor Design 5Z032 24

What about subtraction (a – b) ?
 Two's complement approach: just negate b and add
 How do we negate?

 A very clever solution:

Binvert Operation
CarryIn

a
0

1
Result

b 0 2

CarryOut
TU/e Processor Design 5Z032 25
ALU symbol
operation

32
a
zero
32
ALU result
overflow
32
b

carry-out

TU/e Processor Design 5Z032 26

 Conclusions
 We can build an ALU to support the MIPS instruction set
 key idea: use multiplexor to select the output we want
 we can efficiently perform subtraction using two’s complement
 we can replicate a 1-bit ALU to produce a 32-bit ALU
 Important points about hardware
 all of the gates are always working
 not efficient from energy perspective !!
 the speed of a gate is affected by the number of connected outputs
it has to drive (so-called Fan-Out)
 the speed of a circuit is affected by the number of gates in series
(on the “critical path” or the “deepest level of logic”)
 Unit of measure: FO4 = inverter with Fan-Out of 4
 P4 (heavily superpipelined) has about 15 FO4 critical path

TU/e Processor Design 5Z032 27

Multiplication (1)
 More complicated than addition
 accomplished via shifting and addition
 More time and more area
 Let's look at 3 versions based on gradeschool
algorithm

0010 (multiplicand)
__*_1011 (multiplier)

 Negative numbers: convert and multiply

 there are better techniques, we won’t look at them now

TU/e Processor Design 5Z032 28

Multiplication (2)
Start

First implementation
Product initialized to 0 Multiplier0 = 1 1. Test Multiplier0 = 0
Multiplier0

Multiplicand 1a. Add multiplicand to product and

Shift left place the result in Product register

64 bits

Multiplier 2. Shift the Multiplicand register left 1 bit

64-bit ALU Shift right
32 bits
3. Shift the Multiplier register right 1 bit
Product
Control test
Write
64 bits
No: < 32 repetitions
32nd repetition?

Yes: 32 repetitions

Done

TU/e Processor Design 5Z032 29

Multiplication (3) Start

Second version Multiplier0 = 1 1. Test

Multiplier0
Multiplier0 = 0

1a. Add multiplicand to the left half of

the product and place the result in
the left half of the Product register
Multiplicand

32 bits
2. Shift the Product register right 1 bit

Multiplier
32-bit ALU Shift right
3. Shift the Multiplier register right 1 bit
32 bits

Shift right
Product Control test No: < 32 repetitions
Write 32nd repetition?

64 bits
Yes: 32 repetitions

Done

TU/e Processor Design 5Z032 30

Multiplication (4)
Start

Final version
Product initialized with multiplier Product0 = 1 1. Test Product0 = 0
Product0

Multiplicand
1a. Add multiplicand to the left half of
the product and place the result in
32 bits the left half of the Product register

32-bit ALU
2. Shift the Product register right 1 bit

Shift right Control

Product
Write test
No: < 32 repetitions
64 bits 32nd repetition?

Yes: 32 repetitions

Done

TU/e Processor Design 5Z032 31

Sequential Circuit Multiplier The combinational array multiplier
just described uses a large number of logic gates for multiplying
numbers of practical size, such as 32- or 64-bit numbers.
Multiplication of two n-bit numbers can also be performed in a
sequential circuit that uses a single n-bit adder. The block
diagram in Figure a shows the hardware arrangement for
sequential multiplication. This circuit performs multiplication by
using a single n-bit adder n times to implement the spatial
addition performed by the n rows of ripple-carry adders in Figure

TU/e Processor Design 5Z032 32

Sequential multiplier

TU/e Processor Design 5Z032 33

Multiplication of Signed Numbers

TU/e Processor Design 5Z032 34

 Booth’s algorithm

Booth’s algorithm is a powerful algorithm that is used for signed multiplication. It generates a 2n bit product
for two n bit signed numbers.

35
 Booth’s Algorithm (2)
 Booth’s algorithm works for signed 2’s complement as
well (without any modification)
 Proof: let’s multiply b * a
(ai-1 - ai ) indicates what to do: 0 : do nothing
+1: add b
-1 : subtract
31
We get b*a =  i−1 i
( a
i =0
− a )  b  2 i
=

 30
i
b  a31  −2 +  ai  2 
31

 i =0 

This is exactly what we need !

36
Booth’s algorithm

37
 Booth’s algorithm
 Set the Multiplicand and Multiplier binary bits as M and Q, respectively.
 Initially, we set the AC and Qn + 1 registers value to 0.
 SC represents the number of Multiplier bits (Q), and it is a sequence counter that is
continuously decremented till equal to the number of bits (n) or reached to 0.
 A Qn represents the last bit of the Q, and the Qn+1 shows the incremented bit of Qn
by 1.
 On each cycle of the booth algorithm, Qn and Qn + 1 bits will be checked on the
following parameters as follows:
 When two bits Qn and Qn + 1 are 00 or 11, we simply perform the arithmetic shift
right operation (ashr) to the partial product AC. And the bits of Qn and Qn + 1 is
incremented by 1 bit.
 If the bits of Qn and Qn + 1 is shows to 01, the multiplicand bits (M) will be added
to the AC (Accumulator register). After that, we perform the right shift operation to
the AC and QR bits by 1.
 If the bits of Qn and Qn + 1 is shows to 10, the multiplicand bits (M) will be
subtracted from the AC (Accumulator register). After that, we perform the right
shift operation to the AC and QR bits by 1.
 The operation continuously works till we reached n - 1 bit in the booth algorithm.
 Results of the Multiplication binary bits will be stored in the AC and QR registers.
38
Shift operation
1. RSC (Right Shift Circular)
It shifts the right-most bit of the binary number, and then
it is added to the beginning of the binary bits.

2. RSA (Right Shift Arithmetic)

It adds the two binary bits and then shift the result to the
right by 1-bit position.
Example: 0100 + 0110 => 1010, after adding the binary
number shift each bit by 1 to the right and put the first bit
of resultant to the beginning of the new bit.
39
Exercise
 Multiply the two numbers 7 and 3 by using the
Booth's multiplication algorithm.
 Ans. Here we have two numbers, 7 and 3. First of all,
we need to convert 7 and 3 into binary numbers like 7
= (0111) and 3 = (0011). Now set 7 (in binary 0111) as
multiplicand (M) and 3 (in binary 0011) as a multiplier
(Q).
 And SC (Sequence Count) represents the number of
bits, and here we have 4 bits, so set the SC = 4.
 Also, it shows the number of iteration cycles of the
booth's algorithms and then cycles run SC = SC - 1
time.

TU/e Processor Design 5Z032 40

Example –Booth’s algorithm

TU/e Processor Design 5Z032 41

Exercise
 Multiply the two numbers 23 and -9 by using the
Booth's multiplication algorithm.
 Here, M = 23 = (010111) and Q = -9 = (110111)
 Solution: next slide

TU/e Processor Design 5Z032 42

TU/e Processor Design 5Z032 43
The Booth algorithm can also be used directly for
negative multipliers

TU/e Processor Design 5Z032 44

Booth multiplication with a
negative multiplier

TU/e Processor Design 5Z032 45

 Exercise
Problem 4: Perform signed multiplication of following 2’s
complement numbers using Booth’s algorithm.
(a) A=010111 and B=110110

(b) A=110011 and B=101100 (c) A=110101 and B=011011 (d)

A=001111 and B=001111 (e) A=10100 and B=10101 (f)
A=01110 and B=11000

TU/e Processor Design 5Z032 46

TU/e Processor Design 5Z032 47
(c) A=110101 and B=011011

TU/e Processor Design 5Z032 48

 A=001111 and B=001111
(f) A=10100 and B=10101

(d) A=001111 and B=001111

TU/e Processor Design 5Z032 49

A=01110 and B=11000

TU/e Processor Design 5Z032 50

Fast multiply: Booth’s Algorithm
 Exploit the fact that: 011111 = 100000 - 1
Therefore we can replace multiplier, e.g.:

0001111100 = 0010000000 - 100

 Rules: Current Bit to the Explanation Operation
bit right
1 0 Begin 1s Subtract
multiplicand
1 1 Middle of 1s nothing

0 1 End of 1s Add
multiplicand
0 0 Middle of 0s nothing

TU/e Processor Design 5Z032 51

Modified Booth’s algorithm

TU/e Processor Design 5Z032 52

Divide (1)
 Well known algorithm:

Dividend
Divisor 1000/1001010\1001 Quotient
-1000
10
101
1010
-1000
10 Remainder

TU/e Processor Design 5Z032 53

 Start

Division (2)
1. Substract the Divisor register from the
Remainder register and place the
result in the Remainder register
 Implementation:
>= 0 <0
Test Remainder

2.a Shift the Quotient register 2.b Restore the original value by
to the left, setting the adding the Divisor register. Also,
rightmost bit to 1 shift a 1 into the Quotient register

Divisor
Shift right Shift Divisor Register right 1 bit
64 bits

Quotient no
64-bit ALU
Shift left 33rd repetition?
32 bits

Remainder Control test

yes
Write
64 bits
Done

TU/e Processor Design 5Z032 54

 Non-Restoring Division Algorithm for Unsigned Integer
 Instead of the quotient digit set {0, 1}, the set {-1, 1} is
used by the non-restoring division. The non-restoring
division algorithm is more complex as compared to the
restoring division algorithm. But when we implement this
algorithm in hardware, it has an advantage, i.e., it
contains only one decision and addition/subtraction per
quotient bit. After performing the subtraction operation,
there will not be any restoring steps. Due to this, the
numbers of operations basically cut down up to half.
Because of the less operation, the execution of this
algorithm will be fast. This algorithm basically performs
simple operations such as addition, subtraction. In this
method, we will use the sign bit of register A. 0 is the
starting value/bit of register A.

55
Non –Restoring Division algorithm

TU/e Processor Design 5Z032 56

Example non restoring division
 Divide 11/3 using non restoring division algorithm

 Dividend = 11
 Divisor = 3
 -M = 11101

TU/e Processor Design 5Z032 57

Non restoring division algorithm

TU/e Processor Design 5Z032 58

The Restoring Division Algorithm
 The Restoring Division Algorithm is a method used to
perform division operations on unsigned integers in
computer arithmetic. It's designed to efficiently
compute the quotient and remainder when dividing
one unsigned integer (dividend) by another (divisor),
while also minimizing the number of computational
steps.

TU/e Processor Design 5Z032 59

Restoring division algorithm

TU/e Processor Design 5Z032 60

Exercise

 Divide using restoring division algorithm for the

numbers 11 and 3, where 11 is the dividend and 3 is
the divisor.

TU/e Processor Design 5Z032 61

TU/e Processor Design 5Z032 62
Floating Point (a brief look)
 We need a way to represent
 numbers with fractions, e.g., 3.1416
 very small numbers, e.g., .000000001
 very large numbers, e.g., 3.15576  109
 Representation:
 sign, exponent, significand: (–1)sign  significand  2exponent
 more bits for significand gives more accuracy
 more bits for exponent increases range
 IEEE 754 floating point standard:
 single precision : 8 bit exponent, 23 bit significand
 double precision: 11 bit exponent, 52 bit significand

TU/e Processor Design 5Z032 63

IEEE 754 floating-point standard
 Leading “1” bit of significand is implicit

 Exponent is “biased” to make sorting easier

 all 0s is smallest exponent all 1s is largest
 bias of 127 for single precision and 1023 for double precision
 summary: (–1)sign  (+significand)  2exponent – bias

 Example:
 decimal: -.75 = -3/4 = -3/22
 binary : -.11 = -1.1 x 2-1
 floating point: exponent = -1+bias = 126 = 01111110
 IEEE single precision:
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0000000000

TU/e Processor Design 5Z032 64

Floating Point Complexities
 Operations more complicated: align, renormalize, ...
 In addition to overflow we can have “underflow”
 Accuracy can be a big problem
 IEEE 754 keeps two extra bits, guard and round, and additional
sticky bit (indicating if one of the remaining bits unequal zero)
 four rounding modes
 positive divided by zero yields “infinity”
 zero divide by zero yields “not a number”
 other complexities
 Implementing the standard can be tricky
 Not using the standard can be even worse
 see text for description of 80x86 and Pentium bug!
TU/e Processor Design 5Z032 65
Floating Point on MIPS
 Separate register file for floats: 32 single precision
registers; can be used as 16 doubles
 MIPS-1 floating point instruction set (pg 288/291)
 addition add.f (f =s (single) or f=d (double))
 subtraction sub.f
 multiplication mul.f
 division div.f
 comparison c.x.f where x=eq, neq, lt, le, gt or ge
 sets a bit in (implicit) condition reg. to true or false

 branch bc1t (branch if true) and bclf (branch if false)

 c1 means instruction from coprocessor one !

 load and store: lwc1, swc1

 Study examples on page 293, and 294-296

TU/e Processor Design 5Z032 66

Floating Point on MIPS
 MIPS has 32 single-precision FP registers ($f0,$f1,
…,$f31) or 16 double-precision ($f0,$f2,...)
 MIPS FP instructions:
FP add single add.s $f0,$f1,$f2 $f0 = $f1+$f2
FP substract single sub.s $f0,$f1,$f2 $f0 = $f1-$f2
FP multiply single mul.s $f0,$f1,$f2 $f0 = $f1x$f2
FP divide single div.s $f0,$f1,$f2 $f0 = $f1/$f2
FP add double add.d $f0,$f2,$f4 $f0 = $f2+$f4
FP substract double sub.d $f0,$f2,$f4 $f0 = $f2-$f4
FP multiply double mul.d $f0,$f2,$f4 $f0 = $f2x$f4
FP divide double div.d $f0,$f2,$f4 $f0 = $f2/$f4
load word coprocessor 1 lwc1 $f0,100($s1) $f0 = Memory[$s1+100]
store word coprocessor 1 swc1 $f0,100($s1) Memory[$s1+100] = $f0
branch on copr.1 true bc1t 25 if (cond) goto PC+4+100
branch on copr.1 false bc1f 25 if (!cond) goto PC+4+100
FP compare single [Link].s $f0,$f1 cond = ($f0 < $f1)
FP compare double [Link].d $f0,$f2 cond = ($f0 >= $f2)
TU/e Processor Design 5Z032 67
 Conversion: decimal  IEEE 754 FP
 Decimal number (base 10)
123.456 = 1x102+2x101+3x100+4x10-1+5x10-2+6x10-3
 Binary number (base 2)
101.011 = 1x22+0x21+1x20+0x2-1+1x2-2+1x2-3
 Example conversion: 5.375
 Multiply with power of 2, to get rid of fraction:
5.375 = 5.375x16 / 16 = 86 x 2-4
 Convert to binary, and normalize to [Link]
86 x 2-4 = 1010110 x 2-4 = 1.01011 x 22
 Add bias (127 for single precision) to exponent:
exponent field = 2 + 127 = 129 = 1000 0001
 IEEE single precision format (remind the leading “1” bit):
0 10000001 01011000000000000000000
sign exponent significand

TU/e Processor Design 5Z032 68

Summary
 Computer arithmetic is constrained by limited precision
 Bit patterns have no inherent meaning but standards do exist
 two’s complement
 IEEE 754 floating point

 Computer instructions determine “meaning” of the bit patterns

 Performance and accuracy are important so there are many

complexities in real machines (i.e., algorithms and
implementation).

 We are ready to move on (and implement the processor)

you may want to look back (Section 4.12 is great reading!)

TU/e Processor Design 5Z032 69