ph2nkhang's blog

Bitsets and Bool-Arrays
By ph2nkhang, history, 10 months ago, In English

I just found out about bitsets yesterday and tried using it. Fumbling around with it for while and I realized that it is just a bool array, but more operations built-in. I thought the size would be the limit since C++ only stores a value upto 64-bit. BUT NO, I tried craking the size way up and it works just as well as any array. That and offering every other BITWISE operations. Then I thought this might be too good to be true. So what is the difference really? Is it safe to just ditch bool arrays entirely and switch to bitsets or is there a tradeoff?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What's more bitset is much faster than vector.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Bitset is stored as a vector of SIZE/32 values of unsigned int, so every single bit is used, while bool needs 1 byte for only 1 bit of information. Also for operations like <<, >>, &, |, ^, instead of iterating all the bits, bitset iterate through the array of length SIZE/32.

So bitset<SIZE> arr; uses 8 times less memory and is 32 times faster than bool arr[SIZE]; for almost any operation.

→ Reply