chapter 2.pdf

Data Structure CCCS 224 Chapter 2 Numerical data structures, Integer and floating-point representations. Number systems (binary, decimal, hexadecimal…)  DATA REPRESENTATION Data Types Complements Fixed Point Representations Floating Point Representati...

Data Structure CCCS 224 Chapter 2 Numerical data structures, Integer and floating-point representations. Number systems (binary, decimal, hexadecimal…)  DATA REPRESENTATION Data Types Complements Fixed Point Representations Floating Point Representations Signed Integer Representation Other Binary Codes  Data Types DATA REPRESENTATION Information that a Computer is dealing with * Data - Numeric Data Numbers( Integer, real) - Non-numeric Data Letters, Symbols * Relationship between data elements - Data Structures Linear Lists, Trees, Rings, etc * Program(Instruction)  Data Types NUMERIC DATA REPRESENTATION Data Numeric data - numbers(integer, real) Non-numeric data - symbols, letters Number System Nonpositional number system - Roman number system Positional number system - Each digit position has a value called a weight associated with it - Decimal, Octal, Hexadecimal, Binary Base (or radix) R number - Uses R distinct symbols for each digit - Example AR = an-1 an-2... a1 a0.a-1…a-m n -1 Radix point(.) separates the integer - V(AR ) = åa R i =- m i i portion and the fractional portion R = 10 Decimal number system, R = 2 Binary R = 8 Octal, R = 16 Hexadecimal  Data Types REPRESENTATION OF NUMBERS - POSITIONAL NUMBERS Decimal Binary Octal Hexadecimal 00 0000 00 0 01 0001 01 1 02 0010 02 2 03 0011 03 3 04 0100 04 4 05 0101 05 5 06 0110 06 6 07 0111 07 7 08 1000 10 8 09 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F Binary, octal, and hexadecimal conversion 1 2 7 5 4 3 Octal 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 Binary A F 6 3 Hexa  Data Types CONVERSION OF BASES Base R to Decimal Conversion A = an-1 an-2 an-3 … a0. a-1 … a-m V(A) = S ak Rk (736.4)8 = 7 x 82 + 3 x 81 + 6 x 80 + 4 x 8-1 = 7 x 64 + 3 x 8 + 6 x 1 + 4/8 = (478.5)10 (110110)2 =... = (54)10 (110.111)2 =... = (6.785)10 (F3)16 =... = (243)10 (0.325)6 =... = (0.578703703.................)10 Decimal to Base R number - Separate the number into its integer and fraction parts and convert each part separately. - Convert integer part into the base R number → successive divisions by R and accumulation of the remainders. - Convert fraction part into the base R number → successive multiplications by R and accumulation of integer digits  Data Types EXAMPLE Fraction = 0.6875 Convert 41.687510 to base 2. 0.6875 Integer = 41 x 2 41 1.3750 20 1 x 2 10 0 0.7500 5 0 x 2 2 1 1.5000 1 0 x 2 0 1 1.0000 (41)10 = (101001)2 (0.6875)10 = (0.1011)2 (41.6875)10 = (101001.1011)2 Exercise Convert (63)10 to base 5: (223)5 Convert (1863)10 to base 8: (3507)8 Convert (0.63671875)10 to hexadecimal: (0.A3)16  Complements COMPLEMENT OF NUMBERS Two types of complements for base R number system: - R's complement and (R-1)'s complement The (R-1)'s Complement Subtract each digit of a number from (R-1) Example - 9's complement of 83510 is 16410 - 1's complement of 10102 is 01012(bit by bit complement operation) The R's Complement Add 1 to the low-order digit of its (R-1)'s complement Example - 10's complement of 83510 is 16410 + 1 = 16510 - 2's complement of 10102 is 01012 + 1 = 01102  Fixed Point Representations FIXED POINT NUMBERS Numbers: Fixed Point Numbers and Floating Point Numbers Binary Fixed-Point Representation X = xnxn-1xn-2... x1x0. x-1x-2... x-m Sign Bit(xn): 0 for positive - 1 for negative Remaining Bits(xn-1xn-2... x1x0. x-1x-2... x-m) SIGNED NUMBERS Need to be able to represent both positive and negative numbers - Following 3 representations Signed magnitude representation Signed 1's complement representation Signed 2's complement representation Example: Represent +9 and -9 in 7 bit-binary number Only one way to represent +9 ==> 0 001001 Three different ways to represent -9: In signed-magnitude: 1 001001 In signed-1's complement: 1 110110 In signed-2's complement: 1 110111 In general, in computers, fixed point numbers are represented either integer part only or fractional part only.  Fixed Point Representations ARITHMETIC SUBTRACTION Arithmetic Subtraction in 2’s complement Take the complement of the subtrahend (including the sign bit) and add it to the minuend including the sign bits. (±A)-(-B) =(±A)+ B (±A)- B=(±A)+( -B)  Floating Point Representation FLOATING POINT NUMBER REPRESENTATION * The location of the fractional point is not fixed to a certain location * The range of the representable numbers is wide F = EM mn ekek-1... e0 mn-1mn-2 … m0. m-1 … m-m sign exponent mantissa - Mantissa Signed fixed point number, either an integer or a fractional number - Exponent Designates the position of the radix point Decimal Value V(F) = V(M) * RV(E) M: Mantissa E: Exponent R: Radix Signed Integer Representation Binary addition is as easy as it gets. You need to know only four rules: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 The simplicity of this system makes it possible for digital circuits to carry out arithmetic operations. 13 Signed Integer Representation Example 1: Using signed magnitude binary arithmetic, find the sum of 75 and 46. First, convert 75 and 46 to binary, and arrange as a sum, but separate the (positive) sign bits from the magnitude bits. 14 Signed Integer Representation Example 1: Using signed magnitude binary arithmetic, find the sum of 75 and 46. Just as in decimal arithmetic, we find the sum starting with the rightmost bit and work left. 15 Signed Integer Representation Example 1: Using signed magnitude binary arithmetic, find the sum of 75 and 46. In the second bit, we have a carry, so we note it above the third bit. 16 Signed Integer Representation Example 1: Using signed magnitude binary arithmetic, find the sum of 75 and 46. The third and fourth bits also give us carries. 17 Signed Integer Representation Example 1: Using signed magnitude binary arithmetic, find the sum of 75 and 46. Once we have worked our way through all eight bits, we are done. 18  Signed Integer Representation Example: Using signed magnitude binary arithmetic, find the sum of 107 and 46. We see that the carry from the seventh bit overflows and is discarded, giving us the erroneous result: 107 + 46 = 25. 19 Signed Integer Representation The signs in signed magnitude representation work just like the signs in pencil and paper arithmetic. Example: Using signed magnitude binary arithmetic, find the sum of - 46 and - 25. Because the signs are the same, all we do is add the numbers and supply the negative sign when we are done. 20 Signed Integer Representation Mixed sign addition (or subtraction) is done the same way. Example: Using signed magnitude binary arithmetic, find the sum of 46 and - 25. The sign of the result gets the sign of the number that is larger. – Note the “borrows” from the second and sixth bits. 21 Signed Integer Representation Signed magnitude representation is easy for people to understand, but it requires complicated computer hardware. Another disadvantage of signed magnitude is that it allows two different representations for zero: positive zero and negative zero. For these reasons computer systems employ complement systems for numeric value representation. 22 Signed Integer Representation In complement systems, negative values are represented by some difference between a number and its base. In diminished radix complement systems, a negative value is given by the difference between the absolute value of a number and one less than its base. In the binary system, this gives us one’s complement. 23 Signed Integer Representation For example, in 8-bit one’s complement, positive 3 is: 00000011 negative 3 is: 11111100 In one’s complement, as with signed magnitude, negative values are indicated by a 1 in the high order bit. Complement systems are useful because they eliminate the need for subtraction. 24 Signed Integer Representation With one’s complement addition, the carry bit is “carried around” and added to the sum. Example: Using one’s complement binary arithmetic, find the sum of 48 and - 19 We note that 19 in one’s complement is 00010011, so -19 in one’s complement is: 11101100. 25 Signed Integer Representation Although the “end carry around” adds some complexity, one’s complement is simpler to implement than signed magnitude. But it still has the disadvantage of having two different representations for zero: positive zero and negative zero. Two’s complement solves this problem. Two’s complement is the radix complement of the binary numbering system. 26 Signed Integer Representation To express a value in two’s complement: If the number is positive, just convert it to binary and you’re done. If the number is negative, find the one’s complement of the number and then add 1. Example: In 8-bit one’s complement, positive 3 is: 00000011 Negative 3 in one’s complement is: 11111100 Adding 1 gives us -3 in two’s complement form: 11111101. 27 Signed Integer Representation With two’s complement arithmetic, all we do is add our two binary numbers. Just discard any carries emitting from the high order bit. – Example: Using one’s complement binary arithmetic, find the sum of 48 and - 19. We note that 19 in one’s complement is: 00010011, so -19 in one’s complement is: 11101100, and -19 in two’s complement is: 11101101. 28 Signed Integer Representation When we use any finite number of bits to represent a number, we always run the risk of the result of our calculations becoming too large to be stored in the computer. While we can’t always prevent overflow, we can always detect overflow. In complement arithmetic, an overflow condition is easy to detect. 29 Signed Integer Representation Example: Using two’s complement binary arithmetic, find the sum of 107 and 46. We see that the nonzero carry from the seventh bit overflows into the sign bit, giving us the erroneous result: 107 + 46 = -103. Rule for detecting signed two’s complement overflow: When the “carry in” and the “carry out” of the sign bit differ, overflow has occurred. 30 Signed Integer Representation Overflow and carry are tricky ideas. Signed number overflow means nothing in the context of unsigned numbers, which set a carry flag instead of an overflow flag. If a carry out of the leftmost bit occurs with an unsigned number, overflow has occurred. Carry and overflow occur independently of each other. The table on the next slide summarizes these ideas. 31 Signed Integer Representation 32  Floating Point Representation FLOATING POINT NUMBERS Example sign sign 0.1234567 0 04 mantissa exponent ==> +.1234567 x 10+04 Note: In Floating Point Number representation, only Mantissa(M) and Exponent(E) are explicitly represented. The Radix(R) and the position of the Radix Point are implied. Example A binary number +1001.11 in 16-bit floating point number representation (6-bit exponent and 10-bit fractional mantissa) 0 0 00100 100111000 Sign Exponent Mantissa or 0 0 00101 010011100  Floating Point Representation CHARACTERISTICS OF FLOATING POINT NUMBER REPRESENTATIONS Normal Form - There are many different floating point number representations of the same number → Need for a unified representation in a given computer - the most significant position of the mantissa contains a non-zero digit Representation of Zero - Zero Mantissa = 0 - Real Zero Mantissa = 0 Exponent = smallest representable number which is represented as 00... 0 ¬ Easily identified by the hardware INTERNAL REPRESENTATION AND EXTERNAL REPRESENTATION Another Computer External Representation External Representation Internal Representation Human CPU Memory External Representation Device  External Representations EXTERNAL REPRESENTATION Numbers Most of numbers stored in the computer are eventually changed by some kinds of calculations → Internal Representation for calculation efficiency → Final results need to be converted to as External Representation for presentability Alphabets, Symbols, and some Numbers Elements of these information do not change in the course of processing → No needs for Internal Representation since they are not used for calculations → External Representation for processing and presentability Decimal BCD Code 0 0000 1 0001 Example 2 0010 Decimal Number: 4-bit Binary Code 3 0011 BCD(Binary Coded Decimal) 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 End Chapter 2