4

Operations
On Data
4.1
Foundations of Computer Science Cengage Learning
 Outline

 Three categories of operations performed on data.

 Unary and binary logic operations on bit patterns.
 Logic shift operations / arithmetic shift operations.
 Addition and subtraction on integers in two’s complement
format.
❑ Addition and subtraction on integers in sign-and-magnitude
format.
❑ Addition and subtraction operations in floating-point
format.

4.2
 4-1 LOGIC OPERATIONS

•Logic operations : operations that apply the same

basic operation on individual bits of a pattern, or on two
corresponding bits in two patterns.

•Logic operations: bit level / 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.

4.3
Logic operations at bit level
•A bit: 0 or 1
•0: false ; 1: true
•Boolean algebra: four bit-level operations
•NOT, AND, OR, and XOR.

i
Boolean algebra and logic circuits are discussed in
Appendix E.
4.4
 Figure 4.1 Logic operations at the bit level
4.5
NOT
A unary operator: it takes only one input.
The output bit is the complement of the input.

AND
•Binary operator: it takes two inputs.
•The output bit is 1 if both inputs are 1s
•The output is 0 in the other three cases.

i
For x = 0 or 1 x AND 0 → 0 0 AND x → 0

4.6
 OR
•Binary operator
•The output bit is 0 if both inputs are 0s
•The output is 1 in other three cases.
i
For x = 0 or 1 x OR 1 → 1 1 OR x → 1

XOR
•The XOR operator is a binary operator like the OR operator,
with only one difference: the output is 0 if both inputs are 1s.
i
For x = 0 or 1
1 XOR x → NOT x x XOR 1 → NOT x
4.7
 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.

4.8
 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.

4.9
Logic operations at pattern level
•The same four operators (NOT, AND, OR, and XOR) 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.

Figure 4.2 Logic operators applied to bit patterns

4.10
 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.

4.11
 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.

4.12
 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.

4.13
 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).

4.14
 Applications

The four logic operations can be used to modify a bit pattern.

 Complementing (NOT)

 Unsetting (AND)

 Setting (OR)

 Flipping (XOR)

4.15
 Example 4.7
Use a mask to unset (clear) the five leftmost bits of a pattern.
Test the mask with the pattern 10100110.

Solution
The mask is 00000111. The result of applying the mask is:

4.16
 Example 4.8
Use a mask to set the five leftmost bits of a pattern. Test the
mask with the pattern 10100110.

Solution
The mask is 11111000. The result of applying the mask is:

4.17
 Example 4.9
Use a mask to flip the five leftmost bits of a pattern. Test the
mask with the pattern 10100110.

Solution
The mask is 11111000. The result of applying the mask is:

4.18
 4-2 SHIFT OPERATIONS

•Shift operations : move the bits in a pattern, changing

the positions of the bits.

•To the left or to the right.

•logical shift operations / arithmetic shift operations.

4.19
Logical shift operations
•A logical shift operation is applied to a pattern that does not
represent a signed number.

•We distinguish two types of logical shift operations, as

described below:

 Logical shift

 Logical circular shift (Rotate)

4.20
 Figure 4.3 Logical shift operations

4.21
 Example 4.10

Use a logical left shift operation on the bit pattern 10011000.

Solution
The solution is shown below. The leftmost bit is lost and a 0 is
inserted as the rightmost bit.

Discarded

Added

4.22
 Figure 4.4 Circular shift operations

4.23
 Example 4.11

Use a circular left shift operation on the bit pattern 10011000.

Solution
The solution is shown below. The leftmost bit is circulated and
becomes the rightmost bit.

4.24
Arithmetic shift operations
•Arithmetic shift operations assume that the bit pattern is a
signed integer in two’s complement format.

•Right shift : divide an integer by two

•Left shift : multiply an integer by two

Figure 4.5 Arithmetic shift operations

4.25
 Example 4.12
Use an arithmetic right shift operation on the bit pattern
10011001. The pattern is an integer in two’s complement format.
Solution
The solution is shown below. The leftmost bit is retained and also
copied to its right neighbor bit.

The original number was −103 and the new number is −52,
which is the result of dividing −103 by 2 truncated to the smaller
integer.

4.26
 Example 4.13
Use an arithmetic left shift operation on the bit pattern 11011001.
The pattern is an integer in two’s complement format.
Solution
The solution is shown below. The leftmost bit is lost and a 0 is
inserted as the rightmost bit.

The original number was −39 and the new number is −78. The
original number is multiplied by two. The operation is valid
because no underflow occurred.

4.27
 Example 4.14
Use an arithmetic left shift operation on the bit pattern 01111111.
The pattern is an integer in two’s complement format.
Solution
The solution is shown below. The leftmost bit is lost and a 0 is
inserted as the rightmost bit.

The original number was 127 and the new number is −2. Here the
result is not valid because an overflow has occurred. The
expected answer 127 × 2 = 254 cannot be represented by an 8-bit
pattern.
4.28
 Example 4.15
Combining logic operations and logical shift operations give us
some tools for manipulating bit patterns. Assume that we have a
pattern and we need to use the third bit (from the right) of this
pattern in a decision-making process. We want to know if this
particular bit is 0 or 1. The following shows how we can find out.

We can then test the result: if it is an unsigned integer 1, the

target bit was 1, whereas if the result is an unsigned integer 0, the
target bit was 0.
4.29
 4-3 ARITHMETIC OPERATIONS

•adding, subtracting, multiplying and dividing

•to integers and floating-point numbers.

4.30
 Two’s complement integers
When the subtraction operation is encountered, the computer
simply changes it to an addition operation, but makes two’s
complement of the second number. In other words:

A − B ↔ A + (B + 1)

