inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 2 Number Rep Intro to C 2007 06 26 Scott Beamer Instructor Google goes Green sfgate com CS61C L2 Number Representation Introduction to C 1 Beamer Summer 2007 UCB Review 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 Output Processor Decimal for human calculations binary for CS61C L2 Number Representation Introduction to C 2 Beamer Summer 2007 UCB Putting it all in perspective If the automobile had followed the same development 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 Cringely CS61C L2 Number Representation Introduction to C 3 Beamer Summer 2007 UCB What 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 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 so simple to add in binary that we can build circuits to do it subtraction just as you would in decimal Comparison How do you tell if X Y CS61C L2 Number Representation Introduction to C 4 Beamer Summer 2007 UCB Which base do we use Decimal great for humans especially when doing arithmetic Hex if human looking at long strings of binary numbers its much easier to convert to hex and look 4 bits symbol Terrible for arithmetic on paper Binary what computers use you will learn how computers do To a computer numbers always binary Regardless of how number is written 32ten 3210 0x20 1000002 0b100000 Use subscripts ten hex two in book slides when might be confusing Beamer Summer 2007 UCB CS61C L2 Number Representation Introduction to C 5 BIG 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 s languages 8 16 32 bits Unicode www unicode com Logical values 0 False 1 True colors Ex Red 00 Green 01 Blue 11 locations addresses commands MEMORIZE N bits at most 2N things CS61C L2 Number Representation Introduction to C 6 Beamer Summer 2007 UCB How 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 0001 CS61C L2 Number Representation Introduction to C 7 Beamer Summer 2007 UCB Shortcomings of sign and magnitude Arithmetic circuit complicated Special steps depending whether signs are the same or not Also two zeros 0x00000000 0ten 0x80000000 0ten What would two 0s mean for programming Therefore sign and magnitude abandoned CS61C L2 Number Representation Introduction to C 8 Beamer Summer 2007 UCB Another try complement the bits 710 001112 710 110002 Example Called One s Complement Note positive numbers have leading 0s negative numbers have leadings 1s 00000 00001 01111 10000 11110 11111 What is 00000 Answer 11111 How many positive numbers in N bits How many negative ones CS61C L2 Number Representation Introduction to C 9 Beamer Summer 2007 UCB Shortcomings of One s complement Arithmetic still a somewhat complicated Still two zeros 0x00000000 0ten 0xFFFFFFFF 0ten Although used for awhile on some computer products one s complement was eventually abandoned because another solution was better CS61C L2 Number Representation Introduction to C 10 Beamer Summer 2007 UCB Standard Negative Number Representation What is result for unsigned numbers if tried to 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 pick representation 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 Complement CS61C L2 Number Representation Introduction to C 11 Beamer Summer 2007 UCB 2 s Complement Number line N 5 11111 00000 00001 2N 1 non11110 00010 negatives 0 1 1 11101 2 3 11100 4 2 2N 1 negatives one zero how many positives 15 16 15 10001 10000 01111 00000 10000 11110 11111 CS61C L2 Number Representation Introduction to C 12 00001 01111 Beamer Summer 2007 UCB Two s Complement for N 32 0000 0000 0000 0000 0000 0000 0111 1111 0111 1111 0111 1111 1000 0000 1000 0000 1000 0000 1111 1111 1111 1111 1111 1111 0000 0000 0000two 0000 0000 0001two 0000 0000 0010two 1111 1111 1111 0000 0000 0000 1111 1111 1111 0000 0000 0000 0ten 1ten 2ten 1101two 1110two 1111two 0000two 0001two 0010two 2 147 483 645ten 2 147 483 646ten 2 147 483 647ten 2 147 483 648ten 2 147 483 647ten 2 147 483 646ten 1111 1111 1101two 1111 1111 1110two 1111 1111 1111two 3ten 2ten 1ten One zero 1st bit called sign bit 1 extra negative no positive 2 147 483 648ten CS61C L2 Number Representation Introduction to C 13 Beamer Summer 2007 UCB Two s Complement Formula Can represent positive and negative numbers in terms of the bit value times a power of 2 d31 x 231 d30 x 230 d2 x 22 d1 x 21 d0 x 20 Example 1101two 1x 23 1x22 0x21 1x20 23 22 0 20 8 4 0 1 8 5 3ten CS61C L2 Number Representation Introduction to C 14 Beamer Summer 2007 UCB Two s Complement shortcut Negation Check out www cs berkeley edu dsw twos complement html Change every 0 to 1 and 1 to 0 invert or complement then add 1 to the result Proof Sum of number and its one s complement must be 111 111two However 111 111two 1ten Let x one s complement representation of x Then x x 1 x x 1 0 x 1 x Example 3 to 3 to 3 x 1111 1111 1111 1111 1111 1111 1111 1101 two x 0000 0000 0000 0000 0000 0000 0000 0010 two 1 0000 0000 0000 0000 0000 0000 0000 0011 two 1111 1111 1111 1111 1111 1111 1111 1100 two 1 1111 1111 1111 1111 1111 1111 1111 1101 two You should be able to do this in your head CS61C L2 Number Representation Introduction to C 15 Beamer Summer 2007 UCB Two s comp shortcut Sign extension Convert 2 s complement number rep using n bits to more than n bits Simply replicate the most significant bit sign bit of smaller to fill new bits 2 s comp positive number has infinite 0s 2 s comp negative number has infinite 1s Binary representation hides
View Full Document
Unlocking...