Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS4203/EE4363
Arithmetic for Computers
• Operations on integers
• Addition and subtraction
• Multiplication and division
• Dealing with overflow
• Floating-point real numbers
• Representation and operations
Addition/Subtraction in Binary with Negative Number
Decimal: 0 - 1 = -1
Hexadecimal: 0 - 1 = -1
Binary: 0000 + 0001 =1111
Decimal: -1 + 1 = 0
Hexadecimal: -1 + 1 = 0
Binary: 1111 + 0001 =0000
Decimal: -1 - 1 = -2
Hexadecimal: -1 - 1 = -2
Binary: 1111 - 0001 =1110
2’s-Complement Integers
• Negation rule:
• Invert bits and add 1
• Some properties:
• Only one representation for 0
• Exactly as many positive numbers as negative numbers
• Slight asymmetry – there is one negative number with no
positive counterpart
2’s Complement Addition
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
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
Problems with Finite Math
• Finite size of representation:
• Digital circuit cannot be arbitrarily large.
• Overflow detection – easy to determine when the
number becomes too large.
• Represent negative numbers:
• Unique representation of 0.
-4 0 4 8 12 16 20
0000 0100 1000 1100 10000 10100
Infinite
universe
of integers
∞-∞
4-bit numbers
Overflow and Finite Universe
. . .1111 0000 0001 0010 0011 0100 0101 . . .
Decrease Increase
Infinite
universe
of integers
No overflow
∞-∞
0000
Forbidden fence
1000
00011111
1001
Finite
Universe
of 4-bit
binary
integers
0010
0011
0100
0101
0110
0111
1010
1011
1100
1101
1110
In
cr
ea
se
D
ec
re
as
e
Dealing with Overflow
• Some languages (e.g., C) ignore overflow
• Use MIPS addu, addui, subu instructions
• Other languages (e.g., Ada, Fortran) require raising an
exception
• Use MIPS add, addi, sub instructions
• On overflow, invoke exception handler
• Save PC in exception program counter (EPC) register
• Jump to predefined handler address
• mfc0 (move from coprocessor reg) instruction can
retrieve EPC value, to return after corrective action
Arithmetic for Multimedia
• Graphics and media processing operates on vectors of 8-
bit and 16-bit data
• Use 64-bit adder, with partitioned carry chain
• Operate on 8×8-bit, 4×16-bit, or 2×32-bit vectors
• SIMD (single-instruction, multiple-data)
• Saturating operations
• On overflow, result is largest representable value
• c.f. 2s-complement modulo arithmetic
• E.g., clipping in audio, saturation in video
32-bit Ripple-Carry Adder
FA0
FA1
FA2
FA31
a0
b0
c0 = 0
a1
b1
a2
b2
a31
b31
s0
s1
s2
c32
(discard)
s31c31
c2
c1
c32 c31 . . . c2 c1 0
a31 . . . a2 a1 a0
+ b31 . . . b2 b1 b0
s31 . . . s2 s1 s0
Speeding Up the Adder
16-bit
ripple
carry
adder
a0-a15
b0-b15
c0 = 0
s0-s15
16-bit
ripple
carry
adder
a16-a31
b16-b31
0
16-bit
ripple
carry
adder
a16-a31
b16-b31
1
M
ul
tip
le
xe
r
s16-s31
0
1
This is a carry-select adder
N-bit Adder Design Options
Type of adder Time complexity
(delay)
Space complexity
(size)
Ripple-carry O(N) O(N)
Carry-lookahead O(log2N) O(N log2N)
Carry-skip O(√N) O(N)
Carry-select O(√N) O(N)
Multiplication
Multiplication
1000
× 1001
1000
0000
0000
1000
1001000
Length of product is the sum of operand lengths
multiplicand
multiplier
product
Combinational Multiplier
A0