为什么我们需要一个可变长度位集？

在 C++ 中，位集（bitset）通常用于存储一系列布尔值。标准库提供了 std::bitset，但它的大小必须在编译时确定。对于需要动态大小的场景（如图形学中的像素掩码、数据库中的标记位、或网络协议的位域），我们需要一个在运行时可调整大小的位集。下面我们用 std::vector<uint64_t> 实现一个可变长度位集，并讨论其实现细节、性能以及典型用例。

1. 设计目标

2. 基本实现

#include <vector>
#include <cstdint>
#include <stdexcept>
#include <iostream>
#include <iomanip>

class DynamicBitset {
    std::vector <uint64_t> data_;
    size_t bit_count_;           // 实际位数

    static constexpr size_t BITS_PER_BLOCK = 64;
    static constexpr uint64_t BLOCK_MASK = 0xFFFFFFFFFFFFFFFFULL;

    // 确保内部 vector 至少能存放 n 位
    void ensure_size(size_t n) {
        size_t needed_blocks = (n + BITS_PER_BLOCK - 1) / BITS_PER_BLOCK;
        if (data_.size() < needed_blocks)
            data_.resize(needed_blocks, 0);
    }

    // 对给定索引进行边界检查
    void check_index(size_t idx) const {
        if (idx >= bit_count_)
            throw std::out_of_range("DynamicBitset: index out of range");
    }

public:
    DynamicBitset() : bit_count_(0) {}

    explicit DynamicBitset(size_t n, bool init = false) : bit_count_(n) {
        ensure_size(n);
        if (!init) std::fill(data_.begin(), data_.end(), 0);
    }

    size_t size() const noexcept { return bit_count_; }

    void resize(size_t n, bool init = false) {
        if (n < bit_count_) {
            // 需要清除超出的位
            for (size_t i = n; i < bit_count_; ++i)
                reset(i);
        }
        bit_count_ = n;
        ensure_size(n);
        if (init) std::fill(data_.begin(), data_.end(), 0);
    }

    // 单个位操作
    bool test(size_t idx) const { 
        check_index(idx);
        size_t block = idx / BITS_PER_BLOCK;
        size_t offset = idx % BITS_PER_BLOCK;
        return (data_[block] >> offset) & 1ULL;
    }

    void set(size_t idx, bool value = true) { 
        check_index(idx);
        size_t block = idx / BITS_PER_BLOCK;
        size_t offset = idx % BITS_PER_BLOCK;
        if (value)
            data_[block] |= (1ULL << offset);
        else
            data_[block] &= ~(1ULL << offset);
    }

    void reset(size_t idx) { set(idx, false); }
    void flip(size_t idx) { 
        check_index(idx);
        size_t block = idx / BITS_PER_BLOCK;
        size_t offset = idx % BITS_PER_BLOCK;
        data_[block] ^= (1ULL << offset);
    }

    // 批量操作
    void setAll(bool value = true) {
        std::fill(data_.begin(), data_.end(), value ? BLOCK_MASK : 0);
    }

    void resetAll() { setAll(false); }

    void flipAll() {
        for (auto &block : data_) block ^= BLOCK_MASK;
    }

    // 位运算
    DynamicBitset operator|(const DynamicBitset& rhs) const {
        DynamicBitset result(std::max(bit_count_, rhs.bit_count_), false);
        for (size_t i = 0; i < result.data_.size(); ++i) {
            uint64_t a = (i < data_.size()) ? data_[i] : 0;
            uint64_t b = (i < rhs.data_.size()) ? rhs.data_[i] : 0;
            result.data_[i] = a | b;
        }
        return result;
    }

    DynamicBitset operator&(const DynamicBitset& rhs) const {
        DynamicBitset result(std::max(bit_count_, rhs.bit_count_), false);
        for (size_t i = 0; i < result.data_.size(); ++i) {
            uint64_t a = (i < data_.size()) ? data_[i] : 0;
            uint64_t b = (i < rhs.data_.size()) ? rhs.data_[i] : 0;
            result.data_[i] = a & b;
        }
        return result;
    }

    DynamicBitset operator^(const DynamicBitset& rhs) const {
        DynamicBitset result(std::max(bit_count_, rhs.bit_count_), false);
        for (size_t i = 0; i < result.data_.size(); ++i) {
            uint64_t a = (i < data_.size()) ? data_[i] : 0;
            uint64_t b = (i < rhs.data_.size()) ? rhs.data_[i] : 0;
            result.data_[i] = a ^ b;
        }
        return result;
    }

    // 迭代器支持（仅遍历 1 位）
    class iterator {
        const DynamicBitset &bs_;
        size_t pos_;
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = bool;
        using difference_type = std::ptrdiff_t;
        using pointer = bool*;
        using reference = bool;

        iterator(const DynamicBitset &bs, size_t pos) : bs_(bs), pos_(pos) {}

        bool operator*() const { return bs_.test(pos_); }
        iterator &operator++() { ++pos_; return *this; }
        bool operator==(const iterator &other) const { return pos_ == other.pos_; }
        bool operator!=(const iterator &other) const { return !(*this == other); }
    };

    iterator begin() const { return iterator(*this, 0); }
    iterator end() const { return iterator(*this, bit_count_); }

    // 打印为二进制字符串（最高位在左侧）
    std::string to_string() const {
        std::string s;
        s.reserve(bit_count_);
        for (size_t i = bit_count_; i > 0; --i)
            s += test(i - 1) ? '1' : '0';
        return s;
    }
};

3. 性能考量

1. 内存布局
   `std::vector

   ` 的连续内存提供了缓存友好性。对 64 位块进行掩码运算是 SIMD 友好的，现代 CPU 对此非常优化。

2. 单个位操作
   通过位运算（>>, &, |, ^）实现 O(1) 复杂度。与 std::bitset 的实现相同，唯一差别是我们在运行时需要除以 64 来定位块。

3. 扩容
   ensure_size 会在需要时重新分配向量。若频繁增大位数，最好预估最大大小并一次性分配，以减少重分配成本。

4. 批量运算
   对整个 vector 进行按位操作（OR/AND/XOR）在块级别完成，时间复杂度为 O(n_blocks)。如果需要大量此类运算，建议使用 SIMD 指令集（AVX/AVX2/AVX512）进一步优化。

4. 示例用法

int main() {
    DynamicBitset bs1(130);          // 130 位，全部 0
    bs1.set(0);                      // 位置 0 置 1
    bs1.set(65);                     // 位置 65 置 1
    bs1.set(129);                    // 位置 129 置 1

    std::cout << "bs1: " << bs1.to_string() << '\n';

    DynamicBitset bs2(130, true);    // 全部 1
    bs2.reset(65);                   // 位置 65 清 0

    auto bs_or = bs1 | bs2;
    std::cout << "bs1 | bs2: " << bs_or.to_string() << '\n';

    auto bs_and = bs1 & bs2;
    std::cout << "bs1 & bs2: " << bs_and.to_string() << '\n';

    // 逐位打印
    std::cout << "Bits set in bs1:\n";
    for (size_t i = 0; i < bs1.size(); ++i)
        if (bs1.test(i)) std::cout << i << ' ';
    std::cout << '\n';
}

运行结果示例（仅演示部分）：

bs1: 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000