15 740 Computer Arithmetic A Programmer s View Oct 6 1998 Topics Integer Arithmetic Unsigned Two s Complement Floating Point IEEE Floating Point Standard Alpha floating point class07 ppt W Notatio Number of Bits in Word n C Data Type long int int short char Sun etc 32 32 16 8 Alpha 64 32 16 8 Integers Lower case E g x y z Bit Vectors Upper Case E g X Y Z Write individual bits as integers with value 0 or 1 E g X xw 1 xw 2 x0 Most significant bit on left class07 ppt 2 CS 740 F 98 Encoding Integers Two s Complement Unsigned B2U X w 1 xi 2 i B2T X xw 1 2 i 0 w 1 w 2 xi 2 i i 0 short int x 15740 short int y 15740 Sign Bit C short 2 bytes long x y Decimal 15740 15740 Hex 3D 7C C2 84 Binary 00111101 01111100 11000010 10000100 Sign Bit For 2 s complement most significant bit indicates sign 0 for nonnegative 1 for negative class07 ppt 3 CS 740 F 98 Numeric Two s Complement Values Ranges TMin 2 Unsigned Values UMin 000 0 UMax 111 1 0 100 0 TMax 011 1 2w 1 w 1 2w 1 1 Other Values Minus 1 111 1 Values for W 16 UMax TMax TMin 1 0 class07 ppt Decimal 65535 32767 32768 1 0 Hex FF FF 7F FF 80 00 FF FF 00 00 4 Binary 11111111 11111111 01111111 11111111 10000000 00000000 11111111 11111111 00000000 00000000 CS 740 F 98 Values for Different Word Sizes 8 255 UMax 127 TMax TMin 128 16 65 535 32 767 32 768 W 32 64 4 294 967 295 18 446 744 073 709 551 615 2 147 483 647 9 223 372 036 854 775 807 2 147 483 648 9 223 372 036 854 775 808 Observations C Programming TMax 1 TMin Asymmetric range 2 TMax 1 UMax class07 ppt include limits h K R Appendix B11 Declares constants e g ULONG MAX LONG MAX LONG MIN Values platform specific 5 CS 740 F 98 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 class07 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 6 CS 740 F 98 Casting Signed to Unsigned C Allows Conversions from Signed to Unsigned short int x 15740 unsigned short int ux unsigned short x short int y 15740 unsigned short int uy unsigned short y Resulting Value No change in bit representation Nonnegative values unchanged ux 15740 Negative values change into large positive values uy 49796 class07 ppt 7 CS 740 F 98 Relation Between 2 s Comp Unsigned Two s Complement Unsigned T2U T2B x X B2U ux Maintain Same Bit Pattern w 1 ux 0 x 2w 1 2w 1 2 2w 1 2w ux x w x 2 class07 ppt x 0 x 0 8 CS 740 F 98 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 class07 ppt 9 CS 740 F 98 Casting Expression Evaluation Surprises If mix unsigned and signed in single expression signed values implicitly cast to unsigned Including comparison operations Examples for W 32 Constant1 Constant2 0 1 1 2147483647 2147483647U 1 unsigned 1 2147483647 2147483647 class07 ppt Relation 0U 0 0U 2147483648 2147483648 2 2 2147483648U int 2147483648U 10 Evaluation unsigned signed unsigned signed unsigned signed unsigned unsigned signed CS 740 F 98 Explanation of Casting Surprises 2 s Comp Unsigned Ordering Inversion Negative Big Positive UMax UMax 1 TMax 1 TMax TMax 2 s Comp Range class07 ppt 0 1 2 Unsigned Range 0 TMin 11 CS 740 F 98 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 class07 ppt w k 12 CS 740 F 98 Justification For Sign Extension Prove Correctness by Induction on k Induction Step extending by single bit maintains value w 2w 1 2w 2w 1 Key observation Look at weight of upper bits X 2w 1 xw 1 X 2w xw 1 2w 1 xw 1 2w 1 xw 1 X X class07 ppt w 1 13 CS 740 F 98 Integer Operation C Assume machine with 32Puzzles 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 int x foo int y bar unsigned ux x unsigned uy y 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 class07 ppt x y 0 x 0 x 0 x 0 x 0 14 CS 740 F 98 Unsigned Addition u v u v UAddw u v Operands w bits True Sum w 1 bits Discard Carry w bits Standard Addition Function Ignores carry output Implements Modular Arithmetic s class07 ppt UAddw u v u v mod 2w 15 CS 740 F 98 Visualizing Integer Addition Integer Addition 4 bit integers u and v Compute true sum Add4 u v Values increase linearly with u and v Forms planar surface Add4 u v 30 25 20 15 14 12 10 10 8 5 0 6 4 0 1 2 3 4 u class07 ppt 16 v 2 5 6 7 8 0 9 10 11 12 13 14 15 CS 740 F 98 Visualizing Unsigned Addition Wraps Around If true sum 2w At most once Overflow UAdd4 u v 16 True Sum 2w 1 14 Overflow 12 10 2w 8 14 6 0 12 10 4 Modular Sum 8 6 2 0 4 0 1 2 3 4 u class07 ppt 17 v 2 5 6 7 8 0 9 10 11 12 13 14 15 CS 740 F 98 Mathematical Modular Addition Forms an Abelian Group Properties Closed under addition 0 UAddw u v 2w 1 Commutative UAddw u v UAddw v u Associative UAddw t UAddw u v UAddw UAddw t u v 0 is additive identity UAddw u 0 u Every element has additive inverse UCompw u 2w u Let UAddw u UCompw u 0 class07 ppt 18 CS 740 …
View Full Document