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’s complement format.

 Perform addition and subtraction operations on integers.

4.1 LOGIC OPERATIONS
• Data are stored as bit patterns in computers.
• What is a logic operation?
 An operation applies on individual bits of a
pattern, or on two corresponding bits in two
patterns.
 In other words, we can define logic operations at
the bit level and at the pattern level.
LOGIC OPERATIONS
• A logic operation at the pattern level is
comprised of n logic operations, of the same
type, at the bit level where n is the number
of bits in the pattern.

Logic Operation
& (AND)
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 discussed in Appendix E.
Figure 4.1: Four bit-level operations NOT, AND, OR,
and XOR are used to manipulate bits.
Logic symbol

Truth table

Exclusive OR
NOT
The NOT operator is a unary operator: it takes
only one input. The output bit is the complement
of the input.
For x = 0 NOT x → 1
x = 1 NOT x → 0

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 → NOT x
x XOR 1 → NOT x
Other bit-level logic operations
 x NAND y = NOT (x AND y)
 x AND y = NOT (x NAND y)

x y x AND y x NAND y
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0

NOT(x AND y)

NOT(x NAND y)
Other bit-level logic operations
 x NOR y = NOT (x OR y)
 x OR y = NOT (x NOR y)

x y x OR y x NOR y
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0

NOT(x OR y)

NOT(x NOR y)
Other bit-level logic operations
 x XNOR y = NOT (x XOR y)
 x XOR y = NOT (x XNOR y)

x y x XOR y x XNOR y
0 0 0 1
0 1 1 0
1 0 1 0
1 1 0 1

NOT(x XOR y)

NOT(x XNOR y)
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, 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.
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.
x y x XOR y (NOT x) AND y x AND (NOT
y)

0 0 0 0 0
0 1 1 1 0
1 0 1 0 1
1 1 0 0 0
 Exercises

1. y = NOT(a NAND b). What is the truth

table for y?
a b y
0 0
0 1
1 0
1 1

2. y = (a NOR b) XOR (a AND b). What is

the truth table for y?
4.14
 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 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.

Take ones’ complement of a number.

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.

Applying AND to each pair of the bits at the

same position.
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.
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).
Applications

The four logic operations can be used to modify a bit

pattern.
 Complementing (NOT)
 Unsetting (AND) : setting some bits into zero’s using
a mask pattern
 Setting (OR) : setting some bits into one’s using a
mask pattern
 Flipping (XOR) : setting some bits into their
complement values
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:
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:
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:

Can we just perform NOT operation on these five

bits?
 Exercise

1. A mask 224 is used to derive the

network id with address 248
represented by 8 binary bits with AND
operation. Derive the network id for
this address.

4.24
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 classify shift operations into two categories:
logical shift operations and arithmetic shift
operations.
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 operations may
change the sign of the number that is defined by
the leftmost bit in the pattern.
• We distinguish two types of logical shift
operations, as described below:

 Logical shift

 Logical circular shift (Rotate)

Figure 4.3: Logical shift operations
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
Figure 4.4: Circular shift operations
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

0
Lost c. Yet another Arithmetic left shift
Example 4.12
Use an arithmetic right shift operation on the bit pattern
10011001. The pattern is an integer in two’s complement
format. [-128~127]

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

Why does it work?

2’ complement at negative cases
𝒌− 𝟏 𝒌 −𝟐
−𝟐 +( 𝒔 𝒌 −𝟐 ∗ 𝟐 +…)
Right shift 1 bit
/2 divided by 2
=
=

keep Shift right 1 bit

𝒌− 𝟏
−𝟐
𝒌 −𝟐
𝟐
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.
This bit must be one without underflow

at negative cases when multiply by two.

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.
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.
This bit must be 0 without overflow at

positive cases when multiply by two.

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

1. Check if overflow or underflow has

occurred when 8-bit is used with shift
operation. If yes, why? If not, what is
the result?
(a) 124*2 (b) -110*2
(c) -116/2 (d) 116/2

4.36
Example 4.15 Combining shift and logic operations

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.
Example 4.15 Combining shift and logic operations

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.

Do we have another way?

4.3 ARITHMETIC OPERATIONS
Arithmetic operations involve adding, subtracting,
multiplying, and dividing. We can apply these
operations to integers and floating-point numbers.
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.
Addition and subtraction for 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 ones’ complement of B and
(B + 1) means the two’s complement of B
Addition of two integers

Carry out generated at the ith bit position

becomes the carry in at the (i+1)th position.

carry

sum

Here, c0 =0 for A+B.

ci, carry in & carry out
Put together A-B = A + +1

carry

sum

Here, c0 =1 for A-B.

ci, carry in & carry out
Adding Bits: Half Adder and Full Adder
Half adder : a+b  zero 1s, one 1s, two
1s.
Full adder : a+b+c  zero 1s, one 1s, two 1s,
three 1s.
So we have to use two bits to represent the result of
adding two bits. One bit denotes sum and the other
bit denotes carry.

Table 4.1 shows the sum and carry (C) of adding

three bits a, b, c in the same column.
Figure 4.6: Addition and subtraction in two’s complement
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).
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).

carry out at
MSB position
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).
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).
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.
If carries at these two positions are different, there is an
overflow.

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.
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.
• Refer to the materials in Appendix I.
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.
• Refer to the related materials in Appendix J.
Summary
 Logic operations at bit & pattern levels
 Logical shift & arithmetic shift operations
 Arithmetic operations on integers