15-213“The course that gives CMU its Zip!”Topics• Basic operations–Addition, negation, multiplication• Programming Implications–Consequences of overflow–Using shifts to perform power-of-2multiply/divideCS 213 F’00class04.pptInteger Arithmetic OperationsSept. 7, 2000CS 213 F’00– 2 –class04.pptC 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• x < 0 ⇒ ((x*2) < 0)• ux >= 0• x & 7 == 7 ⇒ (x<<30) < 0• ux > -1• x > y ⇒ -x < -y• x * x >= 0• x > 0 && y > 0 ⇒ x + y > 0• x >= 0 ⇒ -x <= 0• x <= 0 ⇒ -x >= 0int x = foo();int y = bar();unsigned ux = x;unsigned uy = y;InitializationCS 213 F’00– 3 –class04.pptUnsigned AdditionStandard Addition Function• Ignores carry outputImplements Modular Arithmetics = UAddw(u , v) = u + v mod 2wUAdd u vu v u vu v u vwww w( , ) =+ + <+ − + ≥22 2• • •• • •uv+• • •u + v• • •True Sum: w+1 bitsOperands: w bitsDiscard Carry: w bitsUAddw(u , v)CS 213 F’00– 4 –class04.ppt012345678910111213141502468101214051015202530Visualizing Integer AdditionInteger Addition• 4-bit integers uand v• Compute truesum Add4(u , v)• Values increaselinearly with u andv• Forms planarsurfaceAdd4(u , v)uvCS 213 F’00– 5 –class04.ppt0123456789101112131415024681012140246810121416Visualizing Unsigned AdditionWraps Around• If true sum ≥ 2w• At most once02w2w+1UAdd4(u , v)uvTrue SumModular SumOverflowOverflowCS 213 F’00– 6 –class04.pptMathematical PropertiesModular Addition Forms an Abelian Group• Closed under addition0 ≤ UAddw(u , v) ≤ 2w –1• CommutativeUAddw(u , v) = UAddw(v , u)• AssociativeUAddw(t, UAddw(u , v)) = UAddw(UAddw(t, u ), v)• 0 is additive identityUAddw(u , 0) = u• Every element has additive inverse–Let UCompw (u ) = 2w – uUAddw(u , UCompw (u )) = 0CS 213 F’00– 7 –class04.pptDetecting Unsigned OverflowTask• Given s = UAddw(u , v)• Determine if s = u + vApplicationunsigned s, u, v;s = u + v;• Did addition overflow?Claim• Overflow iff s < uovf = (s < u)• Or symmetrically iff s < vProof• Know that 0 ≤ v < 2w• No overflow ⇒ s = u + v ≥ u + 0 = u• Overflow ⇒ s = u + v – 2w< u + 0 = uu v2wsu v2wsNo OverflowOverflowCS 213 F’00– 8 –class04.pptTwo’s Complement AdditionTAdd 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• • •• • •uv+• • •u + v• • •True Sum: w+1 bitsOperands: w bitsDiscard Carry: w bitsTAddw(u , v)CS 213 F’00– 9 –class04.pptCharacterizing TAddFunctionality• True sum requires w+1bits• Drop off MSB• Treat remaining bits as2’s comp. integer–2w –1–2w02w –12w–1True SumTAdd Result1 000…01 100…00 000…00 100…00 111…1100…0000…0011…1PosOverNegOverTAddw(u,v)=u+v+2wu+v<TMinwu+v TMinw≤u+v≤TMaxwu+v−2wTMaxw<u+v (NegOver)(PosOver)uv< 0 > 0< 0> 0NegOverPosOverTAdd(u , v)CS 213 F’00– 10 –class04.ppt-8-7-6-5-4-3-2-101234567-8-6-4-20246-8-6-4-202468Visualizing 2’s Comp. AdditionValues• 4-bit two’scomp.• Range from -8to +7Wraps Around• If sum ≥ 2w–1–Becomesnegative–At most once• If sum < –2w–1–Becomespositive–At most onceTAdd4(u , v)uvPosOverNegOverCS 213 F’00– 11 –class04.pptDetecting 2’s Comp. OverflowTask• Given s = TAddw(u , v)• Determine if s = Addw(u , v)• Exampleint s, u, v;s = u + v;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);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 TAdd02w –12w–1PosOverNegOverCS 213 F’00– 12 –class04.pptMathematical Properties of TAddIsomorphic Algebra to UAdd• TAddw(u , v) = U2T(UAddw(T2U(u ), T2U(v)))–Since both have identical bit patternsTwo’s Complement Under TAdd Forms a Group• Closed, Commutative, Associative, 0 is additive identity• Every element has additive inverseLet TCompw (u ) = U2T(UCompw(T2U(u ))TAddw(u , TCompw (u )) = 0TComp uu u TMinTMin u TMinwww w( ) =− ≠=CS 213 F’00– 13 –class04.pptTwo’s Complement NegationMostly like Integer Negation• TComp(u) = –uTMin is Special Case• TComp(TMin) = TMinNegation in C is ActuallyTComp mx = -x• mx = TComp(x)• Computes additive inversefor TAdd x + -x == 01000100110101011110011011110111100000001001000110100010101100111–2w–12w–1–2w–12w–1uTcomp(u )CS 213 F’00– 14 –class04.pptNegating with Complement & IncrementIn C ~x + 1 == -xComplement• Observation: ~x + x == 1111…112 == -1Increment• ~x + x + (-x + 1) == -1 + (-x + 1)• ~x + 1 == -xWarning: Be cautious treating int’s as integers• OK here: We are using group properties of TAdd and TComp1 0 0 1 0 11 1 x0 1 1 0 1 00 0~x+1 1 1 1 1 11 1-1CS 213 F’00– 15 –class04.pptComp. & Incr. ExamplesDecimal Hex BinaryTMin-3276880 0010000000 00000000~TMin327677F FF01111111 11111111~TMin+1-3276880 0010000000 00000000DecimalHex Binaryx152133B 6D00111011 01101101~x-15214C4 9211000100 10010010~x+1-15213C4 9311000100 10010011y-15213C4 9311000100 10010011TMinx = 15213Decimal Hex Binary0000 0000000000 00000000~0-1FF FF11111111 11111111~0+1000 0000000000 000000000CS 213 F’00– 16 –class04.pptComparing Two’s Complement NumbersTask• Given signed numbers u, v• Determine whether or not u > v–Return 1 for numbers in shaded region belowBad Approach• Test (u–v) > 0–TSub(u,v) = TAdd(u, TComp(v))• Problem: Thrown off by either Negative or Positive Overflowuv< 0 > 0< 0> 0u < vu > vu==vCS 213 F’00– 17 –class04.ppt-8-7-6-5-4-3-2-101234567-8-6-4-20246-8-6-4-202468Comparing with TSubWill Get Wrong Results• NegOver: u < 0, v > 0–but u-v > 0• PosOver: u > 0, v < 0–but u-v < 0uv< 0 > 0< 0> 0u-v+--+++--NegOverPosOverTSub4(u , v)uvPosOverNegOverCS 213 F’00– 18 –class04.pptWorking Around Overflow ProblemsPartition into Three Regions• u < 0, v ≥ 0 ⇒ u < vuv< 0≥ 0< 0≥ 0u<0v≥0• u ≥ 0, v < 0 ⇒ u > v• u, v same sign ⇒ u-v does not overflow–Can safely use test (u–v) > 0v< 0≥ 0< 0≥ 0u≥0v<0uv< 0≥ 0< 0≥ 0u<0v<0u≥0v≥0uuv< 0≥
View Full Document
Unlocking...