3

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?

Improve this question

2 Answers 2

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

How does dividing i by 32 figure out which element of array contains bit i?
Each element contains 32 bits, so bits 0-31 are in index 0, 32-63 in index 1, 64-95 in index 3, etc.
Each element contains 32 bits, meaning... each element is an integer? Then how is this a bit vector? Shouldnt each element of a bit vector contain only 1 bit?? I feel like I am missing something here...
@Telenoobies you may find this link helpful.
BTW, always prefer standard integer types when playing around with bits and binary masks (i.e. your example assumes 32-bit integers, so consider declaring a as an array of uint32_t instead of just int). C doesn't give you any guarantee that an int will always be 32 bits wide, this is platform-dependent.
|
2

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));
Improve this answer

6 Comments

"First part is the 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." I dont see how this finds the index in the array of ints... "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." How does this work? I dont understand...
@Telenoobies: 1. If you would use one full int to keep track of every int, you would need an array as big as the number of ints you have. But if you use every bit of every int to keep track of an int, you can use one int to keep track of 32 ints. So to find which int will have its bit modified to keep track of input i, you use the first part. (Contd.)
@Telenoobies: 2. Let the first part (defined in the answer above) of i be represented by x. You can have a total of 2^5 different ints with same first part as x because there are total 5 bits which you can set to 0 or 1 to get a new number. Those ints are x appended with 00000, which will be mapped to the first bit of the int a[x], to x appended with 11111, which will be mapped to last bit of the int represented by x. So using second part you will map every int, with same first part x, in a[x].
Oo i see I think I understand the first part now. So if i=33, then it will be placed somewhere in a[1], and if i=29, then it will be placed somewhere in a[0]?
@Telenoobies: Yes, i = 33 will be placed in a[1] at 2nd bit because a[0] will store the 32 numbers starting from 0. i = 29 will be placed in a[0] at 30th bit.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.