bitvectors

[VictorH]

Looking for help with understanding:

"A mask can be used to access an individual bit of a byte. Suppose, for example, that we want to access the third bit from the right of byte x. Calculate the value
y = 4 & x
= 00000100 & x
Note that y can have only two values:
00000100 = 4, or
00000000 = 0.
The test (y != 0) and the third bit of x have essentially the same value, true or false. In effect, the value of the third bit (bit index 2, relative to the byte) of x is equal to the value returned by the boolean expression (((1 << 2) & x) != 0). The mask (1 << 2) allows us to access the bit value indirectly using a test."

I understand that bin 100 = 4, but could someone walk me through what y=4&x is doing? Also, please explain how y!=0 and the third bit of x have the same value.

I'm new here, so if I'm in the wrong forum please direct me to a more appropriate one.

Thanks.

[seymore15074]

In C++, & is the bitwise AND operator. It operates on the individual bits of the variables supplied to it. For each bit in the expression a & b, if both the bit of a and the bit of b are 1, the resultant bit is 1; otherwise, the resultant bit is 0.
15 & 4:

00001111b = 15
00000100b = 4
--------------
00000100b = 4


Note that bit 3 of the number 15 can be checked using the bitwise AND operator.

To check a bit, a bitmask of 4 is used. In the bitmask, any bit that you want to check should be 1. If you are only checking a single bit, there will only be a single 1 in the mask.

The result of the operation, could only set the bit(s) that are 1 in the bitmask. In the example, the number 15 did have a 1 for that specific bit and in the bitmask, so the resultant bit (3rd from the right) is 1.

The actual numeric value of the result, from this example, is 4. So, after the operation, using a bitmask with only 1 digit being checked, the answer will always be either 4 or 0 depending on the bit that is being checked.

Therefor, in x = 15 & 4, x can be evaluated against either 4 or 0, like this:

int mask = 1 << 2;  // this is just short hand for saying mask = 4
int x = 15 & mask;
if( x == 0 )  // or ( x != 4 ), if you prefer
{
    // bit was not set
}
else if( x != 0 ) // or ( x == 4 ), if you prefer
{
    // bit was set
}

As mentioned above, the bitwise shift left operator (<<) can be used to shift all bits to the left a number of positions. Each single shift to the left has a "doubling" effect numerically.


00000001b = 1
00000010b = 2
00000100b = 4


There for, without having to go the extra step and figure out the numeric value of a bitmask, you could create a mask to test bit n by using 1 << n-1. For example, 1 << 2, is the bitmask (with value 4) that can be used to test bit 3.

[VictorH]

Thanks for the great explanation. BUT, just to be sure, y = 4 & x is performing bitwise & with 4 (0000 0100) and whatever the entire byte 'x' may be, say, 21 (0001 0101) So, effectively,

0000 0100
&0001 0101
---------------
0000 0100 (in this case, bit 3 set)

Sound right?

[seymore15074]

You got it.