dynamic_bitset.hpp

SECTIONData Structure INCLUDEnoya/dynamic_bitset.hpp

提供运行时长度的位集及位运算、移位和查找置位；适合状态长度不在编译期确定的 bitset 优化。

Complexity: Time: O(n / 64) for whole-bitset operations; O(1) bit access. Space: O(n / 64).

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n / 64) for whole-bitset operations; O(1) bit access.
/// Space: O(n / 64).

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

namespace noya {

/// @brief Resizable packed bitset with bitwise operations, shifts, population
/// count, and efficient iteration over set bits.
struct dynamic_bitset {
  using word_type = std::uint64_t;
  static constexpr std::size_t W = 64;

  std::size_t sz_ = 0;
  std::vector<word_type> a;

  dynamic_bitset() = default;
  explicit dynamic_bitset(std::size_t siz, bool val = false)
      : sz_(siz), a(word_count(siz), val ? ~word_type{} : 0) {
    trim();
  }

  std::size_t size() const { return sz_; }
  bool empty() const { return sz_ == 0; }

  bool test(std::size_t pos) const {
    assert(pos < sz_);
    return (a[pos / W] >> (pos % W)) & 1;
  }

  bool operator[](std::size_t pos) const { return test(pos); }

  dynamic_bitset &set(std::size_t pos, bool val = true) {
    assert(pos < sz_);
    word_type msk = word_type(1) << (pos % W);
    if (val) {
      a[pos / W] |= msk;
    } else {
      a[pos / W] &= ~msk;
    }
    return *this;
  }

  dynamic_bitset &reset(std::size_t pos) { return set(pos, false); }

  dynamic_bitset &flip(std::size_t pos) {
    assert(pos < sz_);
    a[pos / W] ^= word_type(1) << (pos % W);
    return *this;
  }

  dynamic_bitset &set() {
    std::fill(a.begin(), a.end(), ~word_type{});
    trim();
    return *this;
  }

  dynamic_bitset &reset() {
    std::fill(a.begin(), a.end(), word_type{});
    return *this;
  }

  dynamic_bitset &flip() {
    for (word_type &w : a) {
      w = ~w;
    }
    trim();
    return *this;
  }

  std::size_t count() const {
    std::size_t res = 0;
    for (word_type w : a) {
      res += std::popcount(w);
    }
    return res;
  }

  bool any() const {
    return std::any_of(a.begin(), a.end(), [](word_type w) { return w != 0; });
  }

  bool none() const { return !any(); }

  /// @brief Return the first set position at least position, or size() if no
  /// such position exists.
  std::size_t find_next(std::size_t pos) const {
    if (pos >= sz_) {
      return sz_;
    }
    std::size_t idx = pos / W;
    word_type w = a[idx] & (~word_type{} << (pos % W));
    if (w != 0) {
      return std::min(sz_, idx * W + std::size_t(std::countr_zero(w)));
    }
    for (idx++; idx < a.size(); idx++) {
      if (a[idx] != 0) {
        return std::min(sz_, idx * W + std::size_t(std::countr_zero(a[idx])));
      }
    }
    return sz_;
  }

  std::size_t find_first() const { return find_next(0); }

