CODEWITHSUNDEEP
bit-manipulation
Telenoobies
Telenoobies

Reputation: 936

Implement bit vector using bitwise logical operations

This question is asked on Pearls of programming Question 2. And I am having trouble understanding its solution.

Here is the solution written in the book.

#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)); }
void clr(int i) { a[i>>SHIFT]&=~(1<<(i & MASK));  }
int test(int i) { return a[i>>SHIFT]&(1<<(i & MASK)); }

I have ran this in my compiler and I have looked at another question that talks about this problem, but I still dont understand how this solution works.

Why does it do a[i>>SHIFT]? Why cant it just be a[i]=1; Why does i need to shifted right 5 times?

Upvotes: 3

Views: 1193

Answers (2)

displayName
displayName

Reputation: 14379

Divide the 32 bits of int i (starting form bit 0 to bit 31) into two parts.

  • First part is the most significant bits 31 to 5. Use this part to find the index in the array of ints (called a[] here) that you are using to implement the bit array. Initially, the entire array of ints is zeroed out.

Since every int in a[] is 32 bits, it can keep track of 32 ints with those 32 bits. We divide every input i with 32 to find the int in a[] that is supposed to keep track of this i.

Every time a number is divided by 2, it is effectively right shifted once. To divide a number by 32, you simply right shift it 5 times. And that is exactly what we get by filtering out the first part.

  • Second part is the least significant bits 0 to 4. After a number has been binned into the correct index, use this part to set the specific bit of the zero stored in a[] at this index. Obviously, if some bit of the zero at this index has already been set, the value at that index will not be zero anymore.

How to get the first part? Right shifting i by 5 (i.e. i >> SHIFT).

How to get the second part? Do bitwise AND of i by 11111. (11111)2 = 0x1F, defined as MASK. So, i & MASK will give the integer value represented by the last 5 bits of i.

The last 5 bits tell you how many bits to go inside the number in a[]. For example, if i is 5, you want to set the bit in the index 0 of a[] and you specifically want to set the 5th bit of the int value a[0].

Index to set = 5 / 32 = (0101 >> 5) = 0000 = 0.

Bit to set = 5th bit inside a[0]

  • = a[0] & (1 << 5)
  • = a[0] & (1 << (00101 & 11111)).

Setting the bit for given i

  1. Get the int to set by a[i >> 5]
  2. Get the bit to set by pushing a 1 a total of i % 32 times to the left i.e. 1 << (i & 0x1F)
  3. Simply set the bit as a[i >> 5] = a[i >> 5] | (1 << (i & 0x1F));
  4. That can be shortened to a[i >> 5] |= (1 << (i & 0x1F));

Getting/Testing the bit for given i

  1. Get the int where the desired bit lies by a[i >> 5]
  2. Generate a number where all bits except for the i & 0x1F bit are 0. You can do that by negating 1 << (i & 0x1F).
  3. AND the number generated above with the value stored at this index in a[]. If the value is 0, this particular bit was 0. If the value is non-zero, this bit was 1.
  4. In code you would simply, return a[i >> 5] & (1 << (i & 0x1F)) != 0;

Clearing the bit for given i: It means setting the bit for that i to 0.

  1. Get the int where the bit lies by a[i >> 5]
  2. Get the bit by 1 << (i & 0x1F)
  3. Invert all the bits of 1 << (i & 0x1F) so that the i's bit is 0.
  4. AND the number at this index and the number generated in step 3. That will clear i's bit, leaving all other bits intact.
  5. In code, this would be: a[i >> 5] &= ~(1 << (i & 0x1F));

Upvotes: 2

Chris Dodd
Chris Dodd

Reputation: 126203

32 is 25, so a right-shift of 5 bits is equivalent to dividing by 32. So by doing a[i>>5], you are dividing i by 32 to figure out which element of the array contains bit i -- there are 32 bits per element.

Meanwhile & MASK is equivalent to mod 32, so 1<<(i & MASK) builds a 1-bit mask for the particular bit within the word.

Upvotes: 3

Related Questions