Integer Operations
1 Integer Operations
Outline Arithmetic operations overflow Unsigned addition, multiplication Signed addition, negation, multiplication Using Shift to perform power-of-2 multiply/divide Suggested read 1g Chap 2.3 Negation:取反
2 Outline • Arithmetic Operations – overflow – Unsigned addition, multiplication – Signed addition, negation, multiplication – Using Shift to perform power-of-2 multiply/divide • Suggested reading – Chap 2.3 Negation：取反
Unsigned Addition Operands: w bits 上: True Sum w+1 bits uty Discard Carry: w bits UAdd,(u, v)
3 Unsigned Addition • • • • • • u + v • • • u + v • • • True Sum: w+1 bits Operands: w bits Discard Carry: w bits UAddw(u , v)
Unsigned Addition Standard Addition Function Ignores carry output Implements Modular Arithmetic S= UAddwu, v=u+v mod 2W L+1 L1+p<2 UAdd(u,v) 1+y-2L+p>2 P67(2.9)
4 Unsigned Addition • Standard Addition Function – Ignores carry output • Implements Modular Arithmetic – s = UAddw(u , v) = (u + v) mod 2w UAddw(u,v) = u + v u + v 2 w u + v − 2 w u + v 2 w P67 (2.9)
Visualizing Unsigned Addition P68 Figure 2.16 Overflow Wraps around If true sum≥2Ww Addu, v) At most once True Sum 2 W+1 Overflow 64208 0 Modular sum Module:取模
5 Visualizing Unsigned Addition P68 Figure 2.16 • Wraps Around – If true sum ≥ 2w – At most once 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 16 UAdd4 (u , v) u v Overflow 0 2 w 2 w+1 True Sum Modular Sum Overflow Module: 取模