What is the most effective way to erase individual bits in a bitset? is it XOR or AND/NOT?

Question

I have a large bitset that I want to frequently reset individual bits in it. Which method is faster?

a) bitset[word_index] ^= 1 << bit_index

or

b) bitset[word_index] &= ~(1 << bit_index)

The application is for the desktop (if that plays a role).

Answer 1

They don't do the same thing.

Option a will flip the given bit; option b will clear it. Go with whichever actually reflects your intention. If you want to clear the bit but you happen to know it will always be set, I'd use option b as it states the "clear the bit" part more obviously.

When you say you want to do this "frequently" - just how frequently is this? Do you have any evidence to suggest that this is the bottleneck in your application? If not, why are you interested in the fastest way of doing it rather than the most readable way?

Answer 2

Assuming your code correctly does what you intend it to: this is termed a micro-optimisation.

There is unlikely to be any substantial difference. A good optimising compiler will produce fast code either way.

Suggest you benchmark in your particular circumstances. (Also, suggest you write unit tests)

Answer 3

if you want to CLEAR a bit at position N you have to set up a mask with a 0 in position N and 1s everywhere else then use the bitwise AND operator like this:

a &= ~(1 << N);

if you want to SET a bit at position N you have to set up a mask with a 1 in position N and 0s everywhere else then use the bitwise OR operator like this:

a |= (1 << N);

if you want to TOGGLE a bit at position N you have to set up a mask with a 1 in position N and 0s everywhere else then use the bitwise XOR operator like this:

a ^= (1 << N);

you can apply the same reasoning to affect multiple bits at once, typically by ORing togethre individual bit-masks. For example to clear the 3rd, 5th, and 9th bits in a you might do:

a &= ~( (1 << 3) | (1 << 5) | (1 << 9) );

why would you do it like that instead of just saying:

a &= 0x0DD7;

two reasons -

(1) typically the 3, 5, and 9 won't be literals, but defined constants for better readability. (2) the compiler will turn it into that at compile time anyway (given that you use constants), no need to make your code less readable.