std::bitset with dynamic size (tools/dynamic_bitset.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-03-15 22:50:56+09:00
• Include: #include "tools/dynamic_bitset.hpp"

It is a sequence of bits of length $n$ determined at runtime. Its interface is compatible to that of std::bitset.

License

• CC0

Author

• anqooqie

Methods based on std::bitset

dynamic_bitset s();
dynamic_bitset s(const dynamic_bitset& t);
dynamic_bitset s(dynamic_bitset&& t);
dynamic_bitset& s.operator=(const dynamic_bitset& t);
dynamic_bitset& s.operator=(dynamic_bitset&& t);

dynamic_bitset s(std::size_t n);
dynamic_bitset s(const std::string& str);

dynamic_bitset& s.operator&=(const dynamic_bitset& t);
dynamic_bitset& s.operator|=(const dynamic_bitset& t);
dynamic_bitset& s.operator^=(const dynamic_bitset& t);
dynamic_bitset& s.operator<<=(std::size_t pos);
dynamic_bitset& s.operator>>=(std::size_t pos);
dynamic_bitset& s.set();
dynamic_bitset& s.set(std::size_t pos);
dynamic_bitset& s.set(std::size_t pos, bool val);
dynamic_bitset& s.reset();
dynamic_bitset& s.reset(std::size_t pos);
dynamic_bitset s.operator~() const;
dynamic_bitset& s.flip();
dynamic_bitset& s.flip(std::size_t pos);

typename dynamic_bitset::reference s.operator[](std::size_t pos);
bool s.operator[](std::size_t pos) const;
std::size_t s.count() const;
std::size_t s.size() const;
bool s.test(std::size_t pos) const;
bool s.all() const;
bool s.any() const;
bool s.none() const;
std::string s.to_string() const;
bool operator==(const dynamic_bitset& s, const dynamic_bitset& t);
bool operator!=(const dynamic_bitset& s, const dynamic_bitset& t);
dynamic_bitset s.operator<<(std::size_t pos) const;
dynamic_bitset s.operator>>(std::size_t pos) const;

dynamic_bitset operator&(const dynamic_bitset& s, const dynamic_bitset& t);
dynamic_bitset operator|(const dynamic_bitset& s, const dynamic_bitset& t);
dynamic_bitset operator^(const dynamic_bitset& s, const dynamic_bitset& t);
std::istream& operator>>(std::istream& is, dynamic_bitset& s);
std::ostream& operator<<(std::ostream& os, const dynamic_bitset& s);

struct reference {
  reference& operator=(bool x);
  reference& operator=(const reference& other);
  bool operator~() const;
  operator bool() const;
  reference& flip();
};

They are methods based on std::bitset.

Constraints

• Same as ones of std::bitset.

Time Complexity

• Same as ones of std::bitset.

empty

bool s.empty();

It returns whether $n$ is $0$ or not.

Constraints

• None

Time Complexity

• $O(1)$

resize

void s.resize(std::size_t m);

It resizes s to contain $m$ bits. If the current size $n$ is greater than $m$, s is reduced to its first $m$ bits. If the current size $n$ is less than $m$, additional $0$s are appended to s.

Constraints

• None

Time Complexity

• $O(n)$

shrink_to_fit

void s.shrink_to_fit();

It requests the removal of unused memory allocated for s. It is a non-binding request. It depends on the implementation whether the request is fulfilled.

Constraints

• None

Time Complexity

• $O(n)$

Find_first

std::size_t s.Find_first();

It returns the least $i$ such that $0 \leq i < n$ and s.test(i) hold. If such the integer does not exist, it returns $n$.

Constraints

• None

Time Complexity

• $O(i)$ where $i$ is the return value of s.Find_first()

Find_next

std::size_t s.Find_next(std::size_t i);

It returns the least $j$ such that $i < j < n$ and s.test(j) hold. If such the integer does not exist, it returns $n$.

Constraints

• $i < n$

Time Complexity

• $O(j - i)$ where $j$ is the return value of s.Find_next(i)

Depends on

• $\left\lceil \frac{x}{y} \right\rceil$ (tools/ceil.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)

Required by

• tools/matrix_mod2.hpp

Verified with

• tests/matrix_mod2/determinant.test.cpp
• tests/matrix_mod2/inv.test.cpp
• tests/matrix_mod2/multiplies.test.cpp
• tests/matrix_mod2/rank.test.cpp
• tests/matrix_mod2/solve.test.cpp
• tests/rotl.test.cpp
• tests/rotr.test.cpp
• tests/scc_graph/edges_to_scc.test.cpp

Code

#ifndef TOOLS_DYNAMIC_BITSET_HPP
#define TOOLS_DYNAMIC_BITSET_HPP

#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <limits>
#include <sstream>
#include <string>
#include <vector>
#include "tools/ceil.hpp"

namespace tools {
  class dynamic_bitset {
    constexpr static ::std::size_t W = ::std::numeric_limits<::std::uint64_t>::digits;
    ::std::size_t m_size;
    ::std::vector<::std::uint64_t> m_bits;

  public:
    class reference {
      friend class ::tools::dynamic_bitset;

      ::tools::dynamic_bitset *m_parent;
      ::std::size_t m_pos;

      reference(::tools::dynamic_bitset * const parent, const ::std::size_t pos) : m_parent(parent), m_pos(pos) {
      }

    public:
      reference(const reference&) = default;
      reference& operator=(const bool x) {
        this->m_parent->set(this->m_pos, x);
        return *this;
      }
      reference& operator=(const reference& other) {
        return *this = static_cast<bool>(other);
      }
      bool operator~() const {
        return !static_cast<bool>(*this);
      }
      operator bool() const {
        return this->m_parent->test(this->m_pos);
      }
      reference& flip() {
        this->m_parent->flip(this->m_pos);
        return *this;
      }
    };

    dynamic_bitset() : m_size(0) {}
    explicit dynamic_bitset(const ::std::size_t size) : m_size(size), m_bits(::tools::ceil(size, W), 0) {}
    explicit dynamic_bitset(const ::std::string& str) : m_size(str.size()), m_bits(::tools::ceil(str.size(), W), 0) {
      for (::std::size_t i = 0; i < str.size(); ++i) {
        const auto c = str[str.size() - 1 - i];
        assert(c == '0' || c == '1');
        if (c == '1') {
          this->m_bits[i / W] |= UINT64_C(1) << (i % W);
        }
      }
    }

    ::tools::dynamic_bitset& operator&=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] &= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator|=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] |= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator^=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] ^= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator<<=(const ::std::size_t pos) {
      const ::std::size_t diff = pos / W;
      if (diff < this->m_bits.size()) {
        if (pos % W > 0) {
          for (::std::size_t i = this->m_bits.size() - diff; i --> 0;) {
            this->m_bits[i] <<= pos % W;
            if (i > 0) {
              this->m_bits[i] |= this->m_bits[i - 1] >> (W - pos % W);
            }
          }
        }
        if (diff > 0) {
          for (::std::size_t i = this->m_bits.size() - diff; i --> 0;) {
            this->m_bits[i + diff] = this->m_bits[i];
          }
          ::std::fill(this->m_bits.begin(), ::std::next(this->m_bits.begin(), diff), 0);
        }
        if (this->m_size % W > 0) {
          this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
        }
      } else {
        ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator>>=(const ::std::size_t pos) {
      const ::std::size_t diff = pos / W;
      if (diff < this->m_bits.size()) {
        if (pos % W > 0) {
          for (::std::size_t i = diff; i < this->m_bits.size(); ++i) {
            this->m_bits[i] >>= pos % W;
            if (i + 1 < this->m_bits.size()) {
              this->m_bits[i] |= this->m_bits[i + 1] << (W - pos % W);
            }
          }
        }
        if (diff > 0) {
          for (::std::size_t i = diff; i < this->m_bits.size(); ++i) {
            this->m_bits[i - diff] = this->m_bits[i];
          }
          ::std::fill(::std::next(this->m_bits.begin(), this->m_bits.size() - diff), this->m_bits.end(), 0);
        }
      } else {
        ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      }
      return *this;
    }
    ::tools::dynamic_bitset& set() {
      ::std::fill(this->m_bits.begin(), this->m_bits.end(), ::std::numeric_limits<::std::uint64_t>::max());
      if (this->m_size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
      }
      return *this;
    }
    ::tools::dynamic_bitset& set(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] |= UINT64_C(1) << (pos % W);
      return *this;
    }
    ::tools::dynamic_bitset& set(const ::std::size_t pos, const bool val) {
      return val ? this->set(pos) : this->reset(pos);
    }
    ::tools::dynamic_bitset& reset() {
      ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      return *this;
    }
    ::tools::dynamic_bitset& reset(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] &= ~(UINT64_C(1) << (pos % W));
      return *this;
    }
    ::tools::dynamic_bitset operator~() const {
      return ::tools::dynamic_bitset(*this).flip();
    }
    ::tools::dynamic_bitset& flip() {
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] = ~this->m_bits[i];
      }
      if (this->m_size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
      }
      return *this;
    }
    ::tools::dynamic_bitset& flip(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] ^= UINT64_C(1) << (pos % W);
      return *this;
    }
    reference operator[](const ::std::size_t pos) {
      return reference(this, pos);
    }
    bool operator[](const ::std::size_t pos) const {
      return this->test(pos);
    }
    ::std::size_t count() const {
      ::std::size_t result = 0;
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        result += ::std::popcount(this->m_bits[i]);
      }
      return result;
    }
    ::std::size_t size() const {
      return this->m_size;
    }
    bool test(const ::std::size_t pos) const {
      assert(pos < this->m_size);
      return (this->m_bits[pos / W] >> (pos % W)) & 1;
    }
    bool all() const {
      if (this->m_size % W > 0) {
        for (::std::size_t i = 0; i + 1 < this->m_bits.size(); ++i) {
          if (this->m_bits[i] != ::std::numeric_limits<::std::uint64_t>::max()) {
            return false;
          }
        }
        return this->m_bits.back() == (UINT64_C(1) << (this->m_size % W)) - 1;
      } else {
        for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
          if (this->m_bits[i] != ::std::numeric_limits<::std::uint64_t>::max()) {
            return false;
          }
        }
        return true;
      }
    }
    bool any() const {
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        if (this->m_bits[i] != 0) {
          return true;
        }
      }
      return false;
    }
    bool none() const {
      return !this->any();
    }
    ::std::string to_string() const {
      ::std::ostringstream oss;
      oss << *this;
      return oss.str();
    }
    friend bool operator==(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return lhs.m_size == rhs.m_size && lhs.m_bits == rhs.m_bits;
    }
    friend bool operator!=(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return !(lhs == rhs);
    }
    ::tools::dynamic_bitset operator<<(const ::std::size_t pos) const {
      return ::tools::dynamic_bitset(*this) <<= pos;
    }
    ::tools::dynamic_bitset operator>>(const ::std::size_t pos) const {
      return ::tools::dynamic_bitset(*this) >>= pos;
    }
    friend ::tools::dynamic_bitset operator&(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) &= rhs;
    }
    friend ::tools::dynamic_bitset operator|(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) |= rhs;
    }
    friend ::tools::dynamic_bitset operator^(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) ^= rhs;
    }
    friend ::std::istream& operator>>(::std::istream& is, ::tools::dynamic_bitset& self) {
      ::std::string s;
      is >> s;
      self = ::tools::dynamic_bitset(s);
      return is;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::dynamic_bitset& self) {
      for (::std::size_t i = self.m_bits.size(); i --> 0;) {
        for (::std::size_t j = i + 1 < self.m_bits.size() ? W : (self.m_size - 1) % W + 1; j --> 0;) {
          os << ((self.m_bits[i] >> j) & 1);
        }
      }
      return os;
    }
    bool empty() const {
      return this->m_size == 0;
    }
    void resize(const ::std::size_t size) {
      this->m_size = size;
      this->m_bits.resize(::tools::ceil(size, W));
      if (size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (size % W)) - 1;
      }
    }
    void shrink_to_fit() {
      this->m_bits.shrink_to_fit();
    }
  private:
    ::std::size_t Find_first(const ::std::size_t offset) const {
      for (::std::size_t i = offset; i < this->m_bits.size(); ++i) {
        if (this->m_bits[i] > 0) {
          return i * W + ::std::countr_zero(this->m_bits[i]);
        }
      }
      return this->m_size;
    }
  public:
    ::std::size_t Find_first() const {
      return this->Find_first(0);
    }
    ::std::size_t Find_next(const ::std::size_t pos) const {
      assert(pos < this->m_size);

      if (pos % W == W - 1) return this->Find_first((pos + 1) / W);
      if (const auto x = this->m_bits[pos / W] >> (pos % W + 1); x > 0) return pos + ::std::countr_zero(x) + 1;
      return this->Find_first(pos / W + 1);
    }
  };
}

