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
– Grijesh Chauhan, Commented Jul 20, 2013 at 17:04
Are you sure i is int not unsigned int ? where from you bring this code ? — Grijesh Chauhan
– Grijesh Chauhan, Commented Jul 20, 2013 at 17:06
Oops. OK, so I changed it to reflect dividing by 2^5. What about the rest? — Henley Wing Chiu
– Henley Wing Chiu, Commented Jul 20, 2013 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
– Grijesh Chauhan, Commented Jul 20, 2013 at 17:09

aaronman · Accepted Answer · 2013-07-20 18:10:44Z

3

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

edited Jul 20, 2013 at 18:10

answered Jul 20, 2013 at 17:29

aaronman

18.8k8 gold badges65 silver badges81 bronze badges

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

2 Comments

Henley Wing Chiu Over a year ago

+1 for clarifying 0X1F is 31.. I thought it was 1 the whole time. WOW. That clears up a lot. Thanks.

aaronman Over a year ago

@HenleyChiu lol no problem, honestly there are much clearer ways to set a bit, I do not like this code

Collectives™ on Stack Overflow

How to implement bit vectors with bitwise operations?

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related