Lecture 1: Number and Data Representation PDF

Lecture 1 : Number and Data Representation 1  1. Overview 1. Overview 1.1. Some Definitions Representation of Numbers Base/Radix: Decimal...

Lecture 1 : Number and Data Representation 1  1. Overview 1. Overview 1.1. Some Definitions Representation of Numbers Base/Radix: Decimal Binary Octal Hexadecimal Unsigned and Signed numbers Two’s Complement Subtraction Non-integer numbers 2 1.1. Some Definitions 1.1 Some Definitions 1.1.1. Analogue 1.1.2. Digital 1.1.1 Analogue – Signals or information that are represented by a continuously variable physical quantity. For example, electricity, light, sound... In fact, most things we encounter in our everyday world Pic Ref: bbc.co.uk 3 1.1. Some Definitions 1.1 Some Definitions 1.1.1. Analogue 1.1.2. Digital 1.1.2 Digital – Discrete values typically represented by values of a physical quantity. For example, electricity Pic Ref: answers.com 4 1.1. Some Definitions 1.1 Some Definitions 1.2. Representation Digital electronics takes different values (or ranges of 1.3. The decimal system values) of analogue signals to represent different, discrete, values. As an example, consider a light switch A light switch only has two positions. When it is ‘off’, we would measure 0 volts at the supply to the light. When it is ‘on’, we would measure 240 volts at the supply to the light. Thus, we can represent ‘on’ and ‘off’, or ‘0’ and ‘1’, with two arbitrary analogue values; ‘0’ and ‘240’ 5 1.1. Some Definitions 1.2 Representation 1.2. Representation 1.3. The decimal system All information when stored in a computer system, must use some form of internal representation ▪ The program to be executed. ▪ The numerical data to be processed. ▪ Character strings ( A....Z etc. ). 6 1.3. The decimal system 1.3 The Decimal System 1.3.1. Decimal Example What is a Decimal Value? What does 331 really mean? The position of each digit is assigned a weight. Decimal Scheme right-most digit has a weight of 100 = 1. Weighting increases by a factor of 10 for each new symbol as the position moves to the left. 7 1.3. The decimal system 1.3.1 Decimal Example 1.3.1. Decimal Example Again taking the value 331: 102 101 100 3 3 1 3 * 100 3 * 10 1*1 300 30 1 Value = 300 + 30 +1. 8 1.4. Binary 1.4 Binary 1.5. Radix or base Binary number system follows similar rules to decimal system. Except base is 2 not 10. By the BASE rules: Symbols: 0, 1 (all symbols are unique) Highest Symbol = BASE - 1. BASE = 2 this is BINARY. Example: 112 9 1.4. Binary 1.5 RADIX or BASE 1.5. Radix or base 2. The Binary Representation Scheme In any number scheme the base value defines the number of unique symbols. In the Decimal scheme we use the symbols: 0,1,2,3,4,5,6,7,8,9. The highest symbol = BASE –1. All Symbol values are UNIQUE. Example: 1110 10  2. The Binary Representation 2. The Binary Representation Scheme Scheme 2.1. Basic Conversion 2.2 Decimal to Binary Taking a simple value: 01011010 Conversion 27 26 25 24 23 22 21 20 128 64 32 16 8 4 2 1 0 1 0 1 1 0 1 0 Can you tell what this value is? 11  2.1 Basic Conversion 2. The Binary Representation Scheme Converting this representation back to a more 2.1. Basic Conversion familiar DECIMAL form we can see that all 2.2 Decimal to Binary the information necessary about the data is Conversion available. 27 26 25 24 23 22 21 20 0 1 0 1 1 0 1 0 0*128 1*64 0*32 1*16 1*8 0*4 1*2 0*1 0 + 64 + 0 + 16 + 8 + 0 + 2 + 0 = 90 12  2.2 Decimal To Binary 2. The Binary Representation Scheme Conversion 2.1. Basic Conversion Rules: 2.2 Decimal to Binary Conversion Divide the number by 2. Look at the remainder ‘1’ or ‘0’. Use the remainder as Bit value. Loop till done. Convert 2510 13 13  2.2.1 Example: 2.2 Decimal to Binary Conversion Conversion of 2510 2.2.1. Example Divis Quotie Remain or nt der 2 25 1 LSB 2 12 0 2 6 0 2 3 1 2 1 1 MSB 0 Binary Value = 110012 14  2.3 Binary To Decimal 2.3 Binary to Decimal Conversion Conversion 2.4 Most Significant Calculate the value for each Digit Position as (Symbol * Digit / Least Significant Base Weighting) for the position. Then sum all these Digit values. 3. 'Bits', 'Bytes' and Binary 11102 'Words' (1 * 23) + (1 * 22) + (1 * 21) + (0 * 20) (1 * 8) + (1 * 4) + (1 * 2) + (0 * 1) = 1410 This small number indicates the base that we are working in – Why? 15  2.4 Most Significant Digit / 2.3 Binary to Decimal Conversion Least Significant Digit 2.4 Most Significant Digit / Least Significant The concepts of the significance of the Symbol Digit positions is not unique to binary. 3. 'Bits', 'Bytes' and Units, Tens, Hundreds etc. In the decimal scheme. 'Words' Most Significant Digit is the Left - most symbol of the Number. Least Significant Digit is the Right – most symbol of the Number. Example: 110012 16 2.4 Most Significant 3. 'Bits', 'Bytes' and 'Words' Digit / Least Significant Digit 3. 'Bits', 'Bytes' and Within a computer system everything is stored or 'Words’ used in binary format. 4. Unsigned Numbers Each Binary Digit is commonly known as a Bit. Within any computer system information is stored or manipulated in groups of ‘n Bits’. 17 2.4 Most Significant 3. 'Bits', 'Bytes' and 'Words' Digit / Least Significant Digit A Byte is the smallest grouping and it is defined to 3. 'Bits', 'Bytes' and contain ‘n’ Bits. By common usage, the Byte 'Words’ usually refers to a grouping of 8 Bits. 4. Unsigned Numbers A Word is a larger grouping of Bits. Size reflected by a PC’s architecture. Again by common usage, a Word is a grouping of 16 Bits and therefore is 2 Bytes. We also have Nibbles Which are? 18 3. 'Bits', 'Bytes' and 4.Unsigned Numbers 'Words’ 4. Unsigned Numbers Any number range is defined as: 0 Max Number. In the Decimal scheme, if we write a value as 27: The magnitude of the value is 27. By convention the value is Positive. On the other hand if we write the value as: -27 It is not the same since the '-' SIGN identifies it as another value. 19 4.Unsigned Numbers 4.1 Unsigned Binary Representation 4.1 Unsigned Binary Representation The Binary representation in an unsigned form 4.2 Kilo-Mega-Giga has only a MAGNITUDE. 4.3 Unsigned Number Tables All binary combinations of the "n" Bits will uniquely identify a magnitude e.g. 0000 1111. Range 0 to 2n -1 So program variable declarations can define the size and type of storage used! 20  4.2 Kilo - Mega - Giga 4.Unsigned Numbers 4.1 Unsigned Binary Representation Within Binary these terms have slightly 4.2 Kilo-Mega-Giga different meaning to those in Decimal. 20 1 21 2 4.3 Unsigned Number Kilo = 103 = 1000 in Decimal. 22 4 Tables Kilo = 210 = 1024 in Binary. 23 8.... Mega = Kilo * Kilo = (Kilo2). 29 512 1,048,576 Binary / 1,000,000 Decimal. 210 1K Decimal: Mega = 106 / Binary: Mega = 220. 211 2K Giga = Kilo * Mega. 220 1M Why? 230 1G 240 1T 21  4.3 Unsigned Numbers Table 4.Unsigned Numbers 4.1 Unsigned Binary Look at this table of 16 values we need ‘4’ Representation Bits’ to represent all possible values. 4.2 Kilo-Mega-Giga 4.3 Unsigned Number Decimal Binary Decimal Binary Tables 0 0000 8 1000 1 0001 9 1001 2 0010 10 1010 3 0011 11 1011 4 0100 12 1100 5 0101 13 1101 6 0110 14 1110 7 0111 15 1111 22 5. Signed Numbers 5. Signed Numbers 6. Radix Complement The Decimal number system uses ‘-‘ (minus) In Binary we only have two symbols 1 and 0. But we must be able to store signed numbers in computer memory! One possible solution - signed magnitude 00010111 = +23 sign magnitude 10010111 = -23 sign magnitude 23 5. Signed Numbers 5. Signed Numbers 6. Radix Complement What effect does this have on the size of integers a computer can use? 8 bit unsigned binary number 00000000 - 11111111 0 - 25510 8 bit signed binary number 01111111 - 11111111 +12710 - -12710 but we have 00000000 and 10000000! Is this a problem? Range -(2n-1 -1) to 2n-1 -1 24 5. Signed Numbers 6. Radix complement 6. Radix Complement 2's complement Variation of sign magnitude but has some very useful characteristics. Subtraction becomes complementary addition. Convert -ve numbers to 2's complement and then add. Get subtraction through adding a negative. 30 + (-30) = 0 25  6.1 Subtraction and Two’s 6. Radix Complement Complement 6.1. Subtraction and Two’s Complement To create the 2’s complement of a negative 6.1.1. Subtraction and number. 2’s Complement 1. Invert all '1's to '0' and '0's to '1’ 2. Add 1. Each operand must have same number of bits. Example 25 - 7 25 = 00011001 7 = 00000111 26 6. Radix Complement 6.1.1 Subtraction and 2’s Comp 6.1. Subtraction and First convert -7 to 2's complement Two’s Complement 6.1.1. Subtraction and Step 1 : form 1's complement 2’s Complement 00000111 11111000 1's complement Step 2 : add 1 11111000 +1 11111001 -7 in 2's complement representation 27 6. Radix Complement 6.1.1 Subtraction and 2’s Comp 6.1. Subtraction and Two’s Complement Now add 6.1.1. Subtraction and 25 = 00011001 2’s Complement -7 = 11111001 ans = 00010010 1810 Check answer. 28 6.1. Subtraction and 6.1.2 2’s complement answers. Two’s Complement 6.1.1. Subtraction and 2’s ONLY CONVERT NEGATIVE NUMBERS! Complement 6.1.2. 2’s complement When working out the real answer of a 2’s answers complement sum. 1. Look at the most significant bit. 2. If it is a 1 then The answer is negative Change all ones to zero, all zeros to one and add one. Convert this to decimal and write the sign. 29  Example 6.1. Subtraction and Two’s Complement 6.1.1. Subtraction and 2’s Which of the following numbers are correctly Complement converted to 8 bit 2’s complement? 6.1.2. 2’s complement answers Example -3310 = 000111112 -308 = 10011000 3010 = 00011110 I really don’t know 30 6.2. 2’s Comp and Sign 6.2 2’s Comp and Sign Magnitude Magnitude 31 6.2. 2’s Comp and Sign 6.2 2’s Comp and Sign Magnitude Magnitude Number range for 2's complement 8 and 16 bit integers? -128 to +127 8 bit -32768 to +32767 16 bit Range -(2n-1) to + 2n-1 -1 Number range for the sign magnitude representation for 8 and 16 bit integers? -127 to +127 8 bit -32767 to +32767 16 bit Range -(2n-1 -1) to + 2n-1 -1 32 7. Hexadecimal(Hex) 7. Hexadecimal (Hex) 7.1. Conversion of Hexadecimal to/from Hexadecimal (Hex) number system is base 16. Decimal 7.2. Binary to Hexadecimal 16 unique symbols. Conversion Symbols: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. 7.3. Binary&Hex Conversion A = 1010, B = 1110, C = 1210, 7.4. Making Binary easier D = 1310, E = 1410, F = 1510. for Humans Example: 3E816 = 100010. 33  7. Hexadecimal (Hex) 7. Hexadecimal(Hex) 7.1. Conversion of Weight is 16 raised to the power of the position. Hexadecimal to/from Decimal Example: A1F16 7.2. Binary to Hexadecimal Conversion 7.3. Binary&Hex (A x 162) + (1 x 161) + (F x 160) Conversion 7.4. Making Binary easier 162= 256 16 1 for Humans 10 x 256 + 1 x 16 15 x 1 =259110 34  7.1 Conversion of Hexadecimal 7. Hexadecimal(Hex) to / from Decimal 7.1. Conversion of Hexadecimal to/from Hex 9AC16 Decimal (9 * 162)+ (A * 161) + (C * 160) = 2476 7.2. Binary to Hexadecimal 2304 + 160 + 12 = 2476 Conversion 137110 7.3. Binary&Hex Divisor Quotient Remainder Conversion 7.4. Making Binary easier for Humans 16 1371 11 =B 16 85 5 16 5 5 Result = 55B16 0 35 7. Hexadecimal(Hex) 7.2 Binary to Hexadecimal Conversion 7.1. Conversion of Comparison of the Hexadecimal to/from Decimal binary and 7.2. Binary to hexadecimal number Hexadecimal Conversion systems. 7.3. Binary&Hex Conversion What do you notice? 7.4. Making Binary easier for Humans 36 7. Hexadecimal(Hex) 7.2 Binary to Hexadecimal Conversion 7.1. Conversion of A single Hex digit can Hexadecimal to/from represent a 4-bit binary Decimal number. 7.2. Binary to Hexadecimal Conversion Example: 7.3. Binary&Hex (110101111)2 Conversion 0001 1010 1111 7.4. Making Binary easier 1 A F for Humans (110101111)2 = (1AF)16 1 A F 162 161 160 37 7. Hexadecimal(Hex) 7.3 Binary & Hex Conversion 7.1. Conversion of Hexadecimal to/from Consider the value: Decimal 7.2. Binary to Hexadecimal 27 26 25 24 23 22 21 20 Conversion 7.3. Binary&Hex 0 1 0 1 1 0 1 1 Conversion 7.4. Making Binary easier Split this into groupings of 4 Bits for Humans This gives the Hex – 5B16 Hex is simply groupings of 4 Binary Bits. 38 7. Hexadecimal(Hex) 7.4 Making Binary Easier for Humans 7.1. Conversion of Hexadecimal to/from Why was Hexadecimal chosen? Decimal Single hex digit = four bits. 7.2. Binary to Hexadecimal 2 hex digits per byte. Conversion Allows simple conversion to and from binary. 7.3. Binary&Hex Simpler to convert between Base 2 and Base 10. The meaning of a value can be communicated simply and effectively, Conversion both at the computer (i.e. Base 2) level and also so that humans (i.e. 7.4. Making Binary easier Base 10) can visualise the meaning. for Humans Hex is easier for humans to understand and communicate. Example: A16 = 10102 = 1010. 39 8.OCTAL Radix 8 8. OCTAL Radix 8 9. Non Integer Numbers The only other commonly used number base is 8 or Octal. Why use octal? Direct conversion to binary How would you represent 23 decimal in octal? Hint 2310 is 000101112 in 8 bit binary. The answer is : 027 40 8.OCTAL Radix 8 9. Non Integer Numbers 9. Non Integer Numbers Can we always use WHOLE values? It would be nice if we could. Bank balances might be interesting. We need to look at what are called Floating Point numbers. Values such as 3.142, etc. Numbers with a decimal point! Data types such as double (in Java and C). 41 9. Non Integer Numbers 9.1 Scientific Notation 9.1. Scientific Notation 9.2. Scientific Notation: This is a way of expressing very large and very Floating Point Numbers small numbers. 537,000,000 is written 5.37 x 108 5.37 is called the Mantissa. 108 is called the Exponent. 0.000136 is written 1.36 x 10─4 1.36 is called the Mantissa. 10─4 is called the Exponent. 42 9. Non Integer Numbers 9.2 Scientific Notation: 9.1. Scientific Notation Note that a positive exponent tells you how many places to 9.2. Scientific Notation: move the decimal point to the right, making the number Floating Point Numbers bigger. 9.3. Binary: Floating A negative Exponent is how many places to move the Point Format decimal point to the left, making the number smaller. 1.005 x 102 = 100.5 1.005 x 10-2 = 0.01005 1.005 x 100 = 1.005 1.005 x 104 = 10,050 These are called Floating Point numbers. 43 9.2. Scientific Notation: 9.3 Binary: Floating Point Format Floating Point Numbers 9.3. Binary: Floating Expressing a number as a Mantissa and an Point Format Exponent allows us to store Floating Point numbers in a format that only requires whole 9.4. Floating Point in numbers. Decimal Sign = 1 bit. Mantissa = 7 bits. Exponent = 8 bit signed magnitude. Total = 16 bits. 5.62510 +101.10102 1.011010 x 22 44 9.3. Binary: Floating 9.4 Floating Point in Decimal Point Format 9.4. Floating Point in oWhat does 3.14210 actually mean? Decimal 9.5. Floating Point in 100 Point 10-1 10-2 10-3 Binary 1 1/10 1/100 1/1000 3. 1 4 2 o3.142 = (3 * 1) + (1 * 1/10) + (1 * 4/100) + (1 * 2/1000) = 3 + 0.1 + 0.04 + 0.002 45 9.4. Floating Point in 9.5 Floating Point in Binary Decimal 9.5. Floating Point in o What is 1.1012? Binary 9.6. Limitation in Binary 20 Point 2-1 2-2 2-3 1 1/2 1/4 1/8 1. 1 0 1 o 1.1012 = (1 * 1) + (1 * 1/2) + 0 + (1 * 1/8) = 1 + 0.5 + 0 + 0.125 = 1.62510 46 9.5. Floating Point in 9.6 Limitation in Binary Binary 9.6. Limitation in Binary The Columns as we go RIGHT after the POINT 9.7. Converting Decimal to have the place values. Binary 1/2 1/4 1/8 1/16 1/32 0.5 0.25 0.125 0.0625 0.03125 When converting Floating Point decimal numbers to binary using a fixed number of places. NOT ALL VALUES ARE POSSIBLE! 47 9.5. Floating Point in 9.7 Converting Decimal to Binary Binary 9.6. Limitation in Binary Use continuous multiplication by 2. 9.7. Converting Decimal to Binary Each 1 or 0 to the left of the point of the result 9.7.1. Example: Decimal contributes to the binary number. To Binary Continue until the fractional part is 0. Or until you obtain the answer to the accuracy you need. 48 9.6. Limitation in Binary 9.7.1 Example: Decimal to Binary 9.7. Converting Decimal to Binary Take the Decimal Fraction: 0.35 9.7.1. Example: Decimal To Binary 0.35 x 2 0.70 0 MSB 0.70 x 2 1.4 1 0.4 x 2 0.8 0 0.8 x 2 1.6 1 0.6 x 2 1.2 1 LSB 0.2 x 2 0.4 0 and so on Answer: 0.35 = 0.010110 …and so on 49 9.7.1. Example: Decimal to 9.7.2 How close is this answer to 0.35? Binary 9.7.2. How close is this 0.0101102 answer to 0.35? 20 2-1 2-2 2-3 2-4 2-5 2-6 9.8 Accuracy of Floating Point Data 0. 0 1 0 1 1 0 0*20 0 1* 2-2 = 1* 0.25 0.25 1* 2-4 = 1* 0.0625 0.0625 1* 2-5 = 1* 0.0625 0.03125 0.34375 50 9.7.1. Example: Decimal to 9.8 Accuracy of Floating Point Data Binary 9.7.2. How close is this Accuracy defined as closeness to true value. answer to 0.35? Data is inputted to a program in Decimal floating point format 9.8 Accuracy of Floating (e.g. via the keyboard). Point Data It is converted to a binary floating point format of fixed size. This may involve some loss of accuracy. Floating Point arithmetic is only approximate. Integer arithmetic is exact. 51 10. Storage Needs 10 Storage Needs 10.1. Precision 10.2. Range 10.3. Formats that have been used 10.4. IEEE Format now Used 10.5. Floating Point Arithmetic 52 10. Storage Needs 10.1 Precision 10.1. Precision 10.2. Range Determined by the number of bits used to store the 10.3. Formats that have Mantissa. been used 10.4. IEEE Format now A high precision format will result in more Used accurate floating point arithmetic. 10.5. Floating Point Most languages provide a choice: Arithmetic Single precision. Double precision. 53 10. Storage Needs 10.3 Formats That have been Used 10.1. Precision 10.2. Range 10.3. Formats that have been used 10.4. IEEE Format now Used 10.5. Floating Point Arithmetic 55 10. Storage Needs 10.4 IEEE Format now Used 10.1. Precision IEEE 754 floating point standard. 10.2. Range 10.3. Formats that have Single Precision (32 bits): been used Mantissa: 10.4. IEEE Format now 1 Bit for Sign / 23 Bits for Value. Used Exponent: 10.5. Floating Point 8 Bits. Arithmetic Double Precision (64 bits): Mantissa: 1 Bit for Sign / 52 Bits for Value. Exponent: 11 Bits. 56 10.4. IEEE Format now 11. Summary Used 10.5. Floating Point Representation of Numbers Arithmetic 11. Summary Base/Radix: Hex and Octal Non-integer numbers and Floating-Point numbers 58 59