COMPUTER ORGANIZATION AND DESIGN

5th
Edition
The Hardware/Software Interface

Chapter 3

Arithmetic for Computers

 §3.1 Introduction
Arithmetic for Computers
● Operations on integers
● Addition and subtraction
● Multiplication and division
● Dealing with overflow
● Floating-point real numbers
● Representation and operations

2
 §3.2 Addition and Subtraction
Integer Addition
● Example: 7 + 6

● Overflow if result out of range

● Adding +ve and –ve operands, no overflow
● Adding two +ve operands
● Overflow if result sign is 1
● Adding two –ve operands
● Overflow if result sign is 0

3
Integer Subtraction
● Add negation of second operand
● Example: 7 – 6 = 7 + (–6)
+7:0000 0000 … 0000 0111
–6: 1111 1111 … 1111 1010
+1: 0000 0000 … 0000 0001
● Overflow if result out of range
● Subtracting two +ve or two –ve operands, no overflow
● Subtracting +ve from –ve operand
● Overflow if result sign is 0
● Subtracting –ve from +ve operand
● Overflow if result sign is 1

4
 §3.3 Multiplication
Multiplication
● Start with long-multiplication approach
multiplicand

multiplier
1000
×
1001

1000
product
00000
Length of product is
the sum of operand
000000
lengths 1000000
1001000

5
Multiplication Hardware

Initially 0

6
 Optimized Multiplier
● Perform steps in parallel: add/shift

multiplicand
1000
multiplier × 1001
1000
initial
product 01000
001000
Shift Right
product 0001000
1000 (+)
product
1001000

● One cycle per partial-product addition

7
MIPS Multiplication
● Two 32-bit registers for product
● HI: most-significant 32 bits
● LO: least-significant 32-bits
● Instructions
● mult rs, rt / multu rs, rt
● 64-bit product in HI/LO
● mul rd, rs, rt
● Least-significant 32 bits of product –> rd

8
 §3.5 Floating Point
Floating Point
● Representation for non-integral numbers
● Including very small and very large numbers
● Like scientific notation
● –2.34 × 1056 normalized
● +0.002 × 10–4
not normalized
● +987.02 × 109
● In binary
yyyy
● ±[Link] × 2
2
● Types float and double in C

9
Floating Point Standard
● Defined by IEEE Std 754-1985
● Developed in response to divergence of
representations
● Portability issues for scientific code
● Now almost universally adopted
● Two representations
● Single precision (32-bit)
● Double precision (64-bit)

10
IEEE Floating-Point Format
single: 8 bits single: 23 bits
double: 11 bits double: 52 bits
S Exponent Fraction

● S: sign bit (0 ⇒ non-negative, 1 ⇒ negative)

● Normalize significand: 1.0 ≤ |significand| < 2.0
● Always has a leading pre-binary-point 1 bit, so no need to
represent it explicitly (hidden bit)
● Significand is Fraction with the “1.” restored
● Exponent: excess representation: actual exponent + Bias
● Ensures exponent is unsigned
● Single: Bias = 127; Double: Bias = 1023

11
Single-Precision Range
● Exponents 00000000 and 11111111 reserved
● Smallest value
● Exponent: 00000001
⇒ actual exponent = 1 – 127 = –126
● Fraction: 000…00 ⇒ significand = 1.0
● ±1.0 × 2–126 ≈ ±1.2 × 10–38
● Largest value
● exponent: 11111110
⇒ actual exponent = 254 – 127 = +127
● Fraction: 111…11 ⇒ significand ≈ 2.0
● ±2.0 × 2+127 ≈ ±3.4 × 10+38
12
Double-Precision Range
● Exponents 0000…00 and 1111…11 reserved
● Smallest value
● Exponent: 00000000001
⇒ actual exponent = 1 – 1023 = –1022
● Fraction: 000…00 ⇒ significand = 1.0
● ±1.0 × 2–1022 ≈ ±2.2 × 10–308
● Largest value
● Exponent: 11111111110
⇒ actual exponent = 2046 – 1023 = +1023
● Fraction: 111…11 ⇒ significand ≈ 2.0
● ±2.0 × 2+1023 ≈ ±1.8 × 10+308
13
Floating-Point Precision
● Relative precision
● all fraction bits are significant
● Single: approx 2–23
● Equivalent to 23 × log102 ≈ 23 × 0.3 ≈ 6 decimal
digits of precision
● Double: approx 2–52
● Equivalent to 52 × log102 ≈ 52 × 0.3 ≈ 16 decimal
digits of precision

14
Floating-Point Example
● Represent –0.75
● –0.75 = (–1)1 × 1.12 × 2–1
● S=1
● Fraction = 1000…002
● Exponent = –1 + Bias
● Single: –1 + 127 = 126 = 011111102
● Double: –1 + 1023 = 1022 = 011111111102
● Single: 1011111101000…00
● Double: 1011111111101000…00

15
Floating-Point Example
● What number is represented by the
single-precision float
11000000101000…00
● S = 1

● Fraction = 01000…00
2
● Fxponent = 10000001 = 129
2
● x = (–1)1 × (1 + 012) × 2(129 – 127)
= (–1) × 1.25 × 22
= –5.0

16
Denormal Numbers
● Exponent = 000...0 ⇒ hidden bit is 0

● Smaller than normal numbers

● allow for gradual underflow, with diminishing
precision

● Denormal with fraction = 000...0

Two representations
of 0.0!
1
7
Infinities and NaNs
● Exponent = 111...1, Fraction = 000...0
● ±Infinity
● Can be used in subsequent calculations,
avoiding need for overflow check
● Exponent = 111...1, Fraction ≠ 000...0
● Not-a-Number (NaN)
● Indicates illegal or undefined result
● e.g., 0.0 / 0.0
● Can be used in subsequent calculations

1
8
Floating-Point Addition
● Consider a 4-digit decimal example
● 9.999 × 101 + 1.610 × 10–1
● 1. Align decimal points
● Shift number with smaller exponent
● 9.999 × 101 + 0.016 × 101
● 2. Add significands
● 9.999 × 101 + 0.016 × 101 = 10.015 × 101
● 3. Normalize result & check for over/underflow
● 1.0015 × 102
● 4. Round and renormalize if necessary
● 1.002 × 102

19
Floating-Point Addition
● Now consider a 4-digit binary example
● 1.0002 × 2–1 + –1.1102 × 2–2 (0.5 + –0.4375)
● 1. Align binary points
● Shift number with smaller exponent
● 1.0002 × 2–1 + –0.1112 × 2–1
● 2. Add significands
● 1.0002 × 2–1 + –0.1112 × 2–1 = 0.0012 × 2–1
● 3. Normalize result & check for over/underflow
● 1.0002 × 2–4, with no over/underflow
● 4. Round and renormalize if necessary
● 1.0002 × 2–4 (no change) = 0.0625

20
FP Adder Hardware
● Much more complex than integer adder
● Doing it in one clock cycle would take too
long
● Much longer than integer operations
● Slower clock would penalize all instructions
● FP adder usually takes several cycles
● Can be pipelined

21
FP Adder Hardware

Step 1

Step 2

Step 3

Step 4

22