Where B is the one’s complement of B and

(B + 1) means the two’s complement of B

4.31
 We should remember that we add integers column by
column. The following table shows the sum and carry (C).

4.32
 Figure 4.6 Addition and subtraction of integers in two’s complement format
4.33
 Example 4.16
Two integers A and B are stored in two’s complement format.
Show how B is added to A.
A = (00010001)2 B = (00010110)2

Solution
The operation is adding. A is added to B and the result is stored
in R. (+17) + (+22) = (+39).

4.34
 Example 4.17
Two integers A and B are stored in two’s complement format.
Show how B is added to A.
A = (00011000)2 B = (11101111)2

Solution
The operation is adding. A is added to B and the result is stored
in R. (+24) + (17) = (+7).

4.35
 Example 4.18
Two integers A and B are stored in two’s complement format.
Show how B is subtracted from A.
A = (00011000)2 B = (11101111)2

Solution
The operation is subtracting. A is added to (B + 1) and the result
is stored in R. (+24)  (17) = (+41).

4.36
 Example 4.19
Two integers A and B are stored in two’s complement format.
Show how B is subtracted from A.
A = (11011101)2 B = (00010100)2

Solution
The operation is subtracting. A is added to (B + 1) and the result
is stored in R. (−35) − (+20) = (−55).

4.37
 Example 4.20
Two integers A and B are stored in two’s complement format.
Show how B is added to A.

A = (01111111)2 B = (00000011)2
Solution
The operation is adding. A is added to B and the result is stored
in R.

We expect the result to be 127 + 3 = 130, but the answer is −126.

The error is due to overflow, because the expected answer (+130)
is not in the range −128 to +127.
4.38
 i
When we do arithmetic operations on numbers in a
computer, we should remember that each number
and the result should be in the range defined by
the bit allocation.

4.39
 sign-and-magnitude integers
•Addition and subtraction for integers in sign-and-magnitude
representation looks very complex.

•Four different combination of signs (two signs, each of two

values) for addition and

•Four different conditions for subtraction.

•This means that we need to consider eight different

situations.

•However, if we first check the signs, we can reduce these

cases, as shown in Figure 4.7.

4.40
 Figure 4.7 Addition and subtraction of integers in sign-and-magnitude format
4.41
 Example 4.22
Two integers A and B are stored in sign-and-magnitude format.
Show how B is added to A.

A = (0 0010001)2 B = (1 0010110)2
Solution
The operation is adding: the sign of B is not changed. S = AS
XOR BS = 1; RM = AM + (BM +1). Since there is no overflow, we
need to take the two’s complement of RM. The sign of R is the
sign of B. (+17) + ( −22) = (−5).

4.42
 Example 4.23
Two integers A and B are stored in sign-and-magnitude format.
Show how B is subtracted from A.

A = (1 1010001)2 B = (1 0010110)2
Solution
The operation is subtracting: SB = SB. S = AS XOR BS = 1, RM =
AM + (BM +1). Since there is an overflow, the value of RM is final.
The sign of R is the sign of A. (−81) − (−22) = (−59).

4.43
Arithmetic operations on reals
•All arithmetic operations such as addition, subtraction,
multiplication and division can be applied to reals stored in
floating-point format.

•Multiplication of two reals: multiplication of two integers in

sign-and-magnitude representation.
•Division of two reals : division of two integers in sign-and-
magnitude representations.
•Since we did not discuss the multiplication or division of
integers in sign-and magnitude representation, we will not
discuss the multiplication and division of reals, and only
show addition and subtractions for reals.

4.44
 Addition and subtraction of reals
•Addition and subtraction of real numbers in floating-point
numbers :
•the alignment of decimal points.
•addition and subtraction of two integers stored in sign-
and-magnitude (combination of sign and mantissa)
•Figure 4.8 shows a simplified version of the procedure
(there are some special cases that we have ignored).

4.45
 Figure 4.8 Addition and subtraction of reals in floating-point format
4.46
 Example 4.24
Show how the computer finds the result of (+5.75) + (+161.875)
= (+167.625).
Solution
As we saw in Chapter 3, these two numbers are stored in
floating-point format, as shown below, but we need to remember
that each number has a hidden 1 (which is not stored, but
assumed).

4.47
 Example 4.24 (Continued)
•We de-normalize the numbers by adding the hidden 1s to the
mantissa and incrementing the exponent.
•Now both de-normalized mantissas are 24 bits and include the
hidden 1s.
•They should be stored in a location that can hold all 24 bits.
Each exponent is incremented.

4.48
 Example 4.24 (Continued)
Now we do sign-and-magnitude addition, treating the sign and
the mantissa of each number as one integer stored in sign-and-
magnitude representation.

There is no overflow in the mantissa, so we normalize.

The mantissa is only 23 bits, no rounding is needed. E =

(10000110)2 = 134 M = 0100111101. In other words, the result is
(1.0100111101)2 × 2134−127 = (10100111.101)2 = 167.625.

4.49
 Example 4.25
Show how the computer finds the result of (+5.75) +
(−7.0234375) = − 1.2734375.
Solution
These two numbers can be stored in floating-point format, as
shown below:

De-normalization results in:

4.50
 Example 4.25 (Continued)
Alignment is not needed (both exponents are the same), so we
apply addition operation on the combinations of sign and
mantissa. The result is shown below, in which the sign of the
result is negative:

Now we need to normalize. We decrement the exponent three

times and shift the de-normalized mantissa to the left three
positions:

4.51
 Example 4.25 (Continued)
The mantissa is now 24 bits, so we round it to 23 bits.

The result is R = − 2127−127 × 1.0100011 = − 1.2734375, as

expected.

4.52