  dynamic_bitset &operator&=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] &= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator|=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] |= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator^=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] ^= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator<<=(std::size_t k) {
    if (k >= sz_) {
      return reset();
    }
    std::size_t blk = k / W;
    int rem = int(k % W);
    for (std::size_t i = a.size(); i-- > 0;) {
      word_type val = 0;
      if (i >= blk) {
        val = a[i - blk] << rem;
        if (rem != 0 && i > blk) {
          val |= a[i - blk - 1] >> (W - rem);
        }
      }
      a[i] = val;
    }
    trim();
    return *this;
  }

  dynamic_bitset &operator>>=(std::size_t k) {
    if (k >= sz_) {
      return reset();
    }
    std::size_t blk = k / W;
    int rem = int(k % W);
    for (std::size_t i = 0; i < a.size(); i++) {
      word_type val = 0;
      if (i + blk < a.size()) {
        val = a[i + blk] >> rem;
        if (rem != 0 && i + blk + 1 < a.size()) {
          val |= a[i + blk + 1] << (W - rem);
        }
      }
      a[i] = val;
    }
    return *this;
  }

  friend dynamic_bitset operator&(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr &= b;
  }
  friend dynamic_bitset operator|(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr |= b;
  }
  friend dynamic_bitset operator^(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr ^= b;
  }
  friend dynamic_bitset operator<<(dynamic_bitset val, std::size_t k) {
    return val <<= k;
  }
  friend dynamic_bitset operator>>(dynamic_bitset val, std::size_t k) {
    return val >>= k;
  }
  friend dynamic_bitset operator~(dynamic_bitset val) { return val.flip(); }

  friend bool operator==(const dynamic_bitset &,
                         const dynamic_bitset &) = default;

private:
  static std::size_t word_count(std::size_t siz) { return (siz + W - 1) / W; }

  void trim() {
    if (!a.empty() && sz_ % W != 0) {
      a.back() &= (word_type(1) << (sz_ % W)) - word_type(1);
    }
  }

  void check_same_size(const dynamic_bitset &rhs) const {
    assert(sz_ == rhs.sz_);
  }
};

} // namespace noya

#ifndef NOYA_DYNAMIC_BITSET_HPP
#define NOYA_DYNAMIC_BITSET_HPP 1

/// @complexity Time: O(n / 64) for whole-bitset operations; O(1) bit access.
/// Space: O(n / 64).

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

namespace noya {

/// @brief Resizable packed bitset with bitwise operations, shifts, population
/// count, and efficient iteration over set bits.
struct dynamic_bitset {
  using word_type = std::uint64_t;
  static constexpr std::size_t W = 64;

  std::size_t sz_ = 0;
  std::vector<word_type> a;

  dynamic_bitset() = default;
  explicit dynamic_bitset(std::size_t siz, bool val = false)
      : sz_(siz), a(word_count(siz), val ? ~word_type{} : 0) {
    trim();
  }

  std::size_t size() const { return sz_; }
  bool empty() const { return sz_ == 0; }

  bool test(std::size_t pos) const {
    assert(pos < sz_);
    return (a[pos / W] >> (pos % W)) & 1;
  }

  bool operator[](std::size_t pos) const { return test(pos); }

  dynamic_bitset &set(std::size_t pos, bool val = true) {
    assert(pos < sz_);
    word_type msk = word_type(1) << (pos % W);
    if (val) {
      a[pos / W] |= msk;
    } else {
      a[pos / W] &= ~msk;
    }
    return *this;
  }

  dynamic_bitset &reset(std::size_t pos) { return set(pos, false); }

  dynamic_bitset &flip(std::size_t pos) {
    assert(pos < sz_);
    a[pos / W] ^= word_type(1) << (pos % W);
    return *this;
  }

  dynamic_bitset &set() {
    std::fill(a.begin(), a.end(), ~word_type{});
    trim();
    return *this;
  }

  dynamic_bitset &reset() {
    std::fill(a.begin(), a.end(), word_type{});
    return *this;
  }

  dynamic_bitset &flip() {
    for (word_type &w : a) {
      w = ~w;
    }
    trim();
    return *this;
  }

  std::size_t count() const {
    std::size_t res = 0;
    for (word_type w : a) {
      res += std::popcount(w);
    }
    return res;
  }

  bool any() const {
    return std::any_of(a.begin(), a.end(), [](word_type w) { return w != 0; });
  }

  bool none() const { return !any(); }

