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 rewhile 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 &=, >>=

edit: Redid these because apparently the server was under high load at the time of the initial submissions.

1. My bitset: 284262107
2. std::bitset: 284277251
3. tr2::dynamic_bitset: 284267738

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.

Parting notes:

1. If you use it and find some bugs, let me know.
2. If you think it's missing some significant functionality, let me know.

Thanks for reading my blog.

Edit (05/05/2025): Better version here.