Transcript Week-02.2
Dale & Lewis Chapter 3 Data Representation Data and computers • Everything inside a computer is stored as patterns of 0s and 1s • Numbers, text, audio, video, images, graphics, etc. − How do you convert these to 0s and 1s? − How do you store the digital information efficiently? Representing numeric data • Representing Natural numbers with a finite number of digits • General Property: Number of digits Min Max n 0 bn-1 • Example: − − − − b=10, n=3 b=2, n=3 b=8, n=3 b=16, n=3 000 to 999 000 to 111 (equivalent to 0 to 7 in decimal) 000 to 777 (equivalent to 0 to 511 in decimal) 000 to FFF (equivalent to 0 to 4,095 in decimal) Representing negative numbers (integers) • Basic definition − An integer is a number with no fractional part − Examples: +123 -67 • Integers (signed natural numbers) − Previously we looked at unsigned numbers, i.e. natural numbers − Need a mechanism to represent both positive and negative numbers − Two schemes: 1) sign-magnitude, 2) complementary representaion Sign-magnitude • In binary: − Sign: left-most bit (0 = positive, 1 = negative) − Magnitude: remaining bits • Example with 6-bit sign-magnitude representation +5 = 000101 • Ranges in binary Unsigned # of bits Min Max 1 0 1 2 0 3 3 0 7 4 0 15 5 0 31 6 0 63 n 0 2n-1 -5 = 100101 Sign-magnitude Min Max -1 -3 -7 -15 -31 +1 +3 +7 +15 +31 -(2n-1-1) +(2n-1-1) Complementary representation • Difficulties with Sign-magnitude − Two representations for zero +0 = 000000 -0 = 100000 − Arithmetic is awkward, especially subtraction • Complementary representation − Positive numbers are represented by their corresponding natural numbers − Negative numbers are represented as very large natural numbers − Subtracting numbers reduces to performing addition operations negative numbers: negative(x) ≡ bn-x Complementary representation negative numbers: negative(x) ≡ bn-x • Example: let b = 10 and n = 2 Positive numbers (+0) 00 (+1) 01 (+2) 02 (+3) 03 … (+49) 49 Negative numbers (-1) 99 (-2) 98 (-3) 97 … (-49) 51 (-50) 50 -49 -50 +49 Visualization 51 50 49 99 00 01 -1 0 +1 50 98 99 00 01 02 49 -50 -2 -1 0 +1 +2 +49 Examples of arithmetic in Ten’s complement -35 plus +25 equals -10 65 plus 25 equals 90 Ten’s complement +17 plus +25 equals +42 17 plus 25 equals 42 Ten’s complement +20 plus -30 equals -10 20 plus 70 equals 90 Ten’s complement -20 plus +30 equals +10 80 plus 30 equals 10 (110) Ten’s complement Examples of arithmetic in Ten’s complement • Subtraction reduces to addition because A – B = A + (-B) +5 05 -4 96 + -6 + 94 + +6 + 06 -1 99 +2 02 -2 + -4 -6 98 + 96 94 -5 - +3 -8 95 - 03 95 + 97 92 • Easy to convert between positive number and its negative counterpart − This conversion can be made efficiently and simplify logic circuitry (we will see how) Two’s complement representation • Negative numbers: negative(x) ≡ 2n-x • Used in computers because subtraction reduces to addition simpler circuits • To form a negative number − Start with the positive version of the number − Flip the bits: 0 1 and 1 0 − Add 1 to the number produced in the previous step • Same process for conversion back to positive numbers • The above steps are an indirect way of carrying our the evaluation of 2n-x, or more conveniently [(2n-1)-x]+1 Examples of Two’s complement • +5 (0101) to -5 (1011) • -5 (1011) to +5 (0101) • Evaluating 2n-x is 24-5 = 16-5 = 11 • Or • Evaluating [(2n-1)-x]+1 is [(24-1)-5]+1 = 15-5+1 = 11 (this way you never borrow) 10000 101 1011 - 1111 101 1010 + 1 +2 = 0010 + +3 = +0011 +5 = 0101 -2 = 1110 + +3 = +0011 +1 = 10001 ↑ throw away -2 = 1110 = 1110 +2 = 0010 = 0010 - +3 = -0011 = +1101 - +3 = -0011 = +1101 -5 = = 11011 -1 = = 1111 ↑ throw away Sample test/exam questions • Q: Convert -173 to 12-bit two’s complement representation. Show all your work. • A: Step 1: Convert 173 to binary by repeated division by 2 173 ÷ 2 86 1 1 86 ÷ 2 43 0 01 43 ÷ 2 21 1 101 21 ÷ 2 10 1 1101 10 ÷ 2 5 0 01101 5 ÷ 2 2 1 101101 2 ÷ 2 1 0 0101101 1 ÷ 2 0 1 10101101 Sample test/exam questions • Q: Convert -173 to 12-bit two’s complement representation. Show all your work. • A: Step 1: Convert 173 to binary by repeated division by 2 10101101 • Step 2: Expand answer in Step 1 to 12-bits 000010101101 • Step 3: Flip-the-bits and add one 111101010010 + 1 111101010011 • Final answer: -173 = 111101010011 Sample test/exam questions • Q: Convert +173 to 12-bit two’s complement representation. Show all your work. • Q: Convert the 12-bit two’s complement number 111101010011 to decimal.