LESSON
01 – BITWISE OPERATIONS LESSON NOTE BEFORE - SINGLE BIT
OPERATIONS
0 XOR 1 gives 1 0 AND 1 gives 0 NOT(1)
gives 0 NOW – MULTI-BIT
OPERATIONS Inside
computer systems, we often have to apply Boolean operations between two bytes
of data giving us a byte of data as output.
Here’s an example: 0010 1101 AND 0110 1001 gives 0010
1001 In this
lesson, we’ll look at how we do operations that have multiple bits as inputs
and outputs. SIZE OF THE DATA The size of
the data may vary inside computer systems.
For example, 64-bit computer systems usually work with two 64-bit input
values which gives off a 64-bit output value. That would
look like this: 0110 1111
1111 0101 1101 1001 1101 1000 0110 1111 1111 0101 1101 1001 1101 1000 OR 1010 0111 1001
0110 1000 0001 0101 1001 1110 0001 1011 0001 1001 0001 0001 0101 gives 1110 1111
1111 0111 1101 1001 1101 1001 1110 1111 1111 0101 1101 1001 1101 1101 That is
pretty painful to work with! L Instead, we
will use a byte (8 bits) for simplicity as well as for time efficiency. Also, we want to keep our sanity! J BITWISE OPERATIONS To do any
logic operation between two bytes, we simply apply that operation bit by bit. We call such operations bitwise operations. BITWISE AND To do a
bitwise AND on two bytes, we simply do the AND eight different times. The first AND is done between the first
bits, then the next is done between the second bits, the next is done between
the third bits, and so on…
BITWISE OR The Bitwise
OR operation works the same way as the Bitwise AND.
BITWISE NOT The Bitwise
NOT applies only to one byte. The NOT
is applied to each bit individually essentially flipping the byte’s zeros and
ones.
OTHER BITWISE
OPERATIONS All Bitwise
operations work the same way. Here is
one final example.
|
EXAMPLE 1 (IN BINARY) Do the
following shift: 1011 0011 < 2 STEP 1 We simply
move each bit over to the left by two.
The two new bits shifted in gets values of zero. And we lose the two leftmost bits in the
process. 1100 1100 |
EXAMPLE 2 (IN DECIMAL) Do the
following logical shift: 42 >> 1 and show all steps. STEP 1 We will assume
that we are working with 1 byte of data that can store only positive
numbers. So, in binary, 42 is 0010 1010. STEP 2 We now
shift right by 1. The new value,
known as the shifted-in value, is always zero. The bit that is removed is called the
shifted-out bit. 0001 0101 STEP 3 The value
of 0001 0101 in base-10 is 1 + 4 + 16 = 21. CONCLUSION 42
>> 1 gives 21. |
EXAMPLE 3 (IN DECIMAL) Do the
following logical shift: 219 << 2 and show all steps. STEP 1 STEP 2 We now
shift left by 2. The shifted-in
values are both zero. The
shifted-out values are both 1s. 0110 1100 STEP 3 The value
of 0110 1100 in base-10 is 64 + 32 + 8 + 4 = 108. CONCLUSION 219 <<
2 gives 108. |
ARITHMETIC SHIFTS
The logical
shifts that we have seen above deal with positive numbers. When dealing with numbers that are
potentially negative, we usually want to use an arithmetic shift when
shifting right. Note that shifting
left is identical for arithmetic and logical shifts.
Arithmetic
shifts to the right, instead of shifting in a zero, shift in the same value
that was already present on the far left.
This has the impact of maintaining the sign of the number.
EXAMPLE 1 (IN DECIMAL) Do the
following arithmetic shift: -116 >> 2. Assume the computer system is storing the
number in 1 byte of data and uses 2’s complement to work with negative
numbers. STEP 1 We first
find 116 in binary. 0111 0100 STEP 2 We take
the 1’s complement of the above byte. 1000 1011 STEP 3 We take
the 2’s complement of the above byte. 1000 1100 STEP 4 Now we
can apply the right shift by 1. The value
we shift in on the left side is the same value that was present on the left
side before – in this case, a 1. 1100 0110 STEP 5 The
problem asked us to shift by 2. Se
we again shift right and once again shift in a 1. 1110 0011 STEP 6 To
convert back to decimal, we much remove 1 to return to 1’s complement. 1110 0010 STEP 7 We now
undo 1’s complement. 0001 1101 STEP 8 We can
now convert to decimal. 16 + 8 +
4 + 1 =29 The
number is negative, so the answer is -29. |
CIRCULAR SHIFTS
A circular
shift is simply a shift to the left or the right but with the bits shifted
out at one end being brought back in on the other end.
EXAMPLE (IN BINARY) Do a
circular shift to the right by 2 on the following byte: 0010 0101 SOLUTION The two
rightmost bits gets brought to the left. 0100 1001 |
USES OF SHIFTS
Shifting
right by 1 has the effect of dividing the number by 2. Shifting right by n has the effect of dividing
by 2n.
Shifting
left by 1 has the effect of multiplying by 2.
Shifting left by n has the effect of multiplying by 2n. Of course, if the shifting causes overflow
(bits of value 1 being shifted out), then one does not get the result of the
multiplication.
Circular
shifting is not used as often. One
situation where this shifting is used is in circuits with sequences of
lights. Imagine a straight line of 5 LEDs. Initially, the rightmost LED is on and all
others are off. Then, the 2nd
LED is on and the rest are off. Then,
the 3rd. Then the 4th
and then the 5th. And then
the process restarts with the 1st LED being the lone one on.