In Class Handout Version 15 213 The course that gives CMU its Zip Integers Sep 4 2001 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 divide class03 ppt CS 213 F 01 C 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 Initialization x 2 0 x 7 7 x 30 0 x 0 ux 0 int x foo int y bar ux 1 unsigned ux x x y unsigned uy y x y x x 0 x 0 y 0 class03 ppt x y 0 x 0 x 0 x 0 x 0 2 CS 213 F 01 Encoding 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 Sign Bit C short 2 bytes long x y Decimal 15213 15213 Hex 3B 6D C4 93 Binary 00111011 01101101 11000100 10010011 Sign Bit For 2 s complement most significant bit indicates sign 0 for nonnegative 1 for negative class03 ppt 3 CS 213 F 01 Encoding Example Cont x y Weight 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 Sum class03 ppt 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 4 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 CS 213 F 01 Numeric Ranges Unsigned Values UMin 000 0 UMax 111 1 Two s Complement Values 0 TMin 100 0 TMax 011 1 2w 1 2w 1 2w 1 1 Other Values Minus 1 111 1 Values for W 16 UMax TMax TMin 1 0 class03 ppt Decimal 65535 32767 32768 1 0 Hex FF FF 7F FF 80 00 FF FF 00 00 5 Binary 11111111 11111111 01111111 11111111 10000000 00000000 11111111 11111111 00000000 00000000 CS 213 F 01 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 Observations C Programming include limits h K R App B11 Declares constants e g ULONG MAX LONG MAX LONG MIN Values platform specific TMin TMax 1 Asymmetric range UMax 2 TMax 1 class03 ppt 64 18 446 744 073 709 551 615 9 223 372 036 854 775 807 9 223 372 036 854 775 808 6 CS 213 F 01 Unsigned Signed Numeric Values X 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 B2U X 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class03 ppt B2T X 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 Example Values W 4 Equivalence Same encodings for nonnegative values Uniqueness 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 integer 7 CS 213 F 01 Casting Signed to 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 No change in bit representation Nonnegative values unchanged ux 15213 Negative values change into large positive values uy 50323 class03 ppt 8 CS 213 F 01 Relation Between 2 s Comp 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 x ux w x 2 class03 ppt x 0 x 0 9 CS 213 F 01 Relation Between Signed Unsigned Weight 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 Sum uy class03 ppt 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 10 CS 213 F 01 Signed vs Unsigned in C Constants By default are considered to be signed integers Unsigned if have U as suffix 0U 4294967259U Casting Explicit casting between signed unsigned same as U2T and T2U int tx ty unsigned ux uy tx int ux uy unsigned ty Implicit casting also occurs via assignments and procedure calls tx ux uy ty class03 ppt 11 CS 213 F 01 Casting Surprises Expression Evaluation If mix unsigned and signed in single expression signed values implicitly cast to unsigned Including comparison operations Examples for W 32 Constant1 0 1 1 2147483647 2147483647U 1 unsigned 1 2147483647 2147483647 class03 ppt Constant2 Relation 0U 0 0U 2147483648 2147483648 2 2 2147483648U int 2147483648U 12 Evaluation unsigned signed unsigned signed unsigned signed unsigned unsigned signed CS 213 F 01 Explanation of Casting Surprises 2 s Comp Unsigned Ordering Inversion Negative Big Positive UMax UMax 1 TMax 1 TMax TMax 2 s Comp Range 0 1 2 Unsigned Range 0 TMin class03 ppt 13 CS 213 F 01 Sign Extension Task Given w bit signed integer x Convert it to w k bit integer with same value Rule Make k copies of sign bit X xw 1 xw 1 xw 1 xw 2 x0 w k copies of MSB X X w k class03 ppt 14 CS 213 F 01 Sign Extension Example short int x 15213 int ix int x short int y 15213 int iy int y x ix y iy Decimal Hex 3B 15213 15213 00 00 C4 C4 15213 15213 FF FF C4 6D 92 93 93 Binary 00111011 00000000 00000000 00111011 11000100 11111111 11111111 11000100 01101101 01101101 10010011 10010011 Converting from smaller to larger integer data type C automatically performs sign extension class03 ppt 15 CS 213 F 01 Justification For Sign Extension Prove Correctness by Induction on k Induction Step extending by single bit maintains value w X X w 1 Key observation 2w 1 2w 2w 1 Look at weight of upper bits X 2w 1 xw 1 X 2w xw 1 2w 1 xw 1 2w 1 xw 1 class03 ppt 16 CS 213 F 01 Why Should I Use Unsigned Don t …
View Full Document
Unlocking...