# How do the bit manipulations in this bit-sorting code work?

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][1] 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 #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. [1]: https://web.archive.org/web/20080725054521/http://www.cs.bell-labs.com/cm/cs/pearls/code.html
I will accept Laurence's answer as it helped me understand about the mechanics of the program at a fundamental level.