Thu, 12 Sep 2013, 03:32

Three students, two after class, one later in my office, all had the
same question about the MASK in my bit vector example.  So, I thought
an email message to you would be a good idea.

Recall in class we used a bit vector

P1  P2  P3  P4  P5  P6

to represent which of six printers are available to send a file to
for printing.

There are 2^6 possible printer situations, and each can be described by one
of the 2^6 possible bit vectors.  Each Pi represents a printer that is either
idle or busy.  If Pi=0, the printer is busy.  If Pi=1, the printer is free.

If the bit vector is 010001, printers 2 and 6 are free (Pi=1) and printers
1,3,4, and 5 are busy (Pi=0).

Recall we decided to send the file to Printer 2.  After sending the file
to Printer 2, we want to indicate that Printer 2 is also now busy.  We do
that by changing P2 from a 1 to a 0.  I suggested ANDing 010001 with the
MASK 101111.  And, sure enough it works!

Three students pointed out later that it will also work for the MASK 000001,
that is, we will get the same result if we use the mask 000001.

That is true, the mask 000001 will work for the bit vector 010001.  But that
mask will not work for the bit vector 110001, for example.  Do you see why
it won't work for bit vector 110001?

I suppose we could pick our mask depending on the bit vector, but that would
be cumbersome.  Much better if we can have ONE mask that will work on all 2^k
bit vectors.  That is, one mask that will change P2 from 1 to 0 and leave all
the other bits alone, regardless of the bit vector.

How do we accomplish that?  The MASK is

M1  M2  M3  M4  M5  M6

We want the mask bits to leave alone all the Pi bits EXCEPT P2, the one we
want to make 0.

ANDing the bit vector with the MASK independently ANDs each Pi with its
corresponding Mi.  If M2=0, the result of ANDing P2 and 0 is 0.  If all
the other Mi=1, we have Pi AND 1 for all the other bits.  The result is 1
if Pi=1, and 0 if Pi=0.  The ONE MASK 101111 works for all bit vectors.

Now the Flip side:
=================

Now the flip side: Making P5 go from 0 to 1 to reflect the fact that printer 5
is now done printing and is now available for another job.  If we OR the bit
vector with the MASK, we need a MASK that keeps all Pi except P5 the same and
makes P5=1.  How do we do this?  That is, what ONE mask will work on all bit
vectors.  We use the OR function.  Pi OR 0 is Pi.  P5 OR 1 is 1.

Therefore the MASK for setting P5 and leaving all other Pi unchanged is
000010.  And, this one mask works for all situations, that is, for all 2^6
bit vectors.

Hope this helps.

See you in class on Monday.

Yale Patt