复旦大学：《计算机原理 Computer System》课程PPT课件_Integer Operations; Floating Points

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