邪修卡常：动态bitset

前言

由于 std::bitset 仅支持编译期固定大小，无法动态确定长度，这使得某些 \(\sum n \leq N\) 的多测题中使用 std::bitset 超时。于是我让 AI 生成了一份比赛中可用的动态bitset模版，并且测试了其在部分板题里的性能。

实现

#include 
#include 
#include 
using namespace std;

using u64 = uint64_t;

struct dynamic_bitset
{
    int n;
    std::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);   // 新块自动置零
        n = new_n;
        clean_tail();
    }

    // 读取某一位（只读，不抛异常）
    bool operator[](int pos) const {
        return (b[pos >> 6] >> (pos & 63)) & 1;
    }

    // 设置某一位
    void set(int pos, bool val = true) {
        if (val)
            b[pos >> 6] |= 1ULL << (pos & 63);
        else
            b[pos >> 6] &= ~(1ULL << (pos & 63));
    }

    // 置零某一位
    void reset(int pos) {
        b[pos >> 6] &= ~(1ULL << (pos & 63));
    }

    // 翻转某一位
    void flip(int pos) {
        b[pos >> 6] ^= 1ULL << (pos & 63);
    }

    // 位运算
    dynamic_bitset& operator&=(const dynamic_bitset& rhs) {
        for (size_t i = 0; i < b.size(); ++i) b[i] &= rhs.b[i];
        return *this;
    }
    dynamic_bitset& operator|=(const dynamic_bitset& rhs) {
        for (size_t i = 0; i < b.size(); ++i) b[i] |= rhs.b[i];
        return *this;
    }
    dynamic_bitset& operator^=(const dynamic_bitset& rhs) {
        for (size_t i = 0; i < b.size(); ++i) b[i] ^= rhs.b[i];
        return *this;
    }
    dynamic_bitset operator~() const {
        dynamic_bitset res = *this;
        for (auto& x : res.b) x = ~x;
        res.clean_tail();
        return res;
    }

    // 1 的个数
    int count() const {
        int ans = 0;
        for (auto x : b) ans += __builtin_popcountll(x);
        return ans;
    }

    // 清除尾部多余位
    void clean_tail() {
        if (n == 0) return;
        int rem = n & 63;
        if (rem) b.back() &= (1ULL << rem) - 1;
    }
};

// 非成员二元运算符（方便书写）
inline dynamic_bitset operator&(dynamic_bitset a, const dynamic_bitset& b) { return a &= b; }
inline dynamic_bitset operator|(dynamic_bitset a, const dynamic_bitset& b) { return a |= b; }
inline dynamic_bitset operator^(dynamic_bitset a, const dynamic_bitset& b) { return a ^= b; }

使用范例

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    dynamic_bitset a(10),b;
    b.resize(10);

    a.set(1), a.set(2);
    b.flip(0);

    dynamic_bitset c(a|b);
    cout << c.count() << endl;

    return 0;
}

与 std::bitset 的区别

• 不支持左移/右移
• []只读，无法通过 bit[0] = 1 来置位。置位只能使用 set 和 reset 函数
• 不支持 any、all 等函数（这些也没什么必要）
• 输出不与 cout 兼容，只能逐位遍历
• 不支持转化整数和字符串

与 std::bitset 的性能对比

【模板】传递闭包

std::bitset

动态bitset

[PA 2025] 集合 1 / Zbiory 1

std::bitset

动态bitset

可以看到与 std::bitset 的性能差距还是比较明显。但是作为一种走投无路下的卡常手段，动态bitset已经足够了。如果再追求优化，可以考虑上 SIMD 指令集，由于比赛中不确定是否能够使用，这里不太推荐。