3_Operations on Data.pdf

Operations on Data Instructor: Tsung-Che Chiang [email protected] Department of Computer Science and Information Engineering N...

Operations on Data Instructor: Tsung-Che Chiang [email protected] Department of Computer Science and Information Engineering National Taiwan Normal University Introduction to Computer Science, Fall, 2010 Outline Logic operations Boolean Algebra Shift operations Arithmetic operations Integers Reals Summary 2 Introduction to Computer Science, Fall, 2010 1  Logic Operations Logic operations refer to those operations that apply the same basic operation on individual bits of a pattern, or on two corresponding bits in two patterns. This means that we can define logic operations at the bit level and at the pattern level. A logic operation at the pattern level is n logic operations, of the same type, at the bit level where n is the number of bits in the pattern 3 Introduction to Computer Science, Fall, 2010 Logic Operations: Bit level A bit can take one of the two values: 0 or 1. If we interpret 0 as the value false and 1 as the value true, we can apply the operations defined in Boolean algebra to manipulate bits. In this section, we show briefly four bit-level operations that are used to manipulate bits: NOT, AND, OR, and XOR. 4 Introduction to Computer Science, Fall, 2010 2  Logic Operations: Bit level NOT AND x AND 0 → 0 0 AND x → 0 B. Forouzan and F. Mosharraf, Foundations of Computer Science, 2nd ed., 2008. 5 Introduction to Computer Science, Fall, 2010 Logic Operations: Bit level OR x OR 1 → 1 1 OR x → 1 XOR x XOR 1 → NOT x 1 XOR x → NOT x B. Forouzan and F. Mosharraf, Foundations of Computer Science, 2nd ed., 2008. 6 Introduction to Computer Science, Fall, 2010 3  Logic Operations: Bit level Example 4.1 In English we use the conjunction “ or”sometimes to mean an inclusive-or, and sometimes to means an exclusive-or. a. The sentence “ I would like to have a car or a house”uses “or”in the inclusive sense—I would like to have a car, a house or both. b. The sentence “ Today is either Monday or Tuesday”uses “or”in the exclusive sense—today is either Monday or Tuesday, but it cannot be both. 7 Introduction to Computer Science, Fall, 2010 Logic Operations: Bit level Example 4.2 The XOR operator is not actually a new operator. We can always simulate it using the other three operators. The following two expressions are equivalent x XOR y  [x AND (NOT y)] OR [(NOT x) AND y] The equivalence can be proved if we make the truth table for both. 8 Introduction to Computer Science, Fall, 2010 4  Logic Operations: Pattern level The same four operators can be applied to an n-bit pattern. The effect is the same as applying each operator to each individual bit for NOT and to each corresponding pair of bits for the other three operators. B. Forouzan and F. Mosharraf, Foundations of Computer Science, 2nd ed., 2008. 9 Introduction to Computer Science, Fall, 2010 Logic Operations: Pattern level Example 4.3 Use the NOT operator on the bit pattern 10011000. Solution The solution is shown below. Note that the NOT operator changes every 0 to 1 and every 1 to 0. B. Forouzan and F. Mosharraf, Foundations of Computer Science, 2nd ed., 2008. 10 Introduction to Computer Science, Fall, 2010 5  Logic Operations: Pattern level Example 4.4 Use the AND operator on the bit patterns 10011000 and 00101010. Solution The solution is shown below. Note that only one bit in the output is 1, where both corresponding inputs are 1s. B. Forouzan and F. Mosharraf, Foundations of Computer Science, 2nd ed., 2008. 11 Introduction to Computer Science, Fall, 2010 Logic Operations: Pattern level Example 4.5 Use the OR operator on the bit patterns 10011001 and 00101110. Solution The solution is shown below. Note that only one bit in the output is 0, where both corresponding inputs are 0s. B. Forouzan and F. Mosharraf, Foundations of Computer Science, 2nd ed., 2008. 12 Introduction to Computer Science, Fall, 2010 6  Logic Operations: Pattern level Example 4.6 Use the XOR operator on the bit patterns 10011001 and 00101110. Solution The solution is shown below. Compare the output in this example with the one in Example 4.5. The only difference is that when the two inputs are 1s, the result is 0 (the effect of exclusion). B. Forouzan and F. Mosharraf, Foundations of Computer Science, 2nd ed., 2008. 13 Introduction to Computer Science, Fall, 2010 Logic Operations: Pattern level Bitwise logic operations in C/C++ program int main() { int a = 5, b = 11; printf("a = %d, b = %d\n" "a = %#010X, b = %#010X\n" "NOT: ~a = %#010X\n" "AND: a & b = %#010X\n" " OR: a | b = %#010X\n" "XOR: a ^ b = %#010X\n" , a, b, a, b , ~a , a & b a = 5, b = 11 , a | b a = 0X00000005, b = 0X0000000B , a ^ b); NOT: ~a = 0XFFFFFFFA AND: a & b = 0X00000001 OR: a | b = 0X0000000F return 0; XOR: a ^ b = 0X0000000E } 14 Introduction to Computer Science, Fall, 2010 7  Logic Operations: Pattern level Bitwise logic operations in C/C++ program #include a = 01100101, b = 11100010 #include NOT: ~a = 10011010 #include AND: a & b = 01100000 using namespace std; OR: a | b = 11100111 XOR: a ^ b = 10000111 int main() { bitset a(string("01100101")), b(string("11100010")); cout