bit vector implementation of set in Programming Pearls, 2nd Edition

Question

On Page 140 of Programming Pearls, 2nd Edition, Jon proposed an implementation of sets with bit vectors.

We'll turn now to two final structures that exploit the fact that our sets represent integers. Bit vectors are an old friend from Column 1. Here are their private data and functions:

enum { BITSPERWORD = 32, SHIFT = 5, MASK = 0x1F };
int n, hi, *x;
void set(int i)  {        x[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i)  {        x[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i) { return x[i>>SHIFT] &=  (1<<(i & MASK)); }

As I gathered, the central idea of a bit vector to represent an integer set, as described in Column 1, is that the i-th bit is turned on if and only if the integer i is in the set.

But I am really at a loss at the algorithms involved in the above three functions. And the book doesn't give an explanation.

I can only get that i & MASK is to get the lower 5 bits of i, while i>>SHIFT is to move i 5 bits toward the right.

Anybody would elaborate more on these algorithms? Bit operations always seem a myth to me, :(

Answer 1

If you store your bits in an array of n words you can imagine them to be layed out as a matrix with n rows and 32 columns (BITSPERWORD):

         3                                         0
         1                                         0
      0  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx
      1  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx
      2  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx     
      ....
      n  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx

To get the k-th bit you divide k by 32. The (integer) result will give you the row (word) the bit is in, the reminder will give you which bit is within the word.

Dividing by 2^p can be done simply by shifting p postions to the right. The reminder can be obtained by getting the p rightmost bits (i.e the bitwise AND with (2^p - 1)).

In C terms:

#define div32(k) ((k) >> 5)
#define mod32(k) ((k) & 31)

#define word_the_bit_is_in(k) div32(k)
#define bit_within_word(k)    mod32(k)

Hope it helps.