#endif

#line 1 "tools/dynamic_bitset.hpp"



#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <limits>
#include <sstream>
#include <string>
#include <vector>
#line 1 "tools/ceil.hpp"



#line 5 "tools/ceil.hpp"
#include <type_traits>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 16 "tools/dynamic_bitset.hpp"

namespace tools {
  class dynamic_bitset {
    constexpr static ::std::size_t W = ::std::numeric_limits<::std::uint64_t>::digits;
    ::std::size_t m_size;
    ::std::vector<::std::uint64_t> m_bits;

  public:
    class reference {
      friend class ::tools::dynamic_bitset;

      ::tools::dynamic_bitset *m_parent;
      ::std::size_t m_pos;

      reference(::tools::dynamic_bitset * const parent, const ::std::size_t pos) : m_parent(parent), m_pos(pos) {
      }

    public:
      reference(const reference&) = default;
      reference& operator=(const bool x) {
        this->m_parent->set(this->m_pos, x);
        return *this;
      }
      reference& operator=(const reference& other) {
        return *this = static_cast<bool>(other);
      }
      bool operator~() const {
        return !static_cast<bool>(*this);
      }
      operator bool() const {
        return this->m_parent->test(this->m_pos);
      }
      reference& flip() {
        this->m_parent->flip(this->m_pos);
        return *this;
      }
    };

