From Bits and Gates to C and Beyond: Bits, Data Types, and Operations (PDF)

Because learning changes everything. ® From Bits and Gates to C and Beyond Bits, Data Types, and Operations Chapter 2 © 2020 McGraw-Hill Education. All rights reserved. Authorized only for instructor use in the classroom. No reproduction or further distribution...

Because learning changes everything. ® From Bits and Gates to C and Beyond Bits, Data Types, and Operations Chapter 2 © 2020 McGraw-Hill Education. All rights reserved. Authorized only for instructor use in the classroom. No reproduction or further distribution permitted without the prior written consent of McGraw-Hill Education.  How do we represent data in a computer? At the lowest level, a computer is an electronic machine. Works by controlling the flow of electrons. Easy to recognize two conditions: 1. Presence of a voltage – we’ll call this state “1.” 2. Absence of a voltage – we’ll call this state “0.” We could base the state on the value of the voltage, but control and detection circuits are more complex. Compare sticking a lightbulb (or your finger) in a socket versus using a voltmeter. © McGraw Hill 2  Computer is a Binary Digital system Digital = finite number of values (compared to “analog” = infinite values) Binary = only two values: 0 and 1 Unit of information = binary digit, or “bit” Circuits (see Chapter 3) will pull voltage down towards zero, or will pull up towards the highest voltage. Grey areas represent noise margin -- allowable deviation due to resistance, capacitance, interference from other circuits, temperature, etc. More reliable than analog. Access the text alternative for slide images. © McGraw Hill 3  More than two values... Each "wire" in a logic circuit represents one bit = 0 or 1. Values with more than two states require multiple wires (bits). With two bits, can represent four different values: 00, 01, 10, 11 With three bits, can represent eight different values: 000, 001, 010, 011, 100, 101, 110, 111 With n bits, can represent 2n different values. © McGraw Hill 4  What kinds of values do we want to represent? Numbers - integer, fraction, real, complex,... Text - characters, strings... Images - pixels, colors, shapes... Sound Video Logical - true, false Instructions All data is represented as a collection of bits. We encode a value by assigning a bit pattern to represent that value. We perform operations (transformations) on bits, and we interpret the results according to how the data is encoded. © McGraw Hill 5  Data Type In a computer system, we need a representation of data and operations that can be performed on the data by the machine instructions or the computer language. This combination of representation + operations is known as a data type. Type Representation Operations Unsigned integers binary add, multiply, etc. Signed integers 2's complement binary add, multiply, etc. Real numbers IEEE floating-point add, multiply, etc. Text characters ASCI I input, output, compare © McGraw Hill 6  Unsigned Integers 1 Non-positional notation (unary) Could represent a number (“5”) with a string of ones (“11111”). Problems? Weighted positional notation (binary) Like decimal numbers: “329.” “3” is worth 300, because of its position, while “9” is only worth 9. Since only 0 and 1 digits, use a binary (base-two) number system. Access the text alternative for slide images. © McGraw Hill 7  Unsigned Integers 2 Encode a decimal integer using base-two binary number n Use n bits to represent values from 0 to 2  1 22 21 20 value 0 0 0 0 0 0 1 1 0 1 0 2 0 1 1 3 1 0 0 4 1 0 1 5 1 1 0 6 1 1 1 7 © McGraw Hill 8  Unsigned Binary Arithmetic Base-2 addition -- just like base-10 Add from right to left, propagating carry. Can also do subtraction, multiplication, etc., using base-2. Access the text alternative for slide images. © McGraw Hill 9  Signed Integers How to represent positive (+) and negative (−)? n With n bits, we have 2 encodings. Use half of the patterns (the ones starting with zero) to represent positive numbers. Use the other half (the ones starting with one) to represent negative numbers. Three different encoding schemes Signed-magnitude. 1's complement. 2's complement. © McGraw Hill 10  Signed-Magnitude Leftmost bit represents the sign of the number. 0 = positive 1 = negative Remaining bits represent the magnitude of the number using the binary notation used for unsigned integers. Examples of 5-bit signed-magnitude integers: 00101 = +5 (sign = 0, magnitude = 0101) 10101 = −5 (sign = 1, magnigude = 0101) 01101 = +13 (sign = 0, magnitude = 1101) 10010 = −2 (sign = 0, magnitude = 0010) © McGraw Hill 11  1's complement To get a negative number, start with a positive number (with zero as the leftmost bit) and flip all the bits -- from 0 to 1, from 1 to 0. Examples -- 5-bit 1's complement integers: Access the text alternative for slide images. © McGraw Hill 12  Disadvantages of Signed-Magnitude and 1's Complement In both representations, two different representations of zero Signed-magnitude: 00000 = 0 and 10000 = 0. 1's complement: 00000 = 0 and 11111 = 0. Operations are not simple. Think about how to add +2 and −3. Actions are different for two positive integers, two negative integers, one positive and one negative. A simpler scheme: 2's complement © McGraw Hill 13  2's Complement To simplify circuits, we want all operations on integers to use binary arithmetic, regardless of whether the integers are positive or negative. When we add +X to −X we want to get zero. Therefore, we use "normal" unsigned binary to represent +X. And we assign to −X the pattern of bits that will make X + (−X) = 0. NOTE: When we do this, we get a carry-out bit of 1, which is ignored. We only have 5 bits, so the carry-out bit is ignored and we still have 5 bits. Access the text alternative for slide images. © McGraw Hill 14  2's Complement Integers 4-bit 2's value 4-bit 2's value complement complement 0000 0 0001 1 1111 −1 0010 2 1110 −2 0011 3 1101 −3 0100 4 1100 −4 0101 5 1011 −5 0110 6 1010 −6 0111 7 1001 −7 1000 −8 With n bits, represent values from  2n  1 to  2n  1  1 NOTE: All positive number start with 0, all negative numbers start with 1. © McGraw Hill 15  Converting X to −X 1. Flip all the bits. (Same as 1's complement.) 2. Add +1 to the result. A shortcut method: Copy bits from right to left up to (and including) the first '1'. Then flip remaining bits to the left. Access the text alternative for slide images. © McGraw Hill 16  Converting Binary (2's C) to Decimal 1. If leading bit is one, take two’s complement to get a positive number. 2. Add powers of 2 that have “1” in the corresponding bit positions. 3. If original number was negative, add a minus sign. n 2n 0 1 1 2 X 01101000 two 2 4 3 8 26  25  23  64  32  8 4 16 5 32 104 ten 6 64 7 128 8 256 In the Examples use 8-bit 2’s complement numbers. 9 read512 following table, ‘2n’ as 2 to 10 1024 the power n. © McGraw Hill 17  More Examples X 00100111two n 2n 5 2 1 0 0 1 2  2  2  2  32  4  2  1 In1the 2 39 ten following 2 4 table, read ‘2n’ as32 to8 X 11100110 two the power n.4 16 5 32  X 00011010 6 64 24  23  21  16  8  2 7 128 8 256 26 ten 9 512 10 1024 X  26 ten Examples use 8-bit 2’s complement numbers. © McGraw Hill 18  Converting Decimal to Binary (2's C) 1 First Method: Division 1. Find magnitude of decimal number. (Always positive.) 2. Divide by two – remainder is least significant bit. 3. Keep dividing by two until answer is zero, writing remainders from right to left. 4. Append a zero as the MS bit; if original number was negative, flip bits and add +1. X 104 ten 104 / 2 52 r 0 bit 0 52 / 2 26 r 0 bit 1 26 / 2 13 r 0 bit 2 13 / 2 6 r1 bit 3 6 / 2 3 r 0 bit 4 3 / 2 1 r1 bit 5 X 01101000 two 1/ 2 0 r1 bit 6 © McGraw Hill 19  Converting Decimal to Binary (2's C) 2 n 2n Second Method: Subtract Powers of Two 0 1 1 2 1. Find magnitude of decimal number. 2 4 2. Subtract largest power of two less than or 3 8 equal to number. 4 16 5 32 3. Put a one in the corresponding bit position. 6 64 4. Keep subtracting until result is zero. 7 128 8 256 5. Append a zero as MS bit; if original was 9 512 negative, flip bits and add +1. 10 1024 X 104 ten 104  64 40 bit 6 40  32 8 bit 5 8  8 0 bit 3 X 01101000 two © McGraw Hill 20  Fractions: Fixed-Point Binary We use a "binary point" to separate integer bits from fractional bits, just like we use the "decimal point" for decimal numbers. Two's complement arithmetic still works the same. NOTE: In a computer, the binary point is implicit -- it is not explicitly represented. We just interpret the values appropriately. Access the text alternative for slide images. © McGraw Hill 21  Converting Decimal Fraction to Binary (2's C) 1. Multiply fraction by 2. 2. Record one's digit of result, then subtract it from the decimal number. 3. Continue until you get 0.0000... or you have used the desired number of bits (in which case you have approximated the desired value). X 0.421ten 0.421  2  0.842 bit  1  0 0.842  2  1.684 bit  2  1 0.684  2  1.368 bit  3  1 0.368  2  0.736 bit  4  0 until 0, or until no more bits... X 0.0110 two (if limited to 4 fractional bits) © McGraw Hill 22  Operation: Addition As discussed, 2's complement addition is just binary addition. Assume operands have the same number of bits. Ignore carry-out. Access the text alternative for slide images. © McGraw Hill 23  Operation: Subtraction You can, of course, do subtraction in base-2, but easier to negate the second operand and add. Again, assume same number of bits, and ignore carry-out. Access the text alternative for slide images. © McGraw Hill 24  Operation: Sign Extension To add/subtract, we need both numbers to have the same number of bits. What if one number is smaller? Padding on the left with zero does not work: Instead, replicate the most significant bit (the sign bit): Access the text alternative for slide images. © McGraw Hill 25  Overflow If the numbers are two big, then we cannot represent the sum using the same number of bits. For 2's complement, this can only happen if both numbers are positive or both numbers are negative. How to test for overflow: 1. Signs of both operands are the same, AND. 2. Sign of sum is different. Another test (easier to perform in hardware): Carry-in to most significant bit position is different than carry-out. Access the text alternative for slide images. © McGraw Hill 26  Logical Operations: AND, OR, NOT If we treat each bit as TRUE (1) or FALSE (0), then we define these logical operations, also known as Boolean operations, on a bit. A B A AND A B A OR B A NOT A B 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 View n-bit number as a collection of n logical values (bit vector) operation applied to each bit independently. © McGraw Hill 27  Examples of Logical Operations AND useful for clearing bits AND with zero = 0. AND with one = no change. OR useful for setting bits OR with zero = no change. OR with one = 1. NOT unary operation -- one argument flips every bit. Access the text alternative for slide images. © McGraw Hill 28  Logical Operation: Exclusive-OR (XOR) Another useful logical operation is the XOR. A B A XOR True is one of the bits is 1, but not both. B 0 0 0 0 1 1 1 0 1 1 1 0 XOR useful for selectively flipping bits XOR with zero = no change. XOR with one = flip. Access the text alternative for slide images. © McGraw Hill 29  DeMorgan's Laws 1 There's an interesting relationship between AND and OR. If we NOT two values (A and B), AND them, and then NOT the result, we get the same result as an OR operation. (In the figure below, an overbar denotes the NOT operation.) Here's the truth table to convince you: Copyright © McGraw Hill Education. Permission required or display A B A̅ B̅ A̅ AND B̅ A̅ AND B̅ 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 Access the text alternative for slide images. © McGraw Hill 30  DeMorgan's Laws 2 This means that any OR operation can be written as a combination of AND and NOT. This is interesting, but is it useful? We'll come back to this in later chapters... Also, convince yourself that a similar "trick" works to perform AND using only OR and NOT. Access the text alternative for slide images. © McGraw Hill 31  Very Large or Very Small Numbers: Floating-Point Large values: 6.023  10 23 -- requires 79 bits Small values: 6.626  10  34 -- requires >110 bits Range requires lots of bits, but only four decimal digits of precision. Use a different encoding for the equivalent of “scientific notation”: F × 2 E Need to represent F (fraction), E (exponent), and sign. IEEE 754 Floating-Point Standard (32-bits): N ( 1) S 1.fraction 2exponent  127 , 1 exponent 254 N ( 1) S 0.fraction 2 126 , exponent 0 Access the text alternative for slide images. © McGraw Hill 32  Floating-point Example Single-precision IEEE floating point number: Sign is 1 – number is negative. Exponent field is 01111110 = 126 (decimal). Fraction is 0.100000000000… = 0.5 (decimal). Value  1.5  2(126 127 )  1.5  2  1  0.75. Access the text alternative for slide images. © McGraw Hill 33  Converting from Decimal to Floating-Point Binary How do we represent  6 5 as a floating-point binary number? 8 Ignoring sign, represent as a binary fraction: 0110.101 Next, normalize the number, by moving the binary point to the right of the most significant bit: 0110.101  1.10101 22 Exponent field = 127 + 2 = 129 = 10000001 Fraction field = everything to the right of the binary point: 101010000.... Sign field is 1 (because the number is negative). Answer: 11000000110101000000000000000000 © McGraw Hill 34  Special Values Infinity If exponent field is 11111111, the number represents infinity. Can be positive or negative (per sign bit). Subnormal If exponent field is 00000000, the number is not normalized. This means that the implicit 1 is not present before the binary point. The exponent is −126. N ( 1) S  0. fraction 2 126. Extends the range into very small numbers. Example: 00000000000001000000000000000000. 0.00001two 2 126 2 131 © McGraw Hill 35  Representing Text: ASCII Code To represent other types of data, such as text, we devise various coding schemes. ASCII is a 7-bit code representing basic letters, digits, punctuation,... A portion of the ASCII table is shown below. 7b binary character 7b binary character 011 0000 0 100 0101 E 011 0001 1 110 0101 e 010 0001 ! 010 0000 space 010 0011 # 000 1010 linefeed See complete table in Appendix E. © McGraw Hill 36  Hexadecimal Notation: Binary Shorthand To avoid writing long (error-prone) binary values, group four bits together to make a base-16 digit. Use A to F to represent values 10 to 15. binary hexadecimal decimal binary hexadecimal decimal (base 2) (base 16) (base 10) (base 2) (base 16) (base 10) 0000 0 0 1000 8 8 0001 1 1 1001 9 9 0010 2 2 1010 A 10 0011 3 3 1011 B 11 0100 4 4 1100 C 12 0101 5 5 1101 D 13 0110 6 6 1110 E 15 0111 7 7 1111 F 15 Ex: Hex number 3D6E easier to communicate than binary 0011110101101110. © McGraw Hill 37  Converting from binary to hex Starting from the right, group every four bits together into a hex digit. Sign-extend as needed. This is not a new machine representation or data type, just a convenient way to write the number. Access the text alternative for slide images. © McGraw Hill 38  End of Main Content Because learning changes everything. ® www.mheducation.com © 2020 McGraw-Hill Education. All rights reserved. Authorized only for instructor use in the classroom. No reproduction or further distribution permitted without the prior written consent of McGraw-Hill Education.