Transcript Document
CSE1301 Computer Programming Lecture 32: Number Representation 1 Topics • • • • • Representing characters and integers Converting binary to decimal Converting decimal to binary Adding binary numbers Limitations 2 Representing Characters • ASCII encoding (American Standard Code for Information Interchange) • Each character represented by a one-byte (8-bit) number • Other representations possible too: – EBCDIC (used by older IBM machines) – Unicode (16-bit character codes, provides enough codes for characters from all modern languages) 3 Representing Integers • We represent integers using a base-10 positional notation. • So the number 80710 means: 8104 + 0103 + 7102 + 1101 + 0100 4 Representing Integers • Computers represent integers using a base-2 positional notation. • So the number 101011 means: 125 + 024 + 123 + 022 + 121 + 120 132 + 016 + 18 + 04 + 12 + 11 = 43 in decimal 5 Representing Integers • Curiously, ye Olde Englishe pub-keepers used the same system: • So the number 101011 means: 1gallon + 0pottle + 1quart + 0pint + 1chopin + 1gill 14.6l + 02.3l + 11.1l + 00.6l + 10.3l + 10.1l = 6.1 litres 6 Representing Integers • The first few binary numbers are: 0000....................0 0001....................1 0010....................2 0011....................3 0100....................4 0101....................5 0110....................6 0111....................7 1000....................8 1001....................9 1010....................10 1011....................11 1100....................12 1101....................13 1110....................14 1111....................15 7 Converting binary to decimal Example: Convert the unsigned binary number 10011010 to decimal. 1 0 0 1 1 0 1 0 8 Converting binary to decimal 7 6 5 4 3 2 1 0 1 0 0 1 1 0 1 0 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0 9 Converting binary to decimal 7 6 5 4 3 2 1 0 1 0 0 1 1 0 1 0 128 64 32 16 8 4 2 1 10 Converting binary to decimal 7 6 5 4 3 2 1 0 1 0 0 1 1 0 1 0 128 64 32 16 8 4 2 1 128 + 16 + 8 + 2 = 154 (or 27 + 24 + 23 + 21) So, 10011010 in unsigned binary is 154 in decimal. 11 Converting Decimal to/from Binary Analogy: Giving a $69.10 change from largest to smallest denomination: 69.10 = 1 $50 bill + 19.10 19.10 = 1 $10 bill + 9.10 9.10 = 1 $5 bill + 4.10 4.10 = 2 $2 coin + 0.10 0.10 = 1 10c coin 12 Converting Decimal to/from Binary Bit position. 7 2 6 7 2 5 6 2 4 5 2 3 4 2 2 3 2 1 2 2 0 1 2 0 Decimal value. 13 Converting Decimal to/from Binary Bit position. 7 6 5 4 128 64 32 16 3 2 1 0 8 4 2 1 Decimal value. 14 Decimal to Binary Example: Convert the decimal number 105 to unsigned binary. 15 Q. What is the highest power of 2 that is less than or equal to 105? A. 64 6 5 4 3 2 1 0 32 16 8 4 2 1 1 128 64 Next, consider the difference: 105 - 64 = 41 16 Q. What is the highest power of 2 that is less than or equal to 41? A. 32 6 5 1 1 64 32 4 3 2 1 16 8 4 2 0 1 Next, consider the difference: 41 - 32 = 9 17 Q. What is the highest power of 2 that is less than or equal to 9? A. 8 6 5 1 1 64 32 4 3 2 1 4 2 0 1 16 8 1 Next, consider the difference: 9 - 8 = 1 18 Q. What is the highest power of 2 that is less than or equal to 1? A. 1 6 5 1 1 64 32 4 3 2 1 1 16 8 0 1 4 Next, consider the difference: 1 - 1 = 0 2 1 Done! 19 Finally, fill the empty boxes with zeros. 6 5 4 3 2 1 0 1 1 0 1 0 0 1 64 32 16 8 4 2 1 So, 105 decimal is 1101001 in unsigned binary. 20 Converting decimal to binary • We've seen that you convert binary to decimal by multiplying and adding. • So it's no surprise that you convert decimal to binary by dividing and subtracting. • You can also convert decimal to binary by dividing and noting the remainder. 21 Converting decimal to binary 123 ÷2 61 ÷2 30 ÷2 15 ÷2 7 ÷2 3 ÷2 1 ÷2 0 remainder 1 remainder 1 remainder 0 remainder 1 remainder 1 remainder 1 remainder 1 22 Converting decimal to binary 123 ÷2 61 ÷2 30 ÷2 15 ÷2 7 ÷2 3 ÷2 1 ÷2 0 remainder 1 remainder 1 remainder 0 remainder 1 remainder 1 remainder 1 remainder 1 23 Converting decimal to binary 1111011 123 ÷2 61 ÷2 30 ÷2 15 ÷2 7 ÷2 3 ÷2 1 ÷2 0 remainder 1 remainder 1 remainder 0 remainder 1 remainder 1 remainder 1 remainder 1 24 Converting decimal to binary 102 ÷2 51 ÷2 25 ÷2 12 ÷2 6 ÷2 3 ÷2 1 ÷2 0 remainder 0 remainder 1 remainder 1 remainder 0 remainder 0 remainder 1 remainder 1 25 Converting decimal to binary 102 ÷2 51 ÷2 25 ÷2 12 ÷2 6 ÷2 3 ÷2 1 ÷2 0 remainder 0 remainder 1 remainder 1 remainder 0 remainder 0 remainder 1 remainder 1 26 Converting decimal to binary 1100110 102 ÷2 51 ÷2 25 ÷2 12 ÷2 6 ÷2 3 ÷2 1 ÷2 0 remainder 0 remainder 1 remainder 1 remainder 0 remainder 0 remainder 1 remainder 1 27 Converting decimal to binary 102 ÷2 51 ÷2 25 ÷2 12 ÷2 6 ÷2 3 ÷2 1 ÷2 0 1100110 remainder 0 remainder 1 remainder 1 remainder 0 remainder 0 remainder 1 remainder 1 Most significant bit 28 Converting decimal to binary 102 ÷2 51 ÷2 25 ÷2 12 ÷2 6 ÷2 3 ÷2 1 ÷2 0 1100110 remainder 0 remainder 1 remainder 1 remainder 0 remainder 0 remainder 1 remainder 1 Least significant bit 29 Adding binary numbers • For individual bits there are only four possibilities: 0 + 0 0 0 + 1 1 1 + 0 1 1 + 1 10 30 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 11100101 + 1011101 31 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos. 1 11100101 + 1011101 0 32 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 11100101 + 1011101 10 33 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 11100101 + 1011101 010 34 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 11 1 11100101 + 1011101 0010 35 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 11 1 1 11100101 + 1011101 00010 36 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 11 1 1 11100101 + 1011101 000010 37 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 11 1 1 11100101 + 1011101 1000010 38 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 1 11 1 1 11100101 + 1011101 101000010 39 Adding binary numbers • For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 11100101 + 1011101 101000010 229 + 93 322 40 Adding binary numbers • But that only works for unsigned numbers. (positive numbers) • For signed numbers it's much more complicated. 41 Limitations of representations • None of these number representations acts exactly like the integers. • Infinitely many integers, but only 2N binary numbers for a specific N-bit representation. • That means some operations will overflow. • If the program doesn't crash when that happens, it will simply produce wrong answers (which is worse!) 42 Limitations of representations • Computer arithmetic is only an approximation of integer arithmetic. • Many of the arithmetic laws you're used to don't always hold. (See Tutorial 11 Advanced Exercise for examples.) 43 Reading • Brookshear: Sections 1.4 to 1.7 • D&D: Appendix E 44