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