[AI Readability Summary] This guide explains a dynamic bitset implementation for competitive programming. Its core value is replacing compile-time-fixed
std::bitsetwhen the bitset length is only known at runtime and the total input size across multiple test cases is large. It solves the practical limitation of not being able to allocate a bitset dynamically, while also clarifying performance boundaries and usage patterns. Keywords: dynamic bitset, competitive programming, bitwise operations
Technical specifications capture the implementation at a glance
| Parameter | Description |
|---|---|
| Language | C++ |
| Primary use case | Dynamic bitset maintenance in competitive programming |
| Underlying storage | `std::vector |
| ` | |
| Bit-width unit | 64 bits per block |
| Core operations | set, reset, flip, count, &, |, ^, ~ |
| License/source | Example code from a blog post; no open-source license declared |
| Star count | Not provided |
| Core dependencies | ` |
,, GCC/Clang builtin__builtin_popcountll` |
This kind of dynamic bitset fills the fixed-size gap in std::bitset
`std::bitset
` benefits from aggressive compiler optimization, but `N` must be known at compile time. For problems such as multiple test cases with `∑n ≤ N`, transitive closure on graphs, or set-based DP, that assumption often does not hold. The idea behind a dynamic bitset is straightforward: use `vector ` as the underlying block array, where each `uint64_t` stores 64 bits. This preserves the benefit of block-wise parallel bitwise operations while also allowing runtime `resize`. ### The following template covers the bitset operations most commonly used in contests “`cpp #include #include #include using namespace std; using u64 = uint64_t; struct dynamic_bitset { int n; vector b; dynamic_bitset(int _n = 0) : n(_n), b((_n + 63) >> 6, 0) {} void resize(int new_n) { if (new_n == n) return; b.resize((new_n + 63) >> 6, 0); // Newly expanded blocks are automatically zero-initialized n = new_n; clean_tail(); // Clear invalid trailing bits to avoid polluted results } bool operator[](int pos) const { return (b[pos >> 6] >> (pos & 63)) & 1ULL; // Read-only access to one bit } void set(int pos, bool val = true) { if (val) b[pos >> 6] |= 1ULL > 6] &= ~(1ULL > 6] &= ~(1ULL > 6] ^= 1ULL using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); dynamic_bitset a(10), b; b.resize(10); // Determine the length at runtime a.set(1); // Set bit 1 a.set(2); // Set bit 2 b.flip(0); // Toggle bit 0 dynamic_bitset c = a | b; // Merge two sets cout