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+p2 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: 取模
Unsigned Addition Forms an Abelian Group P68 Closed under addition 0≤ UAdduu,v)≤2w-1 Commutative(交换律) Add(,)=∪Add(v,u) Associative(结合律) UAddw(t, UAddw(u, v)=UAddwqUAddw(t,u,v
6 Unsigned Addition Forms an Abelian Group P68 • Closed under addition – 0 UAddw(u , v) 2 w –1 • Commutative （交换律） – UAddw(u , v) = UAddw(v , u) • Associative （结合律） – UAddw (t, UAddw (u,v)) = UAddw (UAddw (t, u ), v)
Unsigned Addition Forms an Abelian Group o is additive identity UAddw u,o) Every element has additive inverse Let UCompw(u)=2w-u P68(2.10) UAddw(u, UCompw(u))=0
7 Unsigned Addition Forms an Abelian Group • 0 is additive identity – UAddw (u , 0) = u • Every element has additive inverse – Let UCompw (u ) = 2 w – u – UAddw(u , UCompw (u )) = 0 P68 （2.10）
Signed Addition Functionality True sum requires w+l bits Drop off msB Treat remaining bits as 2s comp. integer u+v-2", TMax <u+v(PosOver) Tadd (u, v) 1+V,TMin,≤l+v≤Mamx P70(2.12) u+v+2, u+v<TMin(NegOver PosOver: Positive Overflow NegOver: Negative Overflow
8 Signed Addition • Functionality – True sum requires w+1 bits – Drop off MSB – Treat remaining bits as 2’s comp. integer + + + + + + − + = 2 , ( ) , 2 , ( ) ( , ) u v u v TMin NegOver u v TMin u v TMax u v TMax u v PosOver Tadd u v w w w w w w PosOver：Positive Overflow NegOver：Negative Overflow P70 （2.12）
Signed Addition P70 Figure 2.17 True sum PosOver TAdd(u, v) 0111.1 PosOver TAdd Result 0100..0 2W-1 011.1 <0 0000.00 000..0 NegOver 11000-2-1 100..0 1000..0-2W NegOvel
9 Signed Addition P70 Figure 2.17 u v 0 0 NegOver PosOver TAdd(u , v) –2 w –1 –2 w 0 2 w –1 2 w–1 True Sum TAdd Result 1 000…0 1 100…0 0 000…0 0 100…0 0 111…1 100…0 000…0 011…1 PosOver NegOver
Visualizing 2s Comp. Addition Values 4-bit twos comp. Range from -8 to +7 Wraps Around If sum≥2W-1 Becomes negative If sum <-2W1 Becomes positive
10 Visualizing 2’s Comp. Addition • Values – 4-bit two’s comp. – Range from -8 to +7 • Wraps Around – If sum 2 w-1 • Becomes negative – If sum < –2 w–1 • Becomes positive