c - Help me understand this "Programming pearls" bitsort program -

John Bentley uses a bit vector in column 1 of his book programming pearls to sort the sequence of non-zero positive integers To have a technique to introduce.

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

  / * Copyright (c) 1990 by Lucent Technologies * / / * John Bentley * / / * bitsort.c - Sort the bitmap from column 1 * in the range [0..N-1] * / #include & lt; Stdio.h & gt; # Define BITSPERWORD 32 # Define SHIFT 5 # Define MASK 0x1F #define N 10000000 int a [1 + N / BITSPERWORD]; Zero set (int i) {int sh = i & gt; & Gt; SHIFT; A [i & gt; SHIFT] | = (1 & lt; (i & amp; mask)); } Zero CLR (int i) {a [i & gt; & Gt; SHIFT] & amp; = ~ (1 & lt; (i & msk)); } Int Test (Int'l) {A [i & gt; & Gt; SHIFT] & amp; (1 & lt; & lt; (i & amp; mask)); } Int main () {int i; For (i = 0; i  

I understand what works are CLR, set and test and explain them below: (Please correct me if I am wrong here).

• set ith bit
• test ith bit

gives value, now I can not understand how they work I am unable to understand all the bip manipulation in those three tasks.

Please help.

The first 3 constants are inter-related BITSPERWORD 32. You want to set it based on your compiler + architecture. SHIFT is 5, because 2 ^ 5 = 32. Finally, MASK is 0x1F which is 11111 in binary (i.e.: 5 bits below are all sets). Equally, MASK = BITSPERWORD - 1.

The bitrate is an array of estimated bits. This implementation actually uses an array of ints, and 32bit per int, so whenever we want to set, clear or test (read), we need to find two things:

< Li> which is in the int (array)
• We are talking about that thing

Because we're counting 32 bit count, we just To get the array index, you can divide by 32 (and truncate). 32 (BITSPRR Verde) is the same as the transfer on the right by the 5 (SHIFT). So this is about a [i >> SHIFT] bit, you can also write it as [i / BITSPERWORD] (and in fact, you will probably get the same or very similar code, assuming that your The compiler has the proper adapter).

Now that we know which elements we want, we should know what bit is actually, we want the rest we can do it with% BITSPERWORD, but it has come to know The reason that I & MASK is equal is because BITSPERWORD 2 has the power (2 ^ 5 in this case) and MASK is set below 5 bits.