How to implement bit vectors with bitwise operations?

Question

I am studying a question in the book Programming Pearls, and they recommended this function to set a bit in a bit vector. I'm a bit confused at to what it does.

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

int a[1 + N/BITSPERWORD];

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

Here is my (probably wrong) interpretation of this code. if i = 64,

1) first, it takes i and shifts it to the right by SHIFT (which is 5) bits. This is equivalent to DIVIDING (not multiplying, as I first thought) i by 2^5. So if i is 64, the index of a is 2 (64 / 2^5)

2) a[2] |= (1 << (64 & MASK))
64 & 1 = 1000000 & 01 = 1000001.
So 1 gets left shifted how many bits????

*`This is equivalent to multiplying i by 2^5.`* **NO** This is equivalent to **dividing** `i` by `2^5`. — Grijesh Chauhan, Jul 20 '13 at 17:04
Are you sure `i` is `int` not `unsigned int` **?** where from you bring this code ? — Grijesh Chauhan, Jul 20 '13 at 17:06
Oops. OK, so I changed it to reflect dividing by 2^5. What about the rest? — Henley, Jul 20 '13 at 17:06
`2 (64 / 2^5)` ? or only `(64 / 2^5)` ... think, if `1000 >> 1` == `0100` so `x >> 5` == `x / 2^5` only — Grijesh Chauhan, Jul 20 '13 at 17:09
Note that for real code, you may want to use `std::bitset` instead. It already implements most of what you may want (and probably more besides). — Jerry Coffin, Jul 20 '13 at 17:14
@Henley Chiu Here is [a **gift**](http://stackoverflow.com/questions/7218764/bit-mask-usage-in-the-program-below-from-programming-pearls?answertab=votes#tab-top) for you. — Grijesh Chauhan, Jul 20 '13 at 17:20
@aaronman ok but because you have answered to Henley so every thing is fine. — Grijesh Chauhan, Jul 20 '13 at 18:13
@GrijeshChauhan if your responding to the deleted comment I actually made a mistake — aaronman, Jul 20 '13 at 18:27

aaronman · Accepted Answer · 2013-07-20T18:10:44.687

It seems how this method works, even though I feel like there are better ways to set a bit. Is to find the index of the ith bit it essentially divides by 32 because that is the number of bits per word.
Since the operator used here is | the function is setting the bit to one not toggling the bit
0x1F is actually 31 and when anded with the i you get the remainder (not sure why they just didn't use %)
And lastly the shift takes the 1 to the proper location and or's it with the right slot in the vector.

If you are planning to use this code

you could write it a lot clear without defines and using more obvious methods of doing it, I doubt it would make a difference in speed.
Also you should probably just use std::bitset
the use of the mask to get the remainder particularly annoyed me because I'm pretty sure it would not necessarily work for every number, 31 happens to work because it's all 1's

+1 for clarifying 0X1F is 31.. I thought it was 1 the whole time. WOW. That clears up a lot. Thanks. — Henley, Jul 20 '13 at 17:50
@HenleyChiu lol no problem, honestly there are much clearer ways to set a bit, I do not like this code — aaronman, Jul 20 '13 at 17:51

How to implement bit vectors with bitwise operations?

1 Answers1