Dynamic Bitset
(utilities/dynamic_bitset.hpp)

• View this file on GitHub
• Last update: 2026-06-21 04:03:53+09:00
• Include: #include "utilities/dynamic_bitset.hpp"

Overview

DynamicBitset is a dynamically-sized packed bit array. Unlike std::bitset, whose size must be a compile-time constant, DynamicBitset stores bits in std::vector<uint64_t>, so the logical size can be decided at runtime.

Bits are packed into 64-bit blocks. Single-bit access is constant time, while bulk operations scan one machine word at a time. The implementation keeps unused bits in the last block cleared, so popcount(), all(), topbit(), and bitwise operations operate only on the logical bit range.

Methods

Method	Description	Complexity
DynamicBitset()	Initializes an empty bitset of size 0.	$O(1)$
explicit DynamicBitset(int n, bool val = false)	Initializes a bitset of size n. If val is true, all logical bits are set to 1; otherwise they are set to 0.	$O(N / 64)$
int size() const	Returns the logical number of bits.	$O(1)$
bool test(int i) const	Returns whether bit i is set.	$O(1)$
void set(int i)	Sets bit i to true.	$O(1)$
void set()	Sets all logical bits to true.	$O(N / 64)$
void reset(int i)	Sets bit i to false.	$O(1)$
void reset()	Sets all bits to false.	$O(N / 64)$
void flip(int i)	Flips bit i.	$O(1)$
void flip()	Flips all logical bits.	$O(N / 64)$
int popcount() const	Returns the number of set bits. This replaces the old count() name.	$O(N / 64)$
int lowbit() const	Returns the smallest index i such that bit i is set, or -1 if no bit is set.	$O(N / 64)$
int topbit() const	Returns the largest index i such that bit i is set, or -1 if no bit is set.	$O(N / 64)$
bool any() const	Returns true if at least one bit is set.	$O(N / 64)$
bool all() const	Returns true if all logical bits are set. For size 0, this returns true.	$O(N / 64)$
bool none() const	Returns true if no bit is set.	$O(N / 64)$
operator&=, operator|=, operator^=	Performs an in-place bitwise operation with another bitset of the same size.	$O(N / 64)$
operator&, operator|, operator^, operator~	Returns the result of a bitwise operation.	$O(N / 64)$

Notes

• count() was renamed to popcount() to make the operation explicit and consistent with CPU terminology.
• lowbit() and topbit() return bit indices, not bit masks.
• The implementation uses __builtin_popcountll, __builtin_ctzll, and __builtin_clzll, so it targets GCC/Clang-compatible competitive-programming environments.
• Unused high bits in the last 64-bit block are always cleared after operations that may touch them.

Example

#include "utilities/dynamic_bitset.hpp"
#include <iostream>

int main() {
    m1une::utilities::DynamicBitset bs(100);

    bs.set(10);
    bs.set(25);
    bs.flip(50);

    std::cout << bs.popcount() << "\n";  // 3
    std::cout << bs.lowbit() << "\n";    // 10
    std::cout << bs.topbit() << "\n";    // 50
    std::cout << bs.test(99) << "\n";   // 0

    m1une::utilities::DynamicBitset bs2(100, true);
    bs2.reset(10);

    m1une::utilities::DynamicBitset bs3 = bs & bs2;

    std::cout << bs3.test(10) << "\n";      // 0
    std::cout << bs3.popcount() << "\n";    // 2
    std::cout << (~bs3).popcount() << "\n"; // 98

    return 0;
}

Required by

• Graph All (graph/all.hpp)
• DAG Algorithms (graph/dag.hpp)
• DAG Reachability and Transitive Reduction (graph/dag_reachability.hpp)
• Directed Graph Algorithms (graph/directed.hpp)

Verified with

• verify/graph/cow_game.test.cpp
• verify/graph/dag_algorithms.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/range_edge_graph.test.cpp
• verify/utilities/dynamic_bitset.test.cpp

Code

#ifndef M1UNE_UTILITIES_DYNAMIC_BITSET_HPP
#define M1UNE_UTILITIES_DYNAMIC_BITSET_HPP 1

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

namespace m1une {
namespace utilities {

struct DynamicBitset {
   private:
    static constexpr int BITS_PER_BLOCK = 64;
    static constexpr uint64_t FULL_BLOCK = ~uint64_t{0};