  /// @brief Return the first set position at least position, or size() if no
  /// such position exists.
  std::size_t find_next(std::size_t pos) const {
    if (pos >= sz_) {
      return sz_;
    }
    std::size_t idx = pos / W;
    word_type w = a[idx] & (~word_type{} << (pos % W));
    if (w != 0) {
      return std::min(sz_, idx * W + std::size_t(std::countr_zero(w)));
    }
    for (idx++; idx < a.size(); idx++) {
      if (a[idx] != 0) {
        return std::min(sz_, idx * W + std::size_t(std::countr_zero(a[idx])));
      }
    }
    return sz_;
  }

  std::size_t find_first() const { return find_next(0); }

  dynamic_bitset &operator&=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] &= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator|=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] |= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator^=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] ^= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator<<=(std::size_t k) {
    if (k >= sz_) {
      return reset();
    }
    std::size_t blk = k / W;
    int rem = int(k % W);
    for (std::size_t i = a.size(); i-- > 0;) {
      word_type val = 0;
      if (i >= blk) {
        val = a[i - blk] << rem;
        if (rem != 0 && i > blk) {
          val |= a[i - blk - 1] >> (W - rem);
        }
      }
      a[i] = val;
    }
    trim();
    return *this;
  }

  dynamic_bitset &operator>>=(std::size_t k) {
    if (k >= sz_) {
      return reset();
    }
    std::size_t blk = k / W;
    int rem = int(k % W);
    for (std::size_t i = 0; i < a.size(); i++) {
      word_type val = 0;
      if (i + blk < a.size()) {
        val = a[i + blk] >> rem;
        if (rem != 0 && i + blk + 1 < a.size()) {
          val |= a[i + blk + 1] << (W - rem);
        }
      }
      a[i] = val;
    }
    return *this;
  }

  friend dynamic_bitset operator&(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr &= b;
  }
  friend dynamic_bitset operator|(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr |= b;
  }
  friend dynamic_bitset operator^(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr ^= b;
  }
  friend dynamic_bitset operator<<(dynamic_bitset val, std::size_t k) {
    return val <<= k;
  }
  friend dynamic_bitset operator>>(dynamic_bitset val, std::size_t k) {
    return val >>= k;
  }
  friend dynamic_bitset operator~(dynamic_bitset val) { return val.flip(); }

  friend bool operator==(const dynamic_bitset &,
                         const dynamic_bitset &) = default;

private:
  static std::size_t word_count(std::size_t siz) { return (siz + W - 1) / W; }

  void trim() {
    if (!a.empty() && sz_ % W != 0) {
      a.back() &= (word_type(1) << (sz_ % W)) - word_type(1);
    }
  }

  void check_same_size(const dynamic_bitset &rhs) const {
    assert(sz_ == rhs.sz_);
  }
};

} // namespace noya

#endif // NOYA_DYNAMIC_BITSET_HPP

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

/// @complexity Time: O(n / 64) for whole-bitset operations; O(1) bit access.
/// Space: O(n / 64).

namespace noya {

/// @brief Resizable packed bitset with bitwise operations, shifts, population
/// count, and efficient iteration over set bits.
struct dynamic_bitset {
  using word_type = std::uint64_t;
  static constexpr std::size_t W = 64;

  std::size_t sz_ = 0;
  std::vector<word_type> a;

  dynamic_bitset() = default;
  explicit dynamic_bitset(std::size_t siz, bool val = false)
      : sz_(siz), a(word_count(siz), val ? ~word_type{} : 0) {
    trim();
  }

  std::size_t size() const { return sz_; }
  bool empty() const { return sz_ == 0; }

  bool test(std::size_t pos) const {
    assert(pos < sz_);
    return (a[pos / W] >> (pos % W)) & 1;
  }

  bool operator[](std::size_t pos) const { return test(pos); }

  dynamic_bitset &set(std::size_t pos, bool val = true) {
    assert(pos < sz_);
    word_type msk = word_type(1) << (pos % W);
    if (val) {
      a[pos / W] |= msk;
    } else {
      a[pos / W] &= ~msk;
    }
    return *this;
  }

  dynamic_bitset &reset(std::size_t pos) { return set(pos, false); }

