Hello sirs, you might know that Boost has a dynamic_bitset class, but did you know that GCC also has it? Turns out it's included in the tr2 folder. You can simply include the <tr2/dynamic_bitset> header, and use it as std::tr2::dynamic_bitset. Yes, it works on Codeforces.

Here's a code example, solving abc258_g:

#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
signed main() {
    cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    int n; cin >> n;
    vector<dynamic_bitset<>> adj(n);
    for(int i = 0; i < n; i++){
        adj[i].resize(n);
        for(int j = 0; j < n; j++){
            char c; cin >> c;
            adj[i][j] = c-'0';
        }
    }
    int64_t ans = 0;
    for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) if(adj[i][j]){
        ans += (adj[i]&adj[j]).count();
    }
    cout << ans/3 << "\n";
}

The implementation seems identical to Boost's dynamic bitset, so you can read the full docs here. You can view the source here.

Comparing to std::bitset, here are some notable things I saw:

• They include more set operations, such as set difference, and checking if a bitset is a subset of another bitset.
• They include lexicographical comparisons between bitsets.
• You can append single bits, as well as whole blocks (i.e. integers)
• You can also resize it like a vector. (For some reason there's no pop_back though...)
• Find first and find next are also supported, without weird function names like std::bitset. Unfortunately, there's still no find previous :(
• You can specify the word type and allocator as template arguments.

Of course, it also has all the std::bitset functionality. However, I'm not sure how fast this is compared to std::bitset; you can let me know in the comments. Interestingly, it seems to be using 64 bit integers on Codeforces.

If you enjoyed this blog, please make sure to like and subscribe for more bitset content.