15 213 The course that gives CMU its Zip Integer Arithmetic Operations Sept 7 2000 Topics Basic operations Addition negation multiplication Programming Implications Consequences of overflow Using shifts to perform power of 2 multiply divide class04 ppt CS 213 F 00 C Puzzles Assume machine with 32 bit word size two s complement integers For each of the following C expressions either Argue that is true for all argument values Give example where not true Initialization x 2 0 x 7 7 x 30 0 x 0 ux 0 int x foo int y bar ux 1 unsigned ux x x y unsigned uy y x y x x 0 x 0 y 0 class04 ppt x y 0 x 0 x 0 x 0 x 0 2 CS 213 F 00 Unsigned Addition u v u v UAddw u v Operands w bits True Sum w 1 bits Discard Carry w bits Standard Addition Function Ignores carry output Implements Modular Arithmetic s UAddw u v u v mod 2w u v UAddw u v w u v 2 class04 ppt 3 u v 2w u v 2w CS 213 F 00 Visualizing Integer Addition Integer Addition 4 bit integers u and v Compute true sum Add4 u v Values increase linearly with u and v Forms planar surface Add4 u v 30 25 20 15 14 12 10 10 8 5 6 v 4 0 0 1 2 3 4 u class04 ppt 4 2 5 6 7 8 0 9 10 11 12 13 14 15 CS 213 F 00 Visualizing Unsigned Addition Wraps Around Overflow If true sum 2w At most once UAdd4 u v 16 True Sum 2w 1 14 12 Overflow 10 2w 8 14 6 12 10 4 0 Modular Sum 8 6 2 4 0 0 1 2 3 4 u class04 ppt v 2 5 6 5 7 8 0 9 10 11 12 13 14 15 CS 213 F 00 Mathematical Properties Modular Addition Forms an Abelian Group Closed under addition 0 UAddw u v 2w 1 Commutative UAddw u v UAddw v u Associative UAddw t UAddw u v UAddw UAddw t u v 0 is additive identity UAddw u 0 u Every element has additive inverse Let UCompw u 2w u UAddw u UCompw u 0 class04 ppt 6 CS 213 F 00 Detecting Unsigned Overflow Task No Overflow Given s UAddw u v Determine if s u v u Application v s unsigned s u v s u v Did addition overflow 2w Overflow u Claim v s Overflow iff s u ovf s u Or symmetrically iff s v 2w Proof Know that 0 v 2w No overflow s u v Overflow s u v 2w class04 ppt 7 u 0 u u 0 u CS 213 F 00 Two s Complement Addition u v u v TAddw u v Operands w bits True Sum w 1 bits Discard Carry w bits TAdd and UAdd have Identical Bit Level Behavior Signed vs unsigned addition in C int s t u v s int unsigned u unsigned v t u v Will give s t class04 ppt 8 CS 213 F 00 Characterizing TAdd Functionality True Sum True sum requires w 1 bits Drop off MSB Treat remaining bits as 2 s comp integer 0 111 1 2w 1 PosOver TAdd Result 0 100 0 2w 1 011 1 0 000 0 0 000 0 PosOver TAdd u v 0 v 0 0 u 0 NegOver class04 ppt 1 100 0 2w 1 1 000 0 2w 100 0 NegOver u v 2 w u v TMin w NegOver TAddw u v u v TMinw u v TMax w u v 2 w TMax w u v PosOver 9 CS 213 F 00 Visualizing 2 s Comp Addition Values 4 bit two s comp Range from 8 to 7 Wraps Around If sum 2w 1 Becomes negative At most once If sum 2w 1 Becomes positive At most once class04 ppt NegOver TAdd4 u v 8 6 4 2 0 6 2 4 2 4 0 2 6 4 8 8 7 6 5 4 3 2 1 0 u 10 6 1 2 3 4 5 v 8 6 7 CS 213 F 00 PosOver Detecting 2 s Comp Overflow Task Given s TAddw u v Determine if s Addw u v Example int s u v s u v 2w 1 PosOver 2w 1 0 Claim Overflow iff either u v 0 s 0 NegOver u v 0 s 0 PosOver ovf u 0 v 0 u 0 s 0 NegOver Proof Easy to see that if u 0 and v 0 then TMinw u v TMaxw Symmetrically if u 0 and v 0 Other cases from analysis of TAdd class04 ppt 11 CS 213 F 00 Mathematical Properties of TAdd Isomorphic Algebra to UAdd TAddw u v U2T UAddw T2U u T2U v Since both have identical bit patterns Two s Complement Under TAdd Forms a Group Closed Commutative Associative 0 is additive identity Every element has additive inverse Let TCompw u U2T UCompw T2U u TAddw u TCompw u 0 u TCompw u TMinw class04 ppt 12 u TMinw u TMinw CS 213 F 00 Two s Complement Negation Mostly like Integer Negation TComp u u 2w 1 TMin is Special Case TComp TMin TMin Negation in C is Actually TComp mx x mx TComp x Computes additive inverse for TAdd x x 0 Tcomp u 2w 1 2w 1 2w 1 1001 1000 1011 1010 1101 1100 1110 1111 0001 0000 0011 0010 0101 0100 0110 u class04 ppt 13 0111 CS 213 F 00 Negating with Complement Increment In C x 1 x Complement Observation x x 1111 112 1 x 10011101 x 01100010 1 11111111 Increment x x x 1 x 1 1 x 1 x Warning Be cautious treating int s as integers OK here We are using group properties of TAdd and TComp class04 ppt 14 CS 213 F 00 Comp Incr Examples x 15213 Decimal x 15213 x 15214 x 1 15213 y 15213 Hex 3B 6D C4 92 C4 93 C4 93 Binary 00111011 01101101 11000100 10010010 11000100 10010011 11000100 10010011 TMin TMin TMin TMin 1 Decimal 32768 32767 32768 Hex 80 00 7F FF 80 00 Binary 10000000 00000000 01111111 11111111 10000000 00000000 0 0 0 1 Decimal 0 1 0 Hex 00 00 FF FF 00 00 Binary 00000000 00000000 11111111 11111111 00000000 00000000 0 class04 ppt 15 CS 213 F 00 Comparing Two s Complement Numbers Task Given signed numbers u v Determine whether or not u v Return 1 for numbers in shaded region below u v 0 v 0 u v 0 Bad Approach u v 0 u Test u v 0 TSub u v TAdd u TComp v Problem Thrown off by either Negative or Positive Overflow class04 ppt 16 CS 213 F 00 Comparing with TSub Will Get Wrong Results NegOver u 0 v 0 but u v 0 PosOver u 0 v 0 but u v 0 NegOver TSub4 u v 8 6 NegOver 4 u v 0 v …
View Full Document
Unlocking...