Jon Bentley in Column 1 of his book programming pearls introduces a technique for sorting a sequence of non-zero positive integers using bit vectors.

I have taken the program bitsort.c from here and pasted it below:

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* bitsort.c -- bitmap sort from Column 1
 *   Sort distinct integers in the range [0..N-1]
 */

#include <stdio.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1 + N/BITSPERWORD];

void set(int i) 
{
    int sh = i>>SHIFT;
    a[i>>SHIFT] |=  (1<<(i & MASK)); 
}
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

int main()
{   int i;
for (i = 0; i < N; i++)
	clr(i);

    /*Replace above 2 lines with below 3 for word-parallel init
    int top = 1 + N/BITSPERWORD;
    for (i = 0; i < top; i++)
	a[i] = 0;
    */

while (scanf("%d", &i) != EOF)
	set(i);
for (i = 0; i < N; i++)
        if (test(i))
	printf("%d\n", i);
return 0;
}

I understand what the functions clr, set and test are doing and explain them below: ( please correct me if I am wrong here ).

• clr clears the ith bit
• set sets the ith bit
• test returns the value at the ith bit

Now, I don't understand how the functions do what they do. I am unable to figure out all the bit manipulation happening in those three functions.

Please help.