LESSON 01 – BITWISE OPERATIONS

 

 

LESSON NOTE

BEFORE - SINGLE BIT OPERATIONS


So far, our Boolean operations look like this:

 

            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…

 

EXAMPLE

 

Let’s do 1010 1011 AND 1111 0010.

 

The best way to see how this is done is to place the two bytes one above the other.

 

                 1010 1011

AND         1111 0010

 

We now apply the AND to the first digits only.  Both are 1s so the result will be a 1.

 

                 1010 1011

AND         1111 0010

                                    --------------

                                    1

 

We now consider second digits.  We have to do a 0 AND 1 which gives us a 0.

 

                 1010 1011

AND         1111 0010

                                    --------------

                                    10

 

We continue like this bit by bit until we have done all bits.

 

                 1010 1011

AND         1111 0010

                                    --------------

                                    1010 0010

 

 

BITWISE OR

 

The Bitwise OR operation works the same way as the Bitwise AND.

 

EXAMPLE

 

Let’s do 1010 1100 OR 0100 0110.

 

Again, it is easiest to line up both bytes one on top of the other.  We simply do bit by bit OR operations for each column.

 

                 1010 1100

OR           0100 0110

                                    --------------

                                    1110 1110

 

 

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.

 

EXAMPLE

 

Let’s do NOT 0110 1011.

 

We simply write the operator and the one byte.  Then, we NOT each digit one at a time.

 

NOT         0110 1011

                                    --------------

                                    1001 0100

 

 

OTHER BITWISE OPERATIONS

 

All Bitwise operations work the same way.  Here is one final example.

 

EXAMPLE

 

Let’s do 1101 0010 XOR 0011 0110.

 

Here is the solution:

 

                 1101 0010

XOR         0011 0110

                                    --------------

                                    1110 0100

 


CIRCUIT DIAGRAMS

 

Circuits that reflect the bitwise operations are not much more complex than the ones that we have seen in the past with the exception that there is a great deal of repetition. 

 

When we work with bytes in circuits, each byte is given a letter.  Inputs are often A, B, C, … and the common output letter is Q.

 

To specify specific bits in a byte, we place a subscript number beside the letter.  For example, the bit A1 is the leftmost bit in A and B8 is the rightmost bit in B.

 

In general, the bits in byte A are written as A1, A2, A3, A4, A5, A6, A7, A8.

In general, the bits in byte B are written as B1, B2, B3, B4, B5, B6, B7, B8.

In general, the bits in byte Q are written as Q1, Q2, Q3, Q4, Q5, Q6, Q7, Q8.

 

If A is a byte and B is another byte, we can draw the circuit diagram of A AND B by doing the following:

 

BIT SHIFTS`

 

Another common operation done on bits is the bit shift.  It simply involves moving all bits to the left or to the right by a set amount of spots.

 

LOGICAL BIT SHIFTS

 

When we apply logical bit shifts, we shift all bits in a certain direction and the new bits are given a value of zero.  The symbol that is often used to specify a left bit shift is << and a right bit shift if >>.

 

The line

 

42 >> 2

 

Usually means take the binary content of 42 and shift all bits to the right by 2 spots.

 

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
Again, we will assume that we are working with 1 byte of data that only stores positive numbers.  So, in binary, the number 219 is 1101 1011.

 

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.