[Bugged] Dynamic Bitsets in GCC
Difference between en20 and en21, changed 50 character(s)
**UPD: Unfortunately, left / right shift is bugged and doesn't clear bits [properly](https://codeforces.net/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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en22 English bitset 2024-06-12 19:17:27 150 Tiny change: 'gain when it's on Codef' -> 'gain when the fix is on Codef'
en21 English bitset 2024-06-08 23:19:49 50 (published)
en20 English bitset 2024-06-08 23:19:28 11
en19 English bitset 2024-06-08 23:12:35 272 Tiny change: '1157481). \n\nI'll keep ' -> '1157481). I'll keep ' (saved to drafts)
en18 English bitset 2024-05-13 23:50:33 0 (published)
en17 English bitset 2024-05-13 23:45:34 3 Tiny change: 'ames like std::bits' -> 'ames like in std::bits'
en16 English bitset 2024-05-13 23:42:07 1 Tiny change: 'difference and check' -> 'difference, and check'
en15 English bitset 2024-05-13 23:41:38 1 Tiny change: 'difference, and check' -> 'difference and check'
en14 English bitset 2024-05-13 23:39:11 7 Tiny change: 's all the std::bits' -> 's all the normal std::bits'
en13 English bitset 2024-05-13 23:37:23 17
en12 English bitset 2024-05-13 23:35:34 18
en11 English bitset 2024-05-13 23:31:33 14 Tiny change: 'mentation seems ide' -> 'mentation of the bitset seems ide'
en10 English bitset 2024-05-13 23:30:22 9 Tiny change: ' to use a max sized bit' -> ' to use a constant sized bit'
en9 English bitset 2024-05-13 23:29:46 21 Tiny change: 'er>\n\nIn problems with test cases, we migh' -> 'er>\n\nIn some problems, we migh'
en8 English bitset 2024-05-13 23:26:19 59 Tiny change: '] content.' -> '] content.\n\nThanks [user:qmk] for helping with the blog.'
en7 English bitset 2024-05-13 23:19:28 395 Tiny change: '260853192]).\n\n\nT' -> '260853192], original [submission:217308610]).\n\n\nT'
en6 English bitset 2024-05-13 23:04:10 751 Tiny change: 'main() {\n cin.tie(0)' -> 'main() {\n cin.tie(0)'
en5 English bitset 2024-05-13 22:52:28 71
en4 English bitset 2024-05-13 22:39:57 278 Tiny change: 's I saw:\n- They i' -> 's I saw:\n\n- They i'
en3 English bitset 2024-05-13 22:30:54 54
en2 English bitset 2024-05-13 22:28:59 325
en1 English bitset 2024-05-13 22:24:34 908 Initial revision (saved to drafts)