Disclaimer: It might have bugs, don't send me death threats if you FST.
I couldn't find a nice dynamic bitset template so I wrote one.
It can be found here.
It has additional functionality as compared to std::bitset
(you can answer many kinds of range queries on it, for example: "Find $$$k$$$-th set bit in range $$$[l, r]$$$).
Efficiency:
Firstly, always use the following pragmas with it:
They can reduce runtime by upto 50% (thanks to mr qmk for enlightening me on this).
I am too lazy to run any proper benchmarks, but I solved a few problems with it and it was always faster than std::bitset
and tr2::dynamic_bitset
. Here are some sets of submissions on the same problem with all 3:
1. Using &=
, |
and >>
Bitset | Time | Memory |
---|---|---|
My bitset | 765 ms | 944 KB |
std::bitset | 859 ms | 1628 KB |
tr2::dynamic_bitset | 1077 ms | 1240 KB |
2. Using &=
, >>=
Bitset | Time | Memory |
---|---|---|
My bitset | 390 ms | 1168 KB |
std::bitset | 374 ms | 1152 KB |
tr2::dynamic_bitset | 390 ms | 1160 KB |
So it seems that my bitset is as good or slightly better in every manner. I have no idea why this is the case though, as there is nothing which seems particularly faster in my implementation.
If you use it and find some bugs, let me know.
Thanks for reading my blog.
Note: I will optimize it with SIMD in a couple of days, so it might become faster.
Nice!!
Nice