  dynamic_bitset &flip(std::size_t pos) {
    assert(pos < sz_);
    a[pos / W] ^= word_type(1) << (pos % W);
    return *this;
  }

  dynamic_bitset &set() {
    std::fill(a.begin(), a.end(), ~word_type{});
    trim();
    return *this;
  }

  dynamic_bitset &reset() {
    std::fill(a.begin(), a.end(), word_type{});
    return *this;
  }

  dynamic_bitset &flip() {
    for (word_type &w : a) {
      w = ~w;
    }
    trim();
    return *this;
  }

  std::size_t count() const {
    std::size_t res = 0;
    for (word_type w : a) {
      res += std::popcount(w);
    }
    return res;
  }

  bool any() const {
    return std::any_of(a.begin(), a.end(), [](word_type w) { return w != 0; });
  }

  bool none() const { return !any(); }

  /// @brief Return the first set position at least position, or size() if no
  /// such position exists.
  std::size_t find_next(std::size_t pos) const {
    if (pos >= sz_) {
      return sz_;
    }
    std::size_t idx = pos / W;
    word_type w = a[idx] & (~word_type{} << (pos % W));
    if (w != 0) {
      return std::min(sz_, idx * W + std::size_t(std::countr_zero(w)));
    }
    for (idx++; idx < a.size(); idx++) {
      if (a[idx] != 0) {
        return std::min(sz_, idx * W + std::size_t(std::countr_zero(a[idx])));
      }
    }
    return sz_;
  }

  std::size_t find_first() const { return find_next(0); }

  dynamic_bitset &operator&=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] &= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator|=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] |= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator^=(const dynamic_bitset &rhs) {
    check_same_size(rhs);
    for (std::size_t i = 0; i < a.size(); i++) {
      a[i] ^= rhs.a[i];
    }
    return *this;
  }

  dynamic_bitset &operator<<=(std::size_t k) {
    if (k >= sz_) {
      return reset();
    }
    std::size_t blk = k / W;
    int rem = int(k % W);
    for (std::size_t i = a.size(); i-- > 0;) {
      word_type val = 0;
      if (i >= blk) {
        val = a[i - blk] << rem;
        if (rem != 0 && i > blk) {
          val |= a[i - blk - 1] >> (W - rem);
        }
      }
      a[i] = val;
    }
    trim();
    return *this;
  }

  dynamic_bitset &operator>>=(std::size_t k) {
    if (k >= sz_) {
      return reset();
    }
    std::size_t blk = k / W;
    int rem = int(k % W);
    for (std::size_t i = 0; i < a.size(); i++) {
      word_type val = 0;
      if (i + blk < a.size()) {
        val = a[i + blk] >> rem;
        if (rem != 0 && i + blk + 1 < a.size()) {
          val |= a[i + blk + 1] << (W - rem);
        }
      }
      a[i] = val;
    }
    return *this;
  }

  friend dynamic_bitset operator&(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr &= b;
  }
  friend dynamic_bitset operator|(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr |= b;
  }
  friend dynamic_bitset operator^(dynamic_bitset arr, const dynamic_bitset &b) {
    return arr ^= b;
  }
  friend dynamic_bitset operator<<(dynamic_bitset val, std::size_t k) {
    return val <<= k;
  }
  friend dynamic_bitset operator>>(dynamic_bitset val, std::size_t k) {
    return val >>= k;
  }
  friend dynamic_bitset operator~(dynamic_bitset val) { return val.flip(); }

  friend bool operator==(const dynamic_bitset &,
                         const dynamic_bitset &) = default;

private:
  static std::size_t word_count(std::size_t siz) { return (siz + W - 1) / W; }

  void trim() {
    if (!a.empty() && sz_ % W != 0) {
      a.back() &= (word_type(1) << (sz_ % W)) - word_type(1);
    }
  }

  void check_same_size(const dynamic_bitset &rhs) const {
    assert(sz_ == rhs.sz_);
  }
};

} // namespace noya