    int _n;
    std::vector<uint64_t> blocks;

    static int block_count(int n) {
        assert(n >= 0);
        return (n + BITS_PER_BLOCK - 1) >> 6;
    }

    uint64_t tail_mask() const {
        const int rem = _n & (BITS_PER_BLOCK - 1);
        return rem == 0 ? FULL_BLOCK : ((uint64_t{1} << rem) - 1);
    }

    // Keep unused bits in the last block equal to zero.
    void clean() {
        if (!blocks.empty()) blocks.back() &= tail_mask();
    }

   public:
    DynamicBitset() : _n(0), blocks() {}

    explicit DynamicBitset(int n, bool val = false) : _n(n), blocks(block_count(n), val ? FULL_BLOCK : 0) {
        if (val) clean();
    }

    // Returns the logical number of bits.
    int size() const {
        return _n;
    }

    // Returns whether the bit at index i is set.
    bool test(int i) const {
        assert(0 <= i && i < _n);
        return (blocks[i >> 6] >> (i & (BITS_PER_BLOCK - 1))) & 1;
    }

    // Sets the bit at index i to true.
    void set(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] |= uint64_t{1} << (i & (BITS_PER_BLOCK - 1));
    }

    // Sets all bits to true.
    void set() {
        std::fill(blocks.begin(), blocks.end(), FULL_BLOCK);
        clean();
    }

    // Sets the bit at index i to false.
    void reset(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] &= ~(uint64_t{1} << (i & (BITS_PER_BLOCK - 1)));
    }

    // Sets all bits to false.
    void reset() {
        std::fill(blocks.begin(), blocks.end(), uint64_t{0});
    }

    // Flips the bit at index i.
    void flip(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] ^= uint64_t{1} << (i & (BITS_PER_BLOCK - 1));
    }

    // Flips all bits.
    void flip() {
        for (uint64_t& block : blocks) block = ~block;
        clean();
    }

    // Returns the number of set bits.
    int popcount() const {
        int res = 0;
        for (uint64_t block : blocks) res += __builtin_popcountll(block);
        return res;
    }

    // Returns the index of the least significant set bit, or -1 if no bit is set.
    int lowbit() const {
        const int m = static_cast<int>(blocks.size());
        for (int i = 0; i < m; ++i) {
            if (blocks[i] != 0) return (i << 6) + __builtin_ctzll(blocks[i]);
        }
        return -1;
    }

    // Returns the index of the most significant set bit, or -1 if no bit is set.
    int topbit() const {
        for (int i = static_cast<int>(blocks.size()) - 1; i >= 0; --i) {
            if (blocks[i] != 0) return (i << 6) + (BITS_PER_BLOCK - 1 - __builtin_clzll(blocks[i]));
        }
        return -1;
    }

    // Returns whether at least one bit is set.
    bool any() const {
        for (uint64_t block : blocks) {
            if (block != 0) return true;
        }
        return false;
    }

    // Returns whether every logical bit is set.
    bool all() const {
        if (_n == 0) return true;

        const int m = static_cast<int>(blocks.size());
        for (int i = 0; i + 1 < m; ++i) {
            if (blocks[i] != FULL_BLOCK) return false;
        }
        return blocks.back() == tail_mask();
    }

    // Returns whether no bit is set.
    bool none() const {
        return !any();
    }

    DynamicBitset& operator&=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] &= other.blocks[i];
        return *this;
    }

    DynamicBitset& operator|=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] |= other.blocks[i];
        return *this;
    }

    DynamicBitset& operator^=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] ^= other.blocks[i];
        return *this;
    }

    DynamicBitset operator~() const {
        DynamicBitset res = *this;
        res.flip();
        return res;
    }

    friend DynamicBitset operator&(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs &= rhs;
        return lhs;
    }

    friend DynamicBitset operator|(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs |= rhs;
        return lhs;
    }

    friend DynamicBitset operator^(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs ^= rhs;
        return lhs;
    }
};

}  // namespace utilities
}  // namespace m1une

#endif  // M1UNE_UTILITIES_DYNAMIC_BITSET_HPP

#line 1 "utilities/dynamic_bitset.hpp"