    dynamic_bitset() : m_size(0) {}
    explicit dynamic_bitset(const ::std::size_t size) : m_size(size), m_bits(::tools::ceil(size, W), 0) {}
    explicit dynamic_bitset(const ::std::string& str) : m_size(str.size()), m_bits(::tools::ceil(str.size(), W), 0) {
      for (::std::size_t i = 0; i < str.size(); ++i) {
        const auto c = str[str.size() - 1 - i];
        assert(c == '0' || c == '1');
        if (c == '1') {
          this->m_bits[i / W] |= UINT64_C(1) << (i % W);
        }
      }
    }

    ::tools::dynamic_bitset& operator&=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] &= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator|=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] |= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator^=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] ^= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator<<=(const ::std::size_t pos) {
      const ::std::size_t diff = pos / W;
      if (diff < this->m_bits.size()) {
        if (pos % W > 0) {
          for (::std::size_t i = this->m_bits.size() - diff; i --> 0;) {
            this->m_bits[i] <<= pos % W;
            if (i > 0) {
              this->m_bits[i] |= this->m_bits[i - 1] >> (W - pos % W);
            }
          }
        }
        if (diff > 0) {
          for (::std::size_t i = this->m_bits.size() - diff; i --> 0;) {
            this->m_bits[i + diff] = this->m_bits[i];
          }
          ::std::fill(this->m_bits.begin(), ::std::next(this->m_bits.begin(), diff), 0);
        }
        if (this->m_size % W > 0) {
          this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
        }
      } else {
        ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator>>=(const ::std::size_t pos) {
      const ::std::size_t diff = pos / W;
      if (diff < this->m_bits.size()) {
        if (pos % W > 0) {
          for (::std::size_t i = diff; i < this->m_bits.size(); ++i) {
            this->m_bits[i] >>= pos % W;
            if (i + 1 < this->m_bits.size()) {
              this->m_bits[i] |= this->m_bits[i + 1] << (W - pos % W);
            }
          }
        }
        if (diff > 0) {
          for (::std::size_t i = diff; i < this->m_bits.size(); ++i) {
            this->m_bits[i - diff] = this->m_bits[i];
          }
          ::std::fill(::std::next(this->m_bits.begin(), this->m_bits.size() - diff), this->m_bits.end(), 0);
        }
      } else {
        ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      }
      return *this;
    }
    ::tools::dynamic_bitset& set() {
      ::std::fill(this->m_bits.begin(), this->m_bits.end(), ::std::numeric_limits<::std::uint64_t>::max());
      if (this->m_size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
      }
      return *this;
    }
    ::tools::dynamic_bitset& set(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] |= UINT64_C(1) << (pos % W);
      return *this;
    }
    ::tools::dynamic_bitset& set(const ::std::size_t pos, const bool val) {
      return val ? this->set(pos) : this->reset(pos);
    }
    ::tools::dynamic_bitset& reset() {
      ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      return *this;
    }
    ::tools::dynamic_bitset& reset(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] &= ~(UINT64_C(1) << (pos % W));
      return *this;
    }
    ::tools::dynamic_bitset operator~() const {
      return ::tools::dynamic_bitset(*this).flip();
    }
    ::tools::dynamic_bitset& flip() {
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] = ~this->m_bits[i];
      }
      if (this->m_size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
      }
      return *this;
    }
    ::tools::dynamic_bitset& flip(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] ^= UINT64_C(1) << (pos % W);
      return *this;
    }
    reference operator[](const ::std::size_t pos) {
      return reference(this, pos);
    }
    bool operator[](const ::std::size_t pos) const {
      return this->test(pos);
    }
    ::std::size_t count() const {
      ::std::size_t result = 0;
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        result += ::std::popcount(this->m_bits[i]);
      }
      return result;
    }
    ::std::size_t size() const {
      return this->m_size;
    }
    bool test(const ::std::size_t pos) const {
      assert(pos < this->m_size);
      return (this->m_bits[pos / W] >> (pos % W)) & 1;
    }
    bool all() const {
      if (this->m_size % W > 0) {
        for (::std::size_t i = 0; i + 1 < this->m_bits.size(); ++i) {
          if (this->m_bits[i] != ::std::numeric_limits<::std::uint64_t>::max()) {
            return false;
          }
        }
        return this->m_bits.back() == (UINT64_C(1) << (this->m_size % W)) - 1;
      } else {
        for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
          if (this->m_bits[i] != ::std::numeric_limits<::std::uint64_t>::max()) {
            return false;
          }
        }
        return true;
      }
    }
    bool any() const {
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        if (this->m_bits[i] != 0) {
          return true;
        }
      }
      return false;
    }
    bool none() const {
      return !this->any();
    }
    ::std::string to_string() const {
      ::std::ostringstream oss;
      oss << *this;
      return oss.str();
    }
    friend bool operator==(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return lhs.m_size == rhs.m_size && lhs.m_bits == rhs.m_bits;
    }
    friend bool operator!=(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return !(lhs == rhs);
    }
    ::tools::dynamic_bitset operator<<(const ::std::size_t pos) const {
      return ::tools::dynamic_bitset(*this) <<= pos;
    }
    ::tools::dynamic_bitset operator>>(const ::std::size_t pos) const {
      return ::tools::dynamic_bitset(*this) >>= pos;
    }
    friend ::tools::dynamic_bitset operator&(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) &= rhs;
    }
    friend ::tools::dynamic_bitset operator|(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) |= rhs;
    }
    friend ::tools::dynamic_bitset operator^(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) ^= rhs;
    }
    friend ::std::istream& operator>>(::std::istream& is, ::tools::dynamic_bitset& self) {
      ::std::string s;
      is >> s;
      self = ::tools::dynamic_bitset(s);
      return is;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::dynamic_bitset& self) {
      for (::std::size_t i = self.m_bits.size(); i --> 0;) {
        for (::std::size_t j = i + 1 < self.m_bits.size() ? W : (self.m_size - 1) % W + 1; j --> 0;) {
          os << ((self.m_bits[i] >> j) & 1);
        }
      }
      return os;
    }
    bool empty() const {
      return this->m_size == 0;
    }
    void resize(const ::std::size_t size) {
      this->m_size = size;
      this->m_bits.resize(::tools::ceil(size, W));
      if (size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (size % W)) - 1;
      }
    }
    void shrink_to_fit() {
      this->m_bits.shrink_to_fit();
    }
  private:
    ::std::size_t Find_first(const ::std::size_t offset) const {
      for (::std::size_t i = offset; i < this->m_bits.size(); ++i) {
        if (this->m_bits[i] > 0) {
          return i * W + ::std::countr_zero(this->m_bits[i]);
        }
      }
      return this->m_size;
    }
  public:
    ::std::size_t Find_first() const {
      return this->Find_first(0);
    }
    ::std::size_t Find_next(const ::std::size_t pos) const {
      assert(pos < this->m_size);

      if (pos % W == W - 1) return this->Find_first((pos + 1) / W);
      if (const auto x = this->m_bits[pos / W] >> (pos % W + 1); x > 0) return pos + ::std::countr_zero(x) + 1;
      return this->Find_first(pos / W + 1);
    }
  };
}

Back to top page