Computer Organization & Architecture

Chapter 8

Computer Arithmetic

Muhammad Yousaf
Assistant Professor, Faculty of Computing,
Riphah International University (RIU),
Islamabad
Arithmetic & Logic Unit (ALU)
• ALU performs the calculations
• Everything else in the computer is to
serve ALU
• Handles integers
• May handle floating point (real) numbers
• May be separate (Floating Point Unit) FPU
—Maths co-processor
• May be on-chip FPU (486DX +)

muhammad.yousaf@riu.edu.pk 2
ALU Inputs and Outputs

muhammad.yousaf@riu.edu.pk 3
Integer Representation
• Only have 0 & 1 to represent everything
• Positive numbers stored in binary
—e.g. 41=00101001
• No minus sign
• No period sign
• Sign-Magnitude representation
• Two’s complement representation

muhammad.yousaf@riu.edu.pk 4
Sign-Magnitude
• Left most bit is sign bit
• 0 means positive
• 1 means negative
• +18 = 00010010
• -18 = 10010010
• Problems
—Need to consider both sign and magnitude in
arithmetic
—Two representations of zero (+0 and -0)

muhammad.yousaf@riu.edu.pk 5
Two’s Complement
• +3 = 00000011
• +2 = 00000010
• +1 = 00000001
• +0 = 00000000
• -1 = 11111111
• -2 = 11111110
• -3 = 11111101

muhammad.yousaf@riu.edu.pk 6
Comparison of Representations

muhammad.yousaf@riu.edu.pk 7
Two’s Compliment

muhammad.yousaf@riu.edu.pk 8
Benefits
• One representation of zero
• Arithmetic works easily (see later)
• Negating is fairly easy
— 3 = 00000011
— Boolean complement gives 11111100
— Add 1 to LSB 11111101
— -3 = 11111101

muhammad.yousaf@riu.edu.pk 9
Geometric Depiction of Two’s
Complement Integers

muhammad.yousaf@riu.edu.pk 10
Negation Special Case (0 = -0)
• 0= 00000000
• Bitwise not 11111111
• Add 1 to LSB +1
• Result 1 00000000
• Overflow is ignored, so:
• -0=0

muhammad.yousaf@riu.edu.pk 11
Negation Special Case (- -128 = -128)
• -128 = 10000000
• bitwise not 01111111
• Add 1 to LSB +1
• Result 10000000
• So:
• -(-128) = -128 X

• Monitor MSB (sign bit)

—It should change during negation

muhammad.yousaf@riu.edu.pk 12
Range of Numbers
• 8 bit 2s compliment
—Max: +127 = 01111111 = 27 -1
—Min: -128 = 10000000 = -27

• 16 bit 2s compliment
—+32767 = 01111111 11111111 = 215 - 1
— -32768 = 10000000 00000000 = -215

muhammad.yousaf@riu.edu.pk 13
Conversion Between Lengths
• Positive number pack with leading zeros
• +18 = 00010010
• +18 = 00000000 00010010

• Negative numbers pack with leading ones

• -110 = 10010010
• -110 = 11111111 10010010
—i.e. pack with MSB (sign bit)

muhammad.yousaf@riu.edu.pk 14
Addition and Subtraction
• Normal binary addition
• Monitor sign bit for overflow

• Take twos compliment of subtrahend and

add to minuend
—i.e. a - b = a + (-b)

• In hardware, we only need addition and

complement circuits

muhammad.yousaf@riu.edu.pk 15
Hardware for Addition and Subtraction

muhammad.yousaf@riu.edu.pk 16
Addition in 2’s Complement & Overflow

muhammad.yousaf@riu.edu.pk 17
Subtraction in 2’s Complement

muhammad.yousaf@riu.edu.pk 18
Logical Shift Operations

• Logical Shift Left

— Zero inserted in LSB
— 46=23<<1
— Effect: Multiply by 2

• Logical Shift Right

— Zero inserted in MSB
— 11=23>>1
— Effect: Divide by 2

muhammad.yousaf@riu.edu.pk Source: http://en.wikipedia.org/wiki/Logical_shift (23-11-2010) 19

Arithmetic Shift Operations
• More useful for signed arithmetic
• Arithmetic Shift Left
— Same as logical shift left

• Arithmetic Shift Right

— Sign bit replicated in MSB
— 11=23>>1 (Round Down)
— Effect: Divide by 2
• For signed numbers
— 11101001=-23
— 11110100=-12
— -12=-23>>1 (Round Down)

muhammad.yousaf@riu.edu.pk Source: http://en.wikipedia.org/wiki/Arithmetic_shift (23-11-2010) 20

Multiplication
• Complex
• Work out partial product for each digit
• Take care with place value (column)
• Add partial products

