Chapter Three 1 2004 Morgan Kaufmann Publishers Numbers Bits are just bits no inherent meaning conventions define relationship between bits and numbers Binary numbers base 2 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 decimal 0 2n 1 Of course it gets more complicated numbers representable are finite overflow fractions and real numbers negative numbers e g no MIPS subi instruction addi can add a negative number How do we represent negative numbers i e which bit patterns will represent which numbers 2 2004 Morgan Kaufmann Publishers Possible Representations Sign Magnitude 000 0 001 1 010 2 011 3 100 0 101 1 110 2 111 3 One s Complement Two s Complement 000 0 001 1 010 2 011 3 100 3 101 2 110 1 111 0 000 0 001 1 010 2 011 3 100 4 101 3 110 2 111 1 Issues balance number of zeros ease of operations Which one is best Why 3 2004 Morgan Kaufmann Publishers MIPS 32 bit signed numbers 0000 0000 0000 0111 0111 1000 1000 1000 1111 1111 1111 0000 0000 0000 0000 0000 0000 0000two 0ten 0000 0000 0000 0000 0000 0000 0001two 1ten 0000 0000 0000 0000 0000 0000 0010two 2ten 1111 1111 0000 0000 0000 1111 1111 0000 0000 0000 1111 1111 0000 0000 0000 1111 1111 0000 0000 0000 1111 1111 0000 0000 0000 1111 1111 0000 0000 0000 1110two 1111two 0000two 0001two 0010two 2 147 483 646ten 2 147 483 647ten 2 147 483 648ten 2 147 483 647ten 2 147 483 646ten maxint minint 1111 1111 1111 1111 1111 1111 1101two 3ten 1111 1111 1111 1111 1111 1111 1110two 2ten 1111 1111 1111 1111 1111 1111 1111two 1ten 4 2004 Morgan Kaufmann Publishers Two s Complement Operations Negating a two s complement number invert all bits and add 1 remember negate and invert are quite different Converting n bit numbers into numbers with more than n bits MIPS 16 bit immediate gets converted to 32 bits for arithmetic copy the most significant bit the sign bit into the other bits 0010 0000 0010 1010 1111 1010 sign extension lbu vs lb 5 2004 Morgan Kaufmann Publishers Addition Subtraction Just like in grade school carry borrow 1s 0111 0111 0110 0110 0110 0101 Two s complement operations easy subtraction using addition of negative numbers 0111 1010 Overflow result too large for finite computer word e g adding two n bit numbers does not yield an n bit number 0111 0001 note that overflow term is somewhat misleading 1000 it does not mean a carry overflowed 6 2004 Morgan Kaufmann Publishers Detecting Overflow No overflow when adding a positive and a negative number No overflow when signs are the same for subtraction Overflow occurs when the value affects the sign overflow when adding two positives yields a negative or adding two negatives gives a positive or subtract a negative from a positive and get a negative or subtract a positive from a negative and get a positive Consider the operations A B and A B Can overflow occur if B is 0 Can overflow occur if A is 0 7 2004 Morgan Kaufmann Publishers Effects of Overflow An exception interrupt occurs Control jumps to predefined address for exception Interrupted address is saved for possible resumption Details based on software system language example flight control vs homework assignment Don t always want to detect overflow new MIPS instructions addu addiu subu note addiu still sign extends note sltu sltiu for unsigned comparisons 8 2004 Morgan Kaufmann Publishers Multiplication More complicated than addition accomplished via shifting and addition More time and more area Let s look at 3 versions based on a gradeschool algorithm 1010 x 1001 multiplicand multiplier Negative numbers convert and multiply there are better techniques we won t look at them 9 2004 Morgan Kaufmann Publishers Multiplication Implementation Start Multiplier0 1 1 Test Multiplier0 Multiplier0 0 1a Add multiplicand to product and place the result in Product register Multiplicand Shift left 64 bits Multiplier Shift right 64 bit ALU 2 Shift the Multiplicand register left 1 bit 32 bits Product Write 3 Shift the Multiplier register right 1 bit Control test 64 bits 32nd repetition Datapath No 32 repetitions Yes 32 repetitions Control Done 10 2004 Morgan Kaufmann Publishers Final Version Start Multiplier starts in right half of product Product0 1 1 Test Product0 Product0 0 Multiplicand 32 bits 32 bit ALU Product Shift right Write Control test 3 Shift the Product register right 1 bit 64 bits 32nd repetition What goes here No 32 repetitions Yes 32 repetitions Done 11 2004 Morgan Kaufmann Publishers Division Dividend Quotient x Divisor Remainder 12 2004 Morgan Kaufmann Publishers Floating Point a brief look We need a way to represent numbers with fractions e g 3 1416 very small numbers e g 000000001 very large numbers e g 3 15576 109 Representation sign exponent significand 1 sign significand 2exponent more bits for significand gives more accuracy more bits for exponent increases range IEEE 754 floating point standard single precision 8 bit exponent 23 bit significand double precision 11 bit exponent 52 bit significand 13 2004 Morgan Kaufmann Publishers IEEE 754 floating point standard Leading 1 bit of significand is implicit Exponent is biased to make sorting easier all 0s is smallest exponent all 1s is largest bias of 127 for single precision and 1023 for double precision summary 1 sign significand 2exponent bias Example decimal 75 binary 11 1 1 x 2 1 floating point exponent 126 01111110 IEEE single precision 10111111010000000000000000000000 14 2004 Morgan Kaufmann Publishers Floating point addition Sign Exponent Fraction Sign Exponent 1 Compare the exponents of the two numbers Shift the smaller number to the right until its exponent would match the larger exponent Small ALU Exponent difference 0 Start Fraction 2 Add the significands 1 0 1 0 3 Normalize the sum either shifting right and incrementing the exponent or shifting left and decrementing the exponent Shift right Control 1 Overflow or underflow Big ALU Yes No 0 0 1 Increment or decrement Exception 1 4 Round the significand to the appropriate number of bits Shift left or right No Rounding hardware Still normalized Yes Sign Exponent Fraction Done 15 2004 Morgan Kaufmann Publishers Floating point multiplication 16 2004 Morgan Kaufmann Publishers Floating Point Complexities Operations are somewhat more complicated see text In addition to overflow we can have underflow Accuracy can be a big problem IEEE 754 keeps two extra bits guard and round four rounding modes positive divided by zero yields infinity zero divide by zero yields not a number other complexities Implementing the standard