Using the bitmask in the program below from Pearls Programming

Question

Today I started reading “Programming Pearls,” and as I completed this exercise, I came across this question: “How would you implement your own bit vector?” When I looked at the solution, it was like this:

#define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/BITSPERWORD]; void set(int i) { a[i >> SHIFT] |= (1 << (i & MASK)); 

Where am I confused, this statement

  1 << (i & MASK) 

Can someone please explain to me what is going on here?

Answer 1

Note that MASK set in such a way that it has the lowest SHIFT bits set, where SHIFT is exactly the base-2 BITSPERWORD .

Therefore, (i & MASK) will select the least 5 bits of i , which will be the same as taking the remainder after dividing by 32 (just think about how taking the lower two digits of the decimal number gives you the remainder after dividing by 100, for example). This gives the number of bits in the word of interest to us.

1 << (i & MASK)) (this, by the way, is an expression, not an operator) now creates a value in which exactly the bit that is of interest to us is set. Combining this value into a memory word with |= will set the desired bit of the bit vector.

Answer 2

0x20 is 32, so i & 0x1F accepts i modulo 32, so you never move 32 bits. This is protection because shifting by anything that is not strictly smaller than the size of this type is undefined behavior.