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