Bitset.hpp

#include <algorithm>
#include <cstring>
#include <functional>
#include <vector>
 
class Bitset
{
 
  public:
    Bitset(size_t size, bool default_value = false)
        : num_bits(size)
    {
        bits.resize(num_blocks(), default_value ? ~0ULL : 0ULL);
 
        // Set out of bound bits to zero
        if (num_bits % BITS_PER_BLOCK != 0) {
            //                   |       out of bound       |
            // (1ULL << 40) - 1 = 00000000 00000000 00000000 11111111 11111111 11111111 11111111 11111111
            bits.back() &= (1ULL << (num_bits % BITS_PER_BLOCK)) - 1;
        }
    }
 
    size_t num_blocks() const { return (num_bits + BITS_PER_BLOCK - 1) / BITS_PER_BLOCK; }
 
    bool operator[](size_t pos) const
    {
        assert(pos < num_bits);
        return (bits[pos / BITS_PER_BLOCK] & (1ULL << (pos % BITS_PER_BLOCK))) != 0;
    }
 
    void set(size_t pos, bool value = true)
    {
        if (value) {
            bits[pos / BITS_PER_BLOCK] |= (1ULL << (pos % BITS_PER_BLOCK));
        } else {
            bits[pos / BITS_PER_BLOCK] &= ~(1ULL << (pos % BITS_PER_BLOCK));
        }
    }
 
    void clear() { std::fill(bits.begin(), bits.end(), 0ULL); }
 
    void resize(size_t new_size)
    {
        // size_t old_num_blocks = num_blocks();
        num_bits = new_size;
        bits.resize(num_blocks(), 0ULL);
        if (num_bits % BITS_PER_BLOCK != 0) {
            bits.back() &= (1ULL << (num_bits % BITS_PER_BLOCK)) - 1;
        }
    }
 
    size_t size() const { return num_bits; }
 
    template<typename BinaryOp>
    void merge(const std::vector<Bitset>& other_bitsets, BinaryOp op)
    {
        for (const auto& other : other_bitsets) {
            size_t min_blocks = std::min(num_blocks(), other.num_blocks());
            for (size_t i = 0; i < min_blocks; ++i) {
                bits[i] = op(bits[i], other.bits[i]);
            }
        }
        if (num_bits % BITS_PER_BLOCK != 0) {
            bits.back() &= (1ULL << (num_bits % BITS_PER_BLOCK)) - 1;
        }
    }
 
    void merge_or(const std::vector<Bitset>& other_bitsets) { merge(other_bitsets, std::bit_or<unsigned long long>()); }
 
    void merge_and(const std::vector<Bitset>& other_bitsets)
    {
        merge(other_bitsets, std::bit_and<unsigned long long>());
    }
 
    unsigned long long* data() { return bits.data(); }
 
    const unsigned long long* data() const { return bits.data(); }
 
  private:
    std::vector<unsigned long long> bits;
    size_t num_bits;
    static const size_t BITS_PER_BLOCK = sizeof(unsigned long long) * 8;
};