15-213 “The course that gives CMU its Zip!”C PuzzlesEncoding IntegersEncoding Example (Cont.)Numeric RangesValues for Different Word SizesUnsigned & Signed Numeric ValuesCasting Signed to UnsignedRelation Between 2’s Comp. & UnsignedRelation Between Signed & UnsignedSigned vs. Unsigned in CCasting SurprisesExplanation of Casting SurprisesSign ExtensionSign Extension ExampleJustification For Sign ExtensionWhy Should I Use Unsigned?Negating with Complement & IncrementComp. & Incr. ExamplesUnsigned AdditionVisualizing Integer AdditionVisualizing Unsigned AdditionMathematical PropertiesTwo’s Complement AdditionCharacterizing TAddVisualizing 2’s Comp. AdditionDetecting 2’s Comp. OverflowMathematical Properties of TAddSlide 29MultiplicationUnsigned Multiplication in CUnsigned vs. Signed MultiplicationPower-of-2 Multiply with ShiftUnsigned Power-of-2 Divide with Shift2’s Comp Power-of-2 Divide with ShiftCorrect Power-of-2 DivideCorrect Power-of-2 Divide (Cont.)Properties of Unsigned ArithmeticProperties of Two’s Comp. ArithmeticC Puzzle Answers15-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 negativeB2T(X ) xw 12w 1 xi2ii0w 2B2U(X ) xi2ii0w 1UnsignedTwo’s ComplementSignBitDecimal Hex Binaryx152133B 6D 00111011 01101101y-15213C4 93 11000100 10010011CS 213 F’01– 4 –class03.pptEncoding Example (Cont.) x = 15213: 00111011 01101101 y = -15213: 11000100 10010011Weight 15213 -1521311111200124140081800160011632132006416400128001128256125600512151200102400110242048120480040961409600819218192001638400116384-32768001-32768Sum 15213 -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 FF 11111111 11111111TMax327677F FF 01111111 11111111TMin-3276880 00 10000000 00000000-1-1FF FF 11111111 111111110000 00 00000000 00000000Values for W = 16CS 213 F’01– 6 –class03.pptValues for Different Word SizesObservations•|TMin | = TMax + 1–Asymmetric range•UMax = 2 * TMax + 1 C Programming•#include <limits.h>–K&R App. B11•Declares constants, e.g.,–ULONG_MAX–LONG_MAX–LONG_MIN•Values platform-specificW8 16 32 64UMax 255 65,535 4,294,967,2 95 18,446,744,073,709,551,615TMax 127 32,767 2,147,483,647 9,223,372,036,854,775,8 07TMin -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 nonnegative valuesUniqueness•Every bit pattern represents unique integer value•Each representable integer has unique 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)0000 00001 10010 20011 30100 40101 50110 60111 7–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 = 2wux x x 0x 2wx 0CS 213 F’01– 10 –class03.pptRelation Between Signed & Unsigned•uy = y + 2 * 32768 = y + 65536Weight -15213 50323111112121240000800001611611632000064000012811281128256000051200001024110241102420480000409600008192000016384116384116384327681-32768132768Sum -15213 50323CS 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 values implicitly 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
View Full Document