**UPD: Unfortunately, left / right shift is bugged and doesn't clear bits [properly](https://mirror.codeforces.com/blog/entry/129454?#comment-1157481). It should be fine for other operations, but use it at your own risk.**↵
↵
<spoiler summary="Original Blog">↵
↵
Hello sirs, you might know that Boost has a dynamically sized bitset class, but did you know that GCC also has one? 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 to count triangles in a graph ([abc258_g](https://atcoder.jp/contests/abc258/tasks/abc258_g)):↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h> I wonder if it's possible to get GCC to fix it...↵
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";↵
}↵
```↵
</spoiler>↵
↵
In some problems, we might not be able to use a constant sized bitset. For example, on [problem:1856E2]. Here's a submission where we replaced [user:neal,2024-05-13]'s custom_bitset template with `using custom_bitset = tr2::dynamic_bitset<>;`, and got accepted with little performance difference ([submission:260853192], original [submission:217308610]).↵
↵
↵
The implementation of the bitset seems identical to a version of Boost's dynamic bitset, so you can read the docs [here](https://www.boost.org/doc/libs/1_33_1/libs/dynamic_bitset/dynamic_bitset.html). You can view the source [here](https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/tr2/dynamic_bitset).↵
↵
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 in 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 normal 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 [user:bitset,2024-05-13] content.↵
↵
Thanks [user:qmk,2024-05-13] for helping with the blog.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Original Blog">↵
↵
Hello sirs, you might know that Boost has a dynamically sized bitset class, but did you know that GCC also has one? 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 to count triangles in a graph ([abc258_g](https://atcoder.jp/contests/abc258/tasks/abc258_g)):↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h> I wonder if it's possible to get GCC to fix it...↵
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";↵
}↵
```↵
</spoiler>↵
↵
In some problems, we might not be able to use a constant sized bitset. For example, on [problem:1856E2]. Here's a submission where we replaced [user:neal,2024-05-13]'s custom_bitset template with `using custom_bitset = tr2::dynamic_bitset<>;`, and got accepted with little performance difference ([submission:260853192], original [submission:217308610]).↵
↵
↵
The implementation of the bitset seems identical to a version of Boost's dynamic bitset, so you can read the docs [here](https://www.boost.org/doc/libs/1_33_1/libs/dynamic_bitset/dynamic_bitset.html). You can view the source [here](https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/tr2/dynamic_bitset).↵
↵
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 in 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 normal 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 [user:bitset,2024-05-13] content.↵
↵
Thanks [user:qmk,2024-05-13] for helping with the blog.↵
↵
</spoiler>↵
↵
