Transcript sept09
CS 111 – Sept. 9 • Integer representation: be able to convert both ways (binary decimal) – Unsigned √ – Signed √ – Biased • Real numbers • Commitment: – Please read sections 1.8 and 1.9 – Quiz tomorrow Closer look… • In 5-bit unsigned… – Smallest number is 00000 (= 0) – Largest number is 11111 (= 31) • In 5-bit signed… – Smallest number is 10000 (= –16) – Largest number is 01111 (= 15) • Given a bit pattern, its signed and unsigned values differ by how much? – Try some examples. • In signed: – Leftmost bit is the sign bit. – Positive #’s have same rep’n as unsigned. – Technique for –x doesn’t work for lowest number. Special case. Signed + and – • Signed + is like unsigned. • Watch out for overflow. – – – – The correct mathematical result can’t be represented. (Pos) + (Pos) = (Neg) (Neg) + (Neg) = (Pos) Example: 01111 + 00001. • To subtract, add the opposite. Example: 10111 – 00111 – First, –(00111) = 11001 – Turn into addition problem: 10111 + 11001 = __________ – Is there overflow? Scheme III: biased • Another way to represent integers that allows for negatives. • (It will soon help us see how real numbers are stored.) • The “bias” is the number we subtract from unsigned range. – If B is the bias, the lowest number is –B. • When working with a biased rep’n, you have to be given the bias. – Ex. For 6-bits, bias is typically 31 or 32. – Ex. For 8-bits, bias is typically 127 or 128. • So, a “6 bit biased-31 rep’n” is based on 6-bit unsigned, except that 000000 is now –31 instead of 0. How to convert • How do we represent a number n in biased (B)? 1. Add the bias: n + B. 2. Determine the unsigned rep’n of this number. – Example: What is the 6-bit biased-31 rep’n of –9? • It’s the same as the unsigned rep’n of –9 + 31 = 22. • 22 in 6 bit unsigned is 010110. • How do we convert a biased number back into base 10? 1. Interpret the number as unsigned 2. Subtract the bias. – Example: 101010 is the 6-bit biased-31 rep’n of what number? • If unsigned, 101010 = 32+8+2 = 42. • 42 – 31 = 11. Integer vs. Real • Integer arithmetic on computer is quick & exact, but has limited range. • Real arithmetic needs wide range, and a reasonable degree of precision. – Scientific / numerical computation – 14 significant digits is usually enough! • Skills: – Converting a base-10 real number into binary – Actual representation relies on “scientific notation” Examples • Consider this sequence: 111 = 7 1110 = 14 11100 = 28 111000 = 56 1110000 = 112 • Going the other way… 111. = 7 11.1 = 3.5 or 7/2 1.11 = 1.75 or 7/4 .111 = 7/8 .0111 = 7/16 See the pattern? Each digit corresponds to (+ /–) power of 2. Convert to binary • Separate real number (e.g. 5.7) into integer and fractional parts • Integer part use binary store. • Fractional part: – Keep multiplying fractional part by 2 until it becomes zero, or until you have a repeating pattern. • Example: 9.625 – Integer part 9 becomes “1001” – Fractional part is 0.625: .625 * 2 = 1.25 .25 * 2 = 0.5 .5 * 2 = 1.0 Fractional part reaches 0. So our answer is 1001.101 Repeating pattern • Let’ try converting 0.7 to binary: .7 * 2 = 1.4 .4 * 2 = 0.8 .8 * 2 = 1.6 .6 * 2 = 1.2 .2 * 2 = 0.4 .4 * 2 = 0.8 • “Aha!” The pattern tells you which digits repeat. ____ • Answer is 0.1 0110 0110 0110 … or .10110 Real number rep’n • • • • Also called “floating point” Size is 32 or 64 bits: “single” vs. “double” precision Based on binary scientific notation Let’s look at single precision: – 1 bit for sign (0 = positive, 1 = negative) – 8 bits for exponent (expressed in biased-127) – 23 bits for mantissa • Big mantissa precision is most important feature Example • We saw earlier that 9.625 = 1001.101 in binary. Let’s continue with the true representation. • Sign: 1 bit. Since it’s a positive number, we have 0 • Exponent: 8 bits – If we write 1001.101 in binary scientific notation, we get 1.001101 * 23. – The exponent 3 is expressed in 8-bit biased-127. In other words 3+127=130 in unsigned: 10000010 • Mantissa (23-bits): We only store the fractional part of the mantissa: 001101. Remaining bits are zero. • Final answer: 0 10000010 (1) 001101 017 Decoding • Let’s see if we can decode a real number: 1 10000001 (1) 011 020 • Sign: “1” means a negative number • Exponent: “10000001” looks like 129 in unsigned. But in biased-127 it is 129 – 127 = 2. So our number is something multiplied by 22. • Mantissa: 1.011 in binary = 1 + 1/4 + 1/8 = 1.375 • Combine all 3 parts: –1.375 * 22 = –5.5 Some thoughts • In single precision… – 8 bit exponent 256 possible exponents Highest number ~ 1038 Lowest number ~ 10–38 – 23 bit mantissa ~ 8 million exact real number per power of 2 We have about 7 significant digits • Comparing with double precision – What can we conclude? Precision Sign Exponent Mantissa Single 1 8 23 Double 1 11 52