#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

namespace m1une {
namespace utilities {

struct DynamicBitset {
   private:
    static constexpr int BITS_PER_BLOCK = 64;
    static constexpr uint64_t FULL_BLOCK = ~uint64_t{0};

    int _n;
    std::vector<uint64_t> blocks;

    static int block_count(int n) {
        assert(n >= 0);
        return (n + BITS_PER_BLOCK - 1) >> 6;
    }

    uint64_t tail_mask() const {
        const int rem = _n & (BITS_PER_BLOCK - 1);
        return rem == 0 ? FULL_BLOCK : ((uint64_t{1} << rem) - 1);
    }

    // Keep unused bits in the last block equal to zero.
    void clean() {
        if (!blocks.empty()) blocks.back() &= tail_mask();
    }

   public:
    DynamicBitset() : _n(0), blocks() {}

    explicit DynamicBitset(int n, bool val = false) : _n(n), blocks(block_count(n), val ? FULL_BLOCK : 0) {
        if (val) clean();
    }

    // Returns the logical number of bits.
    int size() const {
        return _n;
    }

    // Returns whether the bit at index i is set.
    bool test(int i) const {
        assert(0 <= i && i < _n);
        return (blocks[i >> 6] >> (i & (BITS_PER_BLOCK - 1))) & 1;
    }

    // Sets the bit at index i to true.
    void set(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] |= uint64_t{1} << (i & (BITS_PER_BLOCK - 1));
    }

    // Sets all bits to true.
    void set() {
        std::fill(blocks.begin(), blocks.end(), FULL_BLOCK);
        clean();
    }

    // Sets the bit at index i to false.
    void reset(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] &= ~(uint64_t{1} << (i & (BITS_PER_BLOCK - 1)));
    }

    // Sets all bits to false.
    void reset() {
        std::fill(blocks.begin(), blocks.end(), uint64_t{0});
    }

    // Flips the bit at index i.
    void flip(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] ^= uint64_t{1} << (i & (BITS_PER_BLOCK - 1));
    }

    // Flips all bits.
    void flip() {
        for (uint64_t& block : blocks) block = ~block;
        clean();
    }

    // Returns the number of set bits.
    int popcount() const {
        int res = 0;
        for (uint64_t block : blocks) res += __builtin_popcountll(block);
        return res;
    }

    // Returns the index of the least significant set bit, or -1 if no bit is set.
    int lowbit() const {
        const int m = static_cast<int>(blocks.size());
        for (int i = 0; i < m; ++i) {
            if (blocks[i] != 0) return (i << 6) + __builtin_ctzll(blocks[i]);
        }
        return -1;
    }

    // Returns the index of the most significant set bit, or -1 if no bit is set.
    int topbit() const {
        for (int i = static_cast<int>(blocks.size()) - 1; i >= 0; --i) {
            if (blocks[i] != 0) return (i << 6) + (BITS_PER_BLOCK - 1 - __builtin_clzll(blocks[i]));
        }
        return -1;
    }

    // Returns whether at least one bit is set.
    bool any() const {
        for (uint64_t block : blocks) {
            if (block != 0) return true;
        }
        return false;
    }

    // Returns whether every logical bit is set.
    bool all() const {
        if (_n == 0) return true;

        const int m = static_cast<int>(blocks.size());
        for (int i = 0; i + 1 < m; ++i) {
            if (blocks[i] != FULL_BLOCK) return false;
        }
        return blocks.back() == tail_mask();
    }

    // Returns whether no bit is set.
    bool none() const {
        return !any();
    }

    DynamicBitset& operator&=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] &= other.blocks[i];
        return *this;
    }

    DynamicBitset& operator|=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] |= other.blocks[i];
        return *this;
    }

    DynamicBitset& operator^=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] ^= other.blocks[i];
        return *this;
    }

    DynamicBitset operator~() const {
        DynamicBitset res = *this;
        res.flip();
        return res;
    }

    friend DynamicBitset operator&(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs &= rhs;
        return lhs;
    }

    friend DynamicBitset operator|(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs |= rhs;
        return lhs;
    }

    friend DynamicBitset operator^(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs ^= rhs;
        return lhs;
    }
};

}  // namespace utilities
}  // namespace m1une

Back to top page