muhammad.yousaf@riu.edu.pk 21
Multiplication Example
• 1011 Multiplicand (decimal 11)
• x 1101 Multiplier (decimal 13)
• 1011 Partial products
• 0 000x Note: if multiplier bit is 1,
• 10 11xx copy multiplicand
otherwise zero
• 101 1xxx
• 1000 1111 Product (11x13=143 decimal)

—Note: length of product is the sum of lengths

of multiplicand and multiplier
—4-bits x 4-bits => 8-bits answer
muhammad.yousaf@riu.edu.pk 22
Unsigned Binary Multiplication

muhammad.yousaf@riu.edu.pk 23
Execution of Example

* Add: A=A+M Shift: Logical Shift Right 24

muhammad.yousaf@riu.edu.pk
Multiplying Negative Numbers
• This does not work!
• Solution 1
—Convert to positive if required
—Multiply as above
—If signs were different, negate answer
• Solution 2
—Booth’s algorithm

muhammad.yousaf@riu.edu.pk 25
Booth’s Algorithm

muhammad.yousaf@riu.edu.pk 26
Example of Booth’s Algorithm

* Shift: Arithmetic Shift Right i.e. sign bit is replicated 27

muhammad.yousaf@riu.edu.pk
Division
• More complex than multiplication
• Negative numbers are really bad!
• Based on long division

muhammad.yousaf@riu.edu.pk 28
Division of Unsigned Binary Integers
* 147/11=> Q=13 ; R=04
1101 Quotient
Divisor 1011 10010011 Dividend
1011
001110
1011
001111
1011
100 Remainder
Addition Negation
10010 01011
10101 10100
+ 1
00111 10101 29
muhammad.yousaf@riu.edu.pk
Flowchart for Unsigned Binary Division

muhammad.yousaf@riu.edu.pk 31
Real Numbers
• Numbers with fractions
• Can be represented in binary form
—1001.1010 = 23 + 20 +2-1 + 2-3 =9.625
—2-1 = ½ = 0.500
—2-3 = 1/8 = 0.125
• Where is the binary point?
• Fixed?
—Very limited
• Moving?
—How do you show where it is?

muhammad.yousaf@riu.edu.pk 32
Floating Point

• (+/-) (1.significand) x (2exponent)

• Floating Point is Misnomer
— Point is actually fixed between sign bit and body of
significant
• Exponent indicates the point position

muhammad.yousaf@riu.edu.pk 33
Floating Point Examples

Binary FP FP Storage Decimal FP

20+127=147 147-127=20

107-127= - 20
- 20+127=107

1/2=0.5000000
1/8=0.1250000
1/128=0.0078125
Result=0.6328125
muhammad.yousaf@riu.edu.pk 34
Signs for Floating Point
• Mantissa (significant) is stored in 2’s
compliment
• Exponent is in biased notation
—e.g. Bias of Excess 127=((2^8)-1)
—For 8 bit exponent field, range is 0-255
— Subtract 127 to get correct value
—Range -127 to +128
– Min: 0-127=-127
– Max: 255-127=128

muhammad.yousaf@riu.edu.pk 35
Normalization
• FP numbers are usually normalized
—i.e. exponent is adjusted so that leading bit
(MSB) of mantissa is 1
• Since MSB is always 1, there is no need to
store it
— Scientific notation
—where numbers are normalized to give a
single digit before the decimal point
—e.g. 3.123 x 103

muhammad.yousaf@riu.edu.pk 36
FP Ranges
• For a 32 bit number
—8 bit exponent
—+/- 2256  1.15 x 1077
• Accuracy
—The effect of changing LSB of mantissa
—23 bit mantissa 2-23  1.2 x 10-7
—About 6 decimal places

muhammad.yousaf@riu.edu.pk 37
IEEE 754 Standard
• IEEE Standard for Floating-Point
Arithmetic
—IEEE 754-1985
—IEEE 754-2008

• Standard for floating point storage

• 32 and 64 bit standards
• 8 and 11 bit exponent respectively

muhammad.yousaf@riu.edu.pk 38
IEEE 754 Formats

(32-bits)

(64-bits)

muhammad.yousaf@riu.edu.pk 39
FP Arithmetic +/-
• Check for zeros
• Align significands (adjusting exponents)
• Add or subtract significands
• Normalize result

muhammad.yousaf@riu.edu.pk 40
FP Arithmetic x/
• Check for zero
• Add/subtract exponents
• Multiply/divide significands (watch sign)
• Normalize
• Round
—All intermediate results should be in double
length storage

muhammad.yousaf@riu.edu.pk 41
 Questions ???

muhammad.yousaf@riu.edu.pk 42