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:

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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 >>

1. My bitset: 284156267
2. std::bitset: 284156622
3. tr2::dynamic_bitset: 284156883

2. Using &=, >>=

1. My bitset: 284178932
2. std::bitset: 284179453
3. tr2::dynamic_bitset: 284179758

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.