CS61C L02 Number Representation (1)Garcia, Spring 2008 © UCBLecturer SOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61cCS61C : Machine StructuresLecture #2 – Number Representation2007-01-25There are two handoutstoday at the front andback of the room!Great book ⇒ The Universal Historyof Numbersby Georges IfrahCS61C L02 Number Representation (2)Garcia, Spring 2008 © UCBReview• Continued rapid improvement in computing• 2X every 2.0 years in memory size;every 1.5 years in processor speed;every 1.0 year in disk capacity;• Mooreʼs Law enables processor(2X transistors/chip ~1.5 yrs)• 5 classic components of all computers Control Datapath Memory Input OutputProcessor}CS61C L02 Number Representation (3)Garcia, Spring 2008 © UCBPutting it all in perspective…“If the automobile had followed the samedevelopment cycle as the computer,a Rolls-Royce would today cost $100,get a million miles per gallon,and explode once a year,killing everyone inside.”– Robert X. CringelyCS61C L02 Number Representation (4)Garcia, Spring 2008 © UCBDecimal Numbers: Base 10Digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9Example:3271 =(3x103) + (2x102) + (7x101) + (1x100)CS61C L02 Number Representation (5)Garcia, Spring 2008 © UCBNumbers: positional notation• Number Base B ⇒ B symbols per digit:• Base 10 (Decimal): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9Base 2 (Binary): 0, 1• Number representation:• d31d30 ... d1d0 is a 32 digit number• value = d31 × B31 + d30 × B30 + ... + d1 × B1 + d0 × B0• Binary: 0,1 (In binary digits called “bits”)• 0b11010 = 1×24 + 1×23 + 0×22 + 1×21 + 0×20= 16 + 8 + 2= 26• Here 5 digit binary # turns into a 2 digit decimal #• Can we find a base that converts to binary easily?#s often written0b…CS61C L02 Number Representation (6)Garcia, Spring 2008 © UCBHexadecimal Numbers: Base 16• Hexadecimal:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F• Normal digits + 6 more from the alphabet• In C, written as 0x… (e.g., 0xFAB5)• Conversion: Binary⇔Hex• 1 hex digit represents 16 decimal values• 4 binary digits represent 16 decimal values⇒1 hex digit replaces 4 binary digits• One hex digit is a “nibble”. Two is a “byte”• 2 bits is a “half-nibble”. Shave and a haircut…• Example:• 1010 1100 0011 (binary) = 0x_____ ?CS61C L02 Number Representation (7)Garcia, Spring 2008 © UCBDecimal vs. Hexadecimal vs. BinaryExamples:1010 1100 0011 (binary)= 0xAC310111 (binary)= 0001 0111 (binary)= 0x170x3F9= 11 1111 1001 (binary)How do we convert betweenhex and Decimal?00 0 000001 1 000102 2 001003 3 001104 4 010005 5 010106 6 011007 7 011108 8 100009 9 100110 A 101011 B 101112 C 110013 D 110114 E 111015 F 1111MEMORIZE!Examples:1010 1100 0011 (binary)= 0xAC310111 (binary)= 0001 0111 (binary)= 0x170x3F9= 11 1111 1001 (binary)How do we convert betweenhex and Decimal?CS61C L02 Number Representation (8)Garcia, Spring 2008 © UCBWhat to do with representations of numbers?• Just what we do with numbers!• Add them• Subtract them• Multiply them• Divide them• Compare them• Example: 10 + 7 = 17• …so simple to add in binary that we canbuild circuits to do it!• subtraction just as you would in decimal• Comparison: How do you tell if X > Y ? 1 0 1 0+ 0 1 1 1-------------------------1 0 0 0 111CS61C L02 Number Representation (9)Garcia, Spring 2008 © UCBBIG IDEA: Bits can represent anything!!• Characters?• 26 letters ⇒ 5 bits (25 = 32)• upper/lower case + punctuation ⇒ 7 bits (in 8) (“ASCII”)• standard code to cover all the worldʼslanguages ⇒ 8,16,32 bits (“Unicode”)www.unicode.com• Logical values?• 0 ⇒ False, 1 ⇒ True• colors ? Ex:• locations / addresses? commands?• MEMORIZE: N bits ⇔ at most 2N thingsRed (00) Green (01) Blue (11)CS61C L02 Number Representation (10)Garcia, Spring 2008 © UCBHow to Represent Negative Numbers?• So far, unsigned numbers• Obvious solution: define leftmost bit to be sign!• 0 ⇒ +, 1 ⇒ –• Rest of bits can be numerical value of number• Representation called sign and magnitude• MIPS uses 32-bit integers. +1ten would be:0000 0000 0000 0000 0000 0000 0000 0001• And –1ten in sign and magnitude would be:1000 0000 0000 0000 0000 0000 0000 0001CS61C L02 Number Representation (11)Garcia, Spring 2008 © UCBShortcomings of sign and magnitude?• Arithmetic circuit complicated• Special steps depending whether signs arethe same or not• Also, two zeros• 0x00000000 = +0ten• 0x80000000 = –0ten• What would two 0s mean for programming?• Therefore sign and magnitude abandonedCS61C L02 Number Representation (12)Garcia, Spring 2008 © UCBAnother try: complement the bits• Example: 710 = 001112 –710 = 110002• Called Oneʼs Complement• Note: positive numbers have leading 0s,negative numbers have leadings 1s.00000 00001 01111...111111111010000 ...• What is -00000 ? Answer: 11111• How many positive numbers in N bits?• How many negative numbers?CS61C L02 Number Representation (13)Garcia, Spring 2008 © UCBShortcomings of Oneʼs complement?• Arithmetic still a somewhat complicated.• Still two zeros• 0x00000000 = +0ten• 0xFFFFFFFF = -0ten• Although used for awhile on somecomputer products, oneʼs complementwas eventually abandoned becauseanother solution was better.CS61C L02 Number Representation (14)Garcia, Spring 2008 © UCBStandard Negative Number Representation• What is result for unsigned numbers if triedto subtract large number from a small one?• Would try to borrow from string of leading 0s,so result would have a string of leading 1s 3 - 4 ⇒ 00…0011 – 00…0100 = 11…1111• With no obvious better alternative, pickrepresentation that made the hardware simple• As with sign and magnitude,leading 0s ⇒ positive, leading 1s ⇒ negative 000000...xxx is ≥ 0, 111111...xxx is < 0 except 1…1111 is -1, not -0 (as in sign & mag.)• This representation is Twoʼs ComplementCS61C L02 Number Representation (15)Garcia, Spring 2008 © UCB2ʼs Complement Number “line”: N = 5• 2N-1 non-negatives• 2N-1 negatives• one zero• how manypositives?0000000001000101111111110100000111110001012-1-2-15-1615......-311101-41110000000 00001 01111...111111111010000 ...CS61C L02 Number Representation (16)Garcia, Spring 2008 © UCBTwoʼs Complement Formula • Can represent positive and negative numbersin terms of the bit value times a power of
View Full Document