15 213 The course that gives CMU its Zip Integers Sep 3 2002 Topics n Numeric Encodings l Unsigned Two s complement n Programming Implications l C promotion rules n Basic operations l Addition negation multiplication n Programming Implications l Consequences of overflow l Using shifts to perform power of 2 multiply divide class03 ppt 15 213 F 02 C Puzzles n Taken from old exams n Assume machine with 32 bit word size two s complement integers n For each of the following C expressions either l Argue that is true for all argument values l Give example where not true x 0 Initialization ux 0 x 7 7 int x foo ux 1 int y bar x y unsigned ux x x x 0 unsigned uy y x 0 y 0 2 x 2 0 x 30 0 x y x y 0 x 0 x 0 x 0 x 0 15 213 F 02 Encoding Integers Integers Unsigned B2U X w 1 xi 2 Two s Complement B2T X xw 1 2 i i 0 w 1 w 2 xi 2 i i 0 short int x 15213 short int y 15213 n Sign Bit C short 2 bytes long x y Decimal 15213 15213 Hex 3B 6D C4 93 Binary 00111011 01101101 11000100 10010011 Sign Bit n For 2 s complement most significant bit indicates sign l 0 for nonnegative l 1 for negative 3 15 213 F 02 Encoding Example Example Cont Cont x y 4 Weight 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 Sum 15213 00111011 01101101 15213 11000100 10010011 15213 1 1 0 0 1 4 1 8 0 0 1 32 1 64 0 0 1 256 1 512 0 0 1 2048 1 4096 1 8192 0 0 0 0 15213 15213 1 1 1 2 0 0 0 0 1 16 0 0 0 0 1 128 0 0 0 0 1 1024 0 0 0 0 0 0 1 16384 1 32768 15213 15 213 F 02 Numeric Ranges Unsigned Values n UMin 0 Two s Complement Values n TMin 2w 1 000 0 n UMax 100 0 2w 1 n 111 1 TMax 2w 1 1 011 1 Other Values n Minus 1 111 1 Values for W 16 UMax TMax TMin 1 0 5 Decimal 65535 32767 32768 1 0 Hex FF FF 7F FF 80 00 FF FF 00 00 Binary 11111111 11111111 01111111 11111111 10000000 00000000 11111111 11111111 00000000 00000000 15 213 F 02 Values for Different Word Sizes W UMax TMax TMin 8 255 127 128 16 65 535 32 767 32 768 32 4 294 967 295 2 147 483 647 2 147 483 648 C Programming Observations n TMin TMax 1 n UMax 2 TMax 1 include limits h l K R App B11 l Asymmetric range n 64 18 446 744 073 709 551 615 9 223 372 036 854 775 807 9 223 372 036 854 775 808 n Declares constants e g l ULONG MAX l LONG MAX l LONG MIN n 6 Values platform specific 15 213 F 02 Unsigned Signed Numeric Values X 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 7 B2U X 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 B2T X 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 Equivalence n Same encodings for nonnegative values Uniqueness n Every bit pattern represents unique integer value n Each representable integer has unique bit encoding Can Invert Mappings n U2B x B2U 1 x l Bit pattern for unsigned integer n T2B x B2T 1 x l Bit pattern for two s comp integer 15 213 F 02 Casting Signed to to Unsigned Unsigned C Allows Conversions from Signed to Unsigned short int x 15213 unsigned short int ux unsigned short x short int y 15213 unsigned short int uy unsigned short y Resulting Value n No change in bit representation n Nonnegative values unchanged l ux 15213 n Negative values change into large positive values l uy 50323 8 15 213 F 02 Relation between Signed Signed Unsigned Unsigned Two s Complement Unsigned T2U T2B x B2U ux X Maintain Same Bit Pattern w 1 ux 0 x 2w 1 2w 1 2 2w 1 2w 9 x ux w x 2 x 0 x 0 15 213 F 02 Relation Between Signed Signed Unsigned Unsigned Weight 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 Sum n 10 uy 15213 1 1 1 2 0 0 0 0 1 16 0 0 0 0 1 128 0 0 0 0 1 1024 0 0 0 0 0 0 1 16384 1 32768 15213 y 2 32768 50323 1 1 1 2 0 0 0 0 1 16 0 0 0 0 1 128 0 0 0 0 1 1024 0 0 0 0 0 0 1 16384 1 32768 50323 y 65536 15 213 F 02 Signed vs Unsigned Unsigned in in C C Constants n By default are considered to be signed integers n Unsigned if have U as suffix 0U 4294967259U Casting n Explicit casting between signed unsigned same as U2T and T2U int tx ty unsigned ux uy tx int ux uy unsigned ty n Implicit casting also occurs via assignments and procedure calls tx ux uy ty 11 15 213 F 02 Casting Surprises Expression Evaluation n If mix unsigned and signed in single expression signed values implicitly cast to unsigned n Including comparison operations n Examples for W 32 Constant1 12 Constant2 Relation Evaluation 0 1 0U 0 unsigned signed 1 2147483647 0U 2147483648 unsigned signed 2147483647U 1 2147483648 2 unsigned signed unsigned 1 2147483647 2 2147483648U unsigned unsigned 2147483647 int 2147483648U 15 213 F 02 signed Explanation of Casting Casting Surprises Surprises 2 s Comp Unsigned n n Ordering Inversion Negative Big Positive TMax 2 s Comp Range 13 0 1 2 TMin UMax UMax 1 TMax 1 TMax Unsigned Range 0 15 213 F 02 Sign Extension Extension Task n Given w bit signed integer x n Convert it to w k bit integer with same value Rule n n Make k copies of sign bit X xw 1 xw 1 xw 1 xw 2 x0 w k copies of MSB X X 14 k w 15 213 F 02 Sign Extension Example Example short int x 15213 int ix int x short int y 15213 int iy int y Decimal Hex 3B 15213 15213 00 00 3B C4 15213 15213 FF FF C4 x ix y iy 15 6D 6D 93 93 Binary 00111011 00000000 00000000 00111011 11000100 11111111 11111111 11000100 n Converting from smaller to larger integer data type n C automatically performs sign extension 01101101 01101101 10010011 10010011 15 213 F 02 Justification For For Sign Sign Extension Extension Prove Correctness by Induction on k n Induction Step extending by single bit maintains value w X X w 1 Key observation n Look at …
View Full Document
Unlocking...