CHAPTER 4

Operation on Data
Objectives
After studying this chapter, the student should be able
to:
 List the three categories of operations performed on data.
 Perform unary and binary logic operations on bit patterns.
 Distinguish between logic shift operations and arithmetic
shift operations.
 Perform logic shift operations on bit patterns.
 Understand some applications of logic and shift operations such
as setting, unsetting, and flipping bits.
 Perform arithmetic shift operation on integers when they are
stored in two’ complement format.
 Perform addition and subtraction operations on reals when they
are stored in sign and magnitude format.
4-1 LOGIC OPERATIONS
In Chapter 3 we discussed the fact that data inside a
computer is stored as patterns of bits. 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.
4.1.1 Logic operations at 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.
Boolean algebra, named in honor of George Boole, belongs
to a special field of mathematics called logic. Boolean
algebra and its application to building logic circuits in
computers are briefly discussed in Appendix E. In this
section, we show briefly four bit-level operations that are
used to manipulate bits: NOT, AND, OR, and XOR.

Boolean algebra and logic circuits are discussed in

Appendix E.
Figure 4.1 Logic operations at the bit level
NOT
The NOT operator is a unary operator: it takes only one
input. The output bit is the complement of the input.

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

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

OR
The OR operator is a binary operator: it takes two inputs.
The output bit is 0 if both inputs are 0s and the output is 1 in
other three cases.

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.

For x = 0 or 1 1 XOR x → NOTx 1 XOR x → 1

Example 4.1
In English we use the conjunction “or” sometimes to means an
inclusive-or, and sometimes to means an exclusive-or.

a. The sentence “I wish to have a car or a house” uses “or” in

the inclusive sense—I wish a car, or a house.

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.
 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
4.1.2 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 other three operators. Figure
4.2 shows these four operators with input and output
patterns.

Figure 4.2 Logic operators applied to bit patterns

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

We have a pattern of: 10100110.

Use a mask to unset (clear to 0) the five leftmost bits of a pattern.

Solution
We can use a mask is: 00000111. The result of applying the
mask is:

4.16
 Example 4.8

We have the pattern 10100110. Use a mask to set ( set to 1) the

five leftmost bits of a pattern.

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. They can move bits to the left
or to the right. We can divide shift operations into two
categories: logical shift operations and arithmetic
shift operations.

4.19
4.2.1 Logical shift operations
A logical shift operation is applied to a pattern that does not
represent a signed number. The reason is that these shift
operation may change the sign of the number that is defined
by the leftmost bit in the pattern. We distinguishes 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.2.2 Arithmetic shift operations
Arithmetic shift operations assume that the bit pattern is a
signed integer in two’s complement format. Arithmetic right
shift is used to divide an integer by two, while arithmetic left
shift is used to multiply an integer by two.

Figure 4.5 Arithmetic shift operations

4.25
Example 4.12

The bit pattern is an integer A= 10011001 = (-103)10.

Use an arithmetic right shift operation on the bit pattern
Solution
The solution is shown below. The leftmost bit is retained and also
copied to its right neighbor bit.

two’s complement format of A = 1 0011001

After shift: B = 1 1001100
Two’s complement of B (without sign) = 0110100. So B
= (-52)10
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
The pattern is an Original number was A= 1 1011001 = -39
Use an arithmetic left shift operation on the bit pattern.
Solution
After shift: B= 1 0110010
Result: based on the two’s complement of B without the sign:
1001110 = (78)10. So B = -78

The original number was −39 and the new number is −78. The
original number is multiplied by two.
4.27
 Example 4.14

Original number was 1: A = 0 1111111= (127)10

Have(its two’s complement format = 0 1111111 )
Use an arithmetic left shift operation on the original bit pattern
Solution
The solution is shown below. The leftmost bit is lost and a 0 is
inserted as the rightmost bit.

The original number was 1: A= 0 0000001

two’s complement of A = 0 1111111
After shifting: B = 1 1111110
two’s complement of B without sign = 1 0000010 = (2)10
the new number is - 2 in the two’s complement system.
This is the overflow problem!!!
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
Arithmetic operations involve adding, subtracting,
multiplying, and dividing. We can apply these
operations to integers and floating-point numbers.

4.30
4.3.1 Arithmetic operations on integers
All arithmetic operations such as addition, subtraction,
multiplication, and division can be applied to integers.
Although multiplication (division) of integers can be
implemented using repeated addition (subtraction), the
procedure is not efficient. There are more efficient
procedures for multiplication and division, such as Booth
procedures, but these are beyond the scope of this book. For
this reason, we only discuss addition and subtraction of
integers here.

4.31
 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.32
 We should remember that we add integers column by
column. The following table shows the sum and carry (C).

4.33
Figure 4.6 Addition and subtraction of integers in two’s complement
 Example 4.16

Two integers A and B . 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.35
 Example 4.17

Two integers A and B. Show how B is subtracted from A.

A = (00011000)2 B = (00010001)2

Solution
A- B = 24 17 = 7
A = 00011000
two’s complement of B = 11101111

= (+7)10
4.36
 Example 4.18

Two integers A and B. Show how B is subtracted from A.

A = (00011000)2 = (24)10
B = (11101111)2
Two’s complement of B = 00010001 = 17 = -B
so B = (-17)10 and A – B = A+(-B) = 24 + 17 = 41
Solution
The operation is subtracting:
A- B = (24)  () = 24 + two complement of B
= (24) + (17) = 41

4.37
 Example 4.19

Two integers A and B, get (-A)+(-B)= ?

A = (00100011)2 B = (00010100)2
Solution
A=35, B=20
(- A) = 11011101
(- B) = 11101100
(-A)+(-B) =1 11001001 = 11001001 in an 8-bit
system.
Get two’s complement without the sign = 0110111 = 55 so the
result with the sign is -55.
Have: (−35) + (-20) = (−55).

4.38
Example 4.20

Two integers A and B . Show how B is added to A.

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

Without any restriction, the result is: 127 + 3 = 130 = (10000010)2

But an error occurred, due to overflow, the leftmost bit is discarded.
It is now the sign. The result (+130) is not in the range −128 to +127.
4.39We have the answer is −126 = -(1111110) = two’s complement of 2.
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.
Sign-and-Magnitude integers
Addition and subtraction
for integers in sign-and-
magnitude representation
looks very complex. We
have 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 the
next figure.
4.41
 Example 4.22
Two integers A and B are stored in sign-and-magnitude format.
Show how B is added to A.

Solution A = (0 0010001)2 B = (1 0010110)2

The operation is adding:
S = AS XOR BS = 1; (Sign)
RM = AM + (BM +1) = 0010001+1101010 =1111011 (Magnitude)
we take the two’s complement of RM =0000101
The sign of R is the sign of B.
So we have: (+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
4.3.2 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 involves
multiplication of two integers in sign-and-magnitude
representation. Division of two reals involves 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 stored in
floating-point numbers is
reduced to addition and
subtraction of two
integers stored in sign-
and-magnitude
(combination of sign and
mantissa) after the
alignment of decimal
points. Next figure
shows a simplified
version of the procedure
(there are some special
cases that we have
ignored).
4.45
 Example 4.23
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.46
 We have had:

We de-normalize the numbers by adding the hidden 1s to the

mantissa and incrementing the exponent until the exponents
are the same.

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.47
 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.48
 Example 4.24
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.49
 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.50
 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.51