15-213“The course that gives CMU its Zip!”Topics• Numeric Encodings–Unsigned & Two’s complement• Programming Implications–C promotion rules• Basic operations–Addition, negation, multiplication• Programming Implications–Consequences of overflow–Using shifts to perform power-of-2 multiply/divideCS 213 F’01class03.pptIntegersSep 4, 2001In-Class Handout VersionCS 213 F’01– 2 –class03.pptC Puzzles• Taken from Exam #2, CS 347, Spring ‘97• 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’01– 3 –class03.pptEncoding Integers short int x = 15213; short int y = -15213;• C short 2 bytes longSign Bit• For 2’s complement, most significant bit indicates sign–0 for nonnegative–1 for negativeB T X x xwwiiiw2 2 21102( ) = − ⋅ + ⋅−−=−∑B U X xiiiw2 201( ) = ⋅=−∑UnsignedTwo’s ComplementSignBitDecimal Hex Binaryx152133B 6D00111011 01101101y-15213C4 9311000100 10010011CS 213 F’01– 4 –class03.pptEncoding Example (Cont.) x = 15213: 00111011 01101101 y = -15213: 11000100 10010011Weight15213 -1521311111200124140081800160011632132006416400128001128256125600512151200102400110242048120480040961409600819218192001638400116384-32768001-32768Sum15213-15213CS 213 F’01– 5 –class03.pptNumeric RangesUnsigned Values• UMin = 0000…0• UMax = 2w – 1111…1Two’s Complement Values• TMin = –2w–1100…0• TMax = 2w–1 – 1011…1Other Values• Minus 1111…1Decimal Hex BinaryUMax65535FF FF11111111 11111111TMax327677F FF01111111 11111111TMin-3276880 0010000000 00000000-1-1FF FF11111111 111111110000 0000000000 00000000Values for W = 16CS 213 F’01– 6 –class03.pptValues for Different Word SizesObservations• |TMin | = TMax + 1–Asymmetric range• UMax = 2 * TMax + 1C Programming• #include <limits.h>–K&R App. B11• Declares constants, e.g.,– ULONG_MAX– LONG_MAX– LONG_MIN• Values platform-specificW8 16 32 64UMax25565,5354,294,967,29518,446,744,073,709,551,615TMax12732,7672,147,483,6479,223,372,036,854,775,807TMin-128-32,768-2,147,483,648-9,223,372,036,854,775,808CS 213 F’01– 7 –class03.pptUnsigned & Signed Numeric ValuesExample Values• W = 4Equivalence• Same encodings for nonnegativevaluesUniqueness• Every bit pattern representsunique integer value• Each representable integer hasunique bit encoding⇒ Can Invert Mappings• U2B(x) = B2U-1(x)–Bit pattern for unsigned integer• T2B(x) = B2T-1(x)–Bit pattern for two’s comp integerX B2T(X)B2U(X)0000000011001020011301004010150110601117–88–79–610–511–412–313–214–1151000100110101011110011011110111101234567CS 213 F’01– 8 –class03.ppt short int x = 15213; unsigned short int ux = (unsigned short) x; short int y = -15213; unsigned short int uy = (unsigned short) y;Casting Signed to UnsignedC Allows Conversions from Signed to UnsignedResulting Value• No change in bit representation• Nonnegative values unchanged–ux = 15213• Negative values change into (large) positive values–uy = 50323CS 213 F’01– 9 –class03.pptT2UT2B B2UTwo’s ComplementUnsignedMaintain Same Bit Patternx uxXRelation Between 2’s Comp. & Unsigned+ + + + + +• • •- + + + + +• • •uxx-w–1 0+2w–1 – –2w–1 = 2*2w–1 = 2wuxx xx xw=≥+ <02 0CS 213 F’01– 10 –class03.pptRelation Between Signed & Unsigned• uy = y + 2 * 32768 = y + 65536Weight-15213 50323111112121240000800001611611632000064000012811281128256000051200001024110241102420480000409600008192000016384116384116384327681-32768132768Sum-1521350323CS 213 F’01– 11 –class03.pptSigned vs. Unsigned in CConstants• By default are considered to be signed integers• Unsigned if have “U” as suffix0U, 4294967259UCasting• Explicit casting between signed & unsigned same as U2T and T2Uint tx, ty;unsigned ux, uy;tx = (int) ux;uy = (unsigned) ty;• Implicit casting also occurs via assignments and procedure callstx = ux;uy = ty;CS 213 F’01– 12 –class03.pptCasting SurprisesExpression Evaluation• If mix unsigned and signed in single expression, signed valuesimplicitly cast to unsigned• Including comparison operations <, >, ==, <=, >=• Examples for W = 32Constant1Constant2Relation Evaluation 0 0U == unsigned-1 0 < signed-1 0U > unsigned2147483647 -2147483648 > signed2147483647U -2147483648 < unsigned-1 -2 > signed(unsigned) -1 -2 > unsigned 2147483647 2147483648U < unsigned 2147483647 (int) 2147483648U > signedCS 213 F’01– 13 –class03.ppt0TMaxTMin–1–20UMaxUMax – 1TMaxTMax + 12’s Comp.RangeUnsignedRangeExplanation of Casting Surprises2’s Comp. → Unsigned• Ordering Inversion• Negative → Big PositiveCS 213 F’01– 14 –class03.pptSign ExtensionTask:• Given w-bit signed integer x• Convert it to w+k-bit integer with same valueRule:• Make k copies of sign bit:• X ′ = xw–1 ,…, xw–1 , xw–1 , xw–2 ,…, x0k copies of MSB• • •X X ′• • • • • •• • •wwkCS 213 F’01– 15 –class03.pptSign Extension Example• Converting from smaller to larger integer data type• C automatically performs sign extension short int x = 15213; int ix = (int) x; short int y = -15213; int iy = (int) y;DecimalHex Binaryx152133B 6D00111011 01101101ix1521300 00 C4 9200000000 00000000 00111011 01101101y-15213C4 9311000100 10010011iy-15213FF FF C4 9311111111 11111111 11000100 10010011CS 213 F’01– 16 –class03.pptJustification For Sign ExtensionProve Correctness by Induction on k• Induction Step: extending by single bit maintains value• Key observation: –2w–1 = –2w +2w–1• Look at weight of upper bits:X –2w–1 xw–1X ′ –2w xw–1 + 2w–1 xw–1 = –2w–1 xw–1- • • •X X ′- + • • •w+1wCS 213 F’01– 17 –class03.pptWhy Should I Use Unsigned?Don’t Use Just Because Number Nonzero• C compilers on some machines generate less efficient codeunsigned i;for (i = 1; i < cnt; i++) a[i] += a[i-1];• Easy to make mistakesfor (i = cnt-2; i >= 0; i--) a[i] += a[i+1];Do
View Full Document