Report

Chapter 2 Representing and Manipulating Information Prof. Qi Tian CS 3843 Fall 2013 http://www.cs.utsa.edu/~qitian/CS3843/ 1 Summary of Lectures • 09-30-2013 (Monday) – Section 2.4.4 Rounding Example – In-class Quiz 2 – Reminder: Midterm 1 on Monday Oct. 7, 2013 – Practice Problems for Midterm One 2 Summary of Lectures • 09-27-2013 (Friday) – – – – IEEE Rounding Methods Practice Problem Quiz 2 next Monday Midterm 1 on Monday Oct. 7, 2013 • 09-25-2013 (Wednesday) – Examples for IEEE Floating Point Representation • 09-23-2013 (Monday) – Section 2.4 IEEE Floating Point Representation (cont.) 3 Summary of Lectures • 09-20-2013 (Friday) – Section 2.4 IEEE Floating Point Representation (cont.) • 09-18-2013 (Wednesday) – Section 2.4 IEEE Floating Point Representation • 09-16-2013 (Monday) – Section 2.3.1 Unsigned Addition and Unsigned Subtraction – Section 2.3.2 Two’s Complement Addition – Quiz 1 4 Summary of Lectures • 09-13-2013 (Friday) – Questions on P.9 of Assignment 1 – Section 2.3.1 Unsigned Addition – Quiz 1 • 09-11-2013 (Wednesday) – Section 2.1.10 Shift Operations • Practice Problem 4 – Questions on Assignment 1 • 09-09-2013 (Monday) – Practice Problems 1-3 5 Summary of Lectures • 09-06-2013 (Friday) – Section 2.2.3 Representing Negative Numbers • Sign & Magnitude System • Two’s Complement System • One’s Complement System • 09-04-2013 (Wednesday) – Section 2.1.2-2.1.10 • Word size/data size/addressing and byte ordering • Boolean Algebra and Logical Operations in C 6 Summary of Lectures • 08-30-2013 (Friday) – Conversion between decimal and base R number • Integer • Fractional number • 08-28-2013 (Wednesday) – Syllabus – Information Storage – Conversion between Binary and Hexadecimal Number 7 Practice Problem 1 - Bit-level Operations in C C expression Binary Representation Binary Result Hexadecimal result ~0x41 ~[0100 0001] [1011 1110] 0x BE ~0x00 0x69 & 0x55 0x69 | 0x55 8 Practice Problem 1 - Bit-level Operations in C C expression Binary Representation Binary Result Hexadecimal result ~0x41 ~[0100 0001] [1011 1110] 0x BE ~0x00 ~[0000 0000] [1111 1111] 0x FF 0x69 & 0x55 [0110 1001]&[0101 0101] [0100 0001] 0x 41 0x69 | 0x55 [0110 1001]|[0101 0101] 0x 7D [0111 1101] 9 Practice Problem 2 - Boolean Operations (bit-level and logical operation in C) Suppose x and y have byte values 0x66 and 0x39, respectively. Fill in the following table indicating the byte value of the different C expressions: Expression Value Expression x&y x && y x| y x || y ~x | ~y !x ||!y x & !y x && ~y Value 10 Practice Problem 2 - Boolean Operations (bit-level and logical operation in C) Suppose x and y have byte values 0x66 and 0x39, respectively. Fill in the following table indicating the byte value of the different C expressions: Expression Value Expression Value x&y 0x20 x && y 0x 1 x| y 0x7F x || y 0x 1 ~x | ~y 0x DF !x ||!y 0x 0 x & !y 0x 0 x && ~y 0x 1 11 Practice Problem 3 Representing Negative Numbers Q1. Using a 8-bit word, find the binary representation of -27. a) Using Sign and Magnitude System b) Using 1’s Complement System c) Using 2’s Complement System 12 Practice Problem 3 Representing Negative Numbers Q1. Using a 8-bit word, find the binary representation of -27. a) Using Sign and Magnitude System N = 27 = 0001, 1011 -27 = 1001,1011 b) Using 1’s Complement System N = 27 = 0001, 1011 N = 1110, 0100 b) Using 2’s Complement System N* = 1110, 0101 13 Practice Problem 3 Representing Negative Numbers Q2. Using a 12-bit word, find the binary representation of -27. a) Using Sign and Magnitude System b) Using 1’s Complement System c) Using 2’s Complement System 14 Practice Problem 3 Representing Negative Numbers Q2. Using a 12-bit word, find the binary representation of -27. a) Using Sign and Magnitude System N = 27 = 0000, 0001, 1011 -27 = 1000, 0001,1011 (not sign extension from 8 bit) b) Using 1’s Complement System N = 27 = 0000, 0001, 1011 N = 1111,1110, 0100 (sign extension from 8 bit) b) Using 2’s Complement System N* = 1111, 1110, 0101 (sign extension from 8 bit) 15 Section 2.2.1 Integer Representation C data type Bytes Minimum Maximum char 1 -128 127 unsigned char 1 0 255 short (int) 2 -32,768 32,767 unsigned short (int) 2 0 65,535 int 4 -2,147,483,648 2,147,483,647 unsigned (int) 4 0 4,294,967,295 long (int) 4 -2,147,483,648 2,147,483,647 unsigned long (int) 4 0 4,294,967,295 long long (int) 8 -9,223,372,036,854,775,808 9,223,372,036,854,775,807 Unsigned long long (int) 8 0 18,446,744,073,709,551,615 Typical range for C integral data type on 32-bit machine 17 Section 2.2 Integer Representation C data type Bytes Minimum Maximum char 1 -128 127 unsigned char 1 0 255 short (int) 2 -32,768 32,767 unsigned short (int) 2 0 65,535 int 4 -2,147,483,648 2,147,483,647 unsigned (int) 4 0 4,294,967,295 long (int) 8 -9,223,372,036,854,775,808 9,223,372,036,854,775,807 unsigned long (int) 8 0 18,446,744,073,709,551,615 long long (int) 8 -9,223,372,036,854,775,808 9,223,372,036,854,775,807 Unsigned long long (int) 8 0 18,446,744,073,709,551,615 Typical range for C integral data type on 64-bit machine 18 Section 2.1.5 ASCII Code • A character is usually represented as a single byte by using the ASCII code. • Strings are represented as arrays of characters terminated by the null character. • ASCII – American Standard Code for Information Interchange – 7-bit code (128 ASCII Characters) – Some properties: • • • • Codes for digits are consecutive: ‘0’ = 48, ‘1’ =49, etc. Codes for upper case letters are consecutive: ‘A’=65, ‘B’=66, etc. Codes for lower case letters are consecutive: ‘a’=97, ‘b’=98, etc. Maximum value is 127. 19 ASCII Code • A compact table in hex and decimal 20 Section 2.1.10 Shift Operations • X =[xn-1,xn-2,…, x1, x0] • Left shift: x << k (C expression) – Result: [xn-k-1, xn-k-2, …, x0, 0,…, 0] – Dropping off the k most significant bits, and filled the right end with k zeros • Right shift: x >> k (C expression) – Logical shift: x >>L k • Result: [0,…,0,xn-1, xn-2, …, xk] – Arithmetic shift: x >>Ak • Result: [xn-1,…, xn-1, xn-1, …, xk] 21 Section 2.1.10 Shift Operations • • • • x << k is equivalent to multiply by 2k, x*2k x >>A k is equivalent to divide by 2k , x/2k k < 32 for integer x Many C compilers perform arithmetic right shifts on negative values in which the vacated values are filled with the sign bit. 22 Section 2.3.6 – Multiplying by constants • A left shift by k bits is equivalent to multiplying by 2 k. • Using addition if a small number of 1 bits x * 49 = x * [110001]= x*[32 + 16 + 1] = x * [25+24+20] = (x*25)+(x*24)+(x*20)= (x<<5) + (x<<4) +x • Using subtraction if a large number of 1 bits in a row x * 78 = x*[1001110] = x*[26+24-2] = (x<<6)+(x<<4)-(x<<1) 23 Practice Problem 4 • For each of the following values of K, find ways to express x *K using only the specified number of operations, where we consider both addition and subtractions to have comparable cost. K Shifts Add/Subs 6 2 1 31 1 1 -6 2 1 55 2 2 Expression 24 Section 2.2.2 Unsigned Encodings • There is only one standard way of encoding unsigned integers. • Bit vector x = [xw-1, xw-2, …, x1, x0] with w bits • Binary to unsigned number: B2Uw(x)=2w-1xw-1+2w-2 xw-2++21 x1+20 x0 • Each integer between 0 and 2w-1 has a unique representation with w bits. 25 Section 2.2.2 Unsigned Encodings • Examples: B2U4([0011])=0x23+0x22+1x21+1x20=3 B2U4([1011])=1x23+0x22+1x21+1x20=11 26 Section 2.3.1 Unsigned Addition • w bits, maximum value is 2w-1. • It might take w+1 bits to represent the value of x+y. • Addition is done modulo 2w. • When x+y does not produce the correct result, we say that overflow has occurred. • In C, overflow is not detected. • How can you test whether adding x and y will produce an overflow? 27 Section 2.3.1 Unsigned Addition • What is 28 Section 2.3.1 Unsigned Addition • What is Sol: 139+147>28 therefore =(139+147)-28=30 29 Unsigned Addition and Substraction Unsigned Addition Unsigned Substraction 30 Section 2.4 IEEE Floating Point Number of bits Precision s exp frac total single 1 8 23 32 double 1 11 52 64 extended 1 15 64 80 31 Example: A 6-bit format s exp (3 bits) frac (2 bits) • What is the bias: 22 -1 = 3. • How many different values can be represented with 6 bits: 26 = 64. • How many of these are NaN: 6 • How many of these are infinity: 2 • How many of these are positive, normalized: 6×4 = 24 • How many of these are negative, normalized: 6×4 = 24 • How many of values are zero (denormalized): 2 • How many of these are denormalized > 0: 3 • How many of these are denormalized < 0: 3 32 A 6-bit format (continued) • What are the positive normalized values? s = 0; exp = 1, 2, 3, 4, 5, or 6 frac = 00, 01, 10, or 11, corresponding to 1.00, 1.01, 1.10, and 1.11 V = 1.frac * 2exp – 3 • Smallest positive normalized number: 0.25 33 A 6-bit format (continued) • Denormalized values: M = frac * 2-2 = frac/4: 0, .25, .5, .75 value = M 2-2 = M/4. The values are 0, .0625, 0.125, and 0.1875 Denormalized spacing: 0.0625 • Largest denormalized number: 0.1875 34 A 6-bit format (continued) • Denormalized values: M = frac * 2-2 = frac/4: 0, .25, .5, .75 value = M × 2-2 = M/4. The values are 0, .0625, 0.125, and 0.1875 Denormalized spacing: 0.0625 • Largest denormalized number: 0.1875 35 A 6-bit format (continued) • The denormalized values are equally spaced: spacing is 0.0625. • The normailzed values are not equally spaced. 36 Example: Rounding Mode Round-to-even Round-towards-zero 1.4 1.6 1.5 2.5 -1.5 Round-down Round-up 37 Example: Rounding Mode Round-to-even Round-towards-zero Round-down Round-up 1.4 1 1 1.6 2 1 1.5 2 1 2.5 2 2 -1.5 -2 -1 1 2 1 2 1 2 2 3 -2 -1 38 Rounding Example • American Patriot Missile Battery in the first Gulf-War, Feb. 25, 1991, failed to intercept an incoming Iraqi Scud missile. • Disaster Result: 28 soldiers killed • Failure Analysis by the US General Accounting Office (GAO): – The underlying cause was an impression in a numeric calculation. 39