Dynamic Bitset

data_structure/dynamic_bitset.hpp · GitHub で見る

共通ページ

長さを実行時に指定するビット集合です。64 bit ごとの論理演算・シフト、区間の更新、立っているビットの列挙、集合間の個数計算を扱います。添字 i が整数としての \(2^i\) のビットに対応します。

#include "lib/data_structure/dynamic_bitset.hpp"
#include <cassert>
#include <vector>

int main() {
	DynamicBitset a("100101"), b("001111");
	assert(a.size() == 6 && a[0] && a[2] && a[5]);
	assert(a.count() == 3 && a.rank(3) == 2);
	assert(a.count_and(b) == 2);
	assert((a & b).to_string() == "000101");
	assert((a - b).to_string() == "100000");
	assert(a.find_first() == 0 && a.find_next(0) == 2);
	assert(a.find_prev(a.size()) == 5 && a.select(3) == a.size());

	std::vector<int> positions;
	a.for_each([&](int i) { positions.push_back(i); });
	assert((positions == std::vector<int>{0, 2, 5}));
	a.set_range(1, 4);
	assert(a.to_string() == "101111");
	a[5] = false;
	assert(a.to_string() == "001111");
}

DynamicBitset はテンプレートではありません。長さと添字は int で、長さは 0 <= n <= INT_MAX、要素の添字は 0 <= i < size() とします。区間はすべて半開区間 [l,r) で、0 <= l <= r <= size() が必要です。空区間の更新は何もせず、個数は 0、切り出した列は空になります。

文字列との変換では通常の二進表記と同様に、右端が添字 0 です。例えば "100101" の true の位置は 0・2・5 です。文字列の先頭の 0 も列長に含みます。空文字列は長さ 0 に対応し、'0'・'1' 以外を含む入力には std::invalid_argument を投げます。

構築・サイズの操作	内容・返り値
DynamicBitset()	長さ 0 の列を作る
DynamicBitset(int n, bool value = false)	長さ n、全要素が value の列を作る
DynamicBitset(std::string_view text)	二進表記をコピーして列を作る
DynamicBitset::from_words(int n, std::span<const std::uint64_t> words)	64 bit 単位の配列をコピーして列を返す
size() / empty()	長さを int / 長さが 0 かを bool で返す
resize(int n, bool value = false)	長さを変更。既存部分を保ち、追加部分を value にする。void
reserve(int n)	n bit 分の領域を予約。長さは変えない。void
push_back(bool value) / pop_back()	添字 size() に追加 / 最大の添字のビットを削除。void。削除には非空が必要
clear() / swap(other)	長さを 0 にする（予約領域は保持）/ 2 つの列を交換。void
words()	内部配列への std::span<const std::uint64_t>
to_string()	長さを保った二進表記を std::string で返す

from_words の配列長は正確に \(\lceil n/64\rceil\) とします。words[0] が添字 0～63、words[1] が 64～127 に対応します。最後のワードのうち長さの外にある上位ビットは読み捨てます。words() の配列長も同じで、外側のビットは常に 0 です。この参照を通した変更はできません。

一点・全体・区間の操作	内容・返り値
test(int i) / const の operator[](int i)	ビット値を bool で返す
非 const の operator[](int i)	bool に変換できる reference プロキシ。bits[i] = value、プロキシ同士の代入、bits[i].flip() が可能
set(int i, bool value = true) / reset(int i) / flip(int i)	一点を代入 / false にする / 反転
set_all(bool value = true) / reset_all() / flip_all()	全体を代入 / false にする / 反転
set_range(int l, int r, bool value = true) / reset_range(l,r) / flip_range(l,r)	区間を代入 / false にする / 反転
count() / count(int l, int r) / rank(int r)	全体 / [l,r) / [0,r) の true の個数を int で返す
any() / none() / all()	true が存在する / 存在しない / 全要素が true かを bool で返す

set・reset・flip とその全体版・区間版は自身への DynamicBitset& を返します。空の列では count() == 0、any() == false、none() == true、all() == true です。rank は区間個数の別表記であり、事前計算した索引を保持する操作ではありません。

テンプレートの all マクロは引数の有無で分岐する定義を使ってください。sort(all(v)) と bits.all() をそのまま併用できます。C++20 以降の定義例は利用者テンプレートとの併用を参照してください。ヘッダーは利用者のマクロを変更しません。

集合間の演算	内容・返り値
a & b / a \| b / a ^ b / a - b	共通部分 / 和集合 / 対称差 / 差集合を DynamicBitset で返す
a &= b / a \|= b / a ^= b / a -= b	同じ演算で a を更新し、DynamicBitset& を返す
~a	長さの内側だけを反転した列を返す
count_and(other) / count_or(other) / count_xor(other) / count_and_not(other)	各演算の結果の true の個数を、結果の列を作らず int で返す
intersection_parity(other)	共通する true の個数が奇数かを bool で返す。GF(2) 上の内積
intersects(other)	共通する true が存在するかを bool で返す
is_subset_of(other) / is_proper_subset_of(other)	自身が部分集合 / 真部分集合かを bool で返す
compare(other)	符号なし整数とみなした大小を int の -1・0・1 で返す
operator== / operator!=	列長と全ビットが等しいか / 異なるかを bool で返す

a & b の長さは min(a.size(),b.size())、a | b・a ^ b の長さは max(a.size(),b.size()) です。添字 0 側をそろえ、短い側に存在しないビットを false として計算します。文字列表現では短い側を左側の 0 で埋めることに相当します。代入演算子の &=・|=・^= も同じ規則で自身の長さを変更します。count_and・count_or・count_xor は、この長さの規則による結果の個数を、列を作らずに返します。

#include "lib/data_structure/dynamic_bitset.hpp"
#include <cassert>

int main() {
	DynamicBitset a("101"), b("11011");
	assert((a | b).to_string() == "11111");
	assert((a ^ b).to_string() == "11110");
	assert((a & b).to_string() == "001");
	assert(a.count_or(b) == 5 && a.count_xor(b) == 4 && a.count_and(b) == 1);
	a |= b;
	assert(a.size() == 5 && a.to_string() == "11111");
	a &= DynamicBitset("10");
	assert(a.size() == 2 && a.to_string() == "10");
	assert((b & DynamicBitset{}).empty());
}

差集合の a - b・a -= b、count_and_not、intersection_parity、intersects、部分集合判定、compare は列長が一致する必要があります。自身との演算も可能です。長さが一致するとき a - b と count_and_not(b) は a & ~b に対応します。compare は大きい添字のビットから比較するため、集合の包含関係とは別の順序です。等値比較は異なる長さも受け付け、末尾がすべて 0 でも長さが違えば等しくありません。

検索・列挙	内容・返り値
find_first(bool value = true) / find_last(bool value = true)	value と等しい最初 / 最後のビットの添字を int で返す
find_next(int pos, bool value = true)	pos より大きい添字から最初の一致を返す。-1 <= pos < size()
find_prev(int pos, bool value = true)	pos より小さい添字から最後の一致を返す。0 <= pos <= size()
select(int k, bool value = true)	添字の昇順で 0 始まり k 番目の一致を返す。k >= 0
for_each(F&& callback) / for_each(int l, int r, F&& callback)	全体 / 区間内の true の添字を昇順に callback(int) へ渡す。void

検索結果がなければ、前方向・後方向ともに size() を返します。select も該当個数が k 以下なら size() です。空の列ではすべての検索が 0 を返します。find_next(-1) は find_first()、find_prev(size()) は find_last() に対応します。列挙中はコールバックから同じ列を変更しないでください。

シフト・組み換え	内容・返り値
a << shift / a >> shift	大きい / 小さい添字へシフトした列を返す。空く部分は false
a <<= shift / a >>= shift	シフトして自身を更新し、DynamicBitset& を返す
or_shift_left(shift) / or_shift_right(shift)	更新前の列を使って a \|= a << shift / a \|= a >> shift を行い、DynamicBitset& を返す
slice(int l, int r)	[l,r) を添字 0 から始まる長さ r-l の列として返す
append(const DynamicBitset& other)	other を大きい添字側へ連結する。自身の連結も可能。void
copy_range(int dst, const DynamicBitset& source, int l, int r)	source[l,r) を自身の [dst,dst+r-l) へ上書き。長さを変えず、自己参照と重複にも対応。void
reverse()	添字 i の値を size()-1-i へ移し、DynamicBitset& を返す
rotate_left(shift) / rotate_right(shift)	大きい / 小さい添字へ巡回移動し、DynamicBitset& を返す

shift の型は std::size_t です。通常のシフトは列長を変えず、shift >= size() なら全ビットが false になります。or_shift_left・or_shift_right は一時的な列を作らずに更新し、この場合は元の列を保ちます。巡回移動では非空の列に対して shift % size() を使い、空の列は何も変えません。

append 後の長さは INT_MAX 以下にしてください。copy_range の [l,r) は source の範囲、0 <= dst と r-l <= size()-dst は書き込み先の範囲です。重なった部分の読み込みには操作前の値を使います。

#include "lib/data_structure/dynamic_bitset.hpp"
#include <cassert>

int main() {
	DynamicBitset bits("1001");
	bits.rotate_left(1);
	assert(bits.to_string() == "0011");
	bits.or_shift_left(2);
	assert(bits.to_string() == "1111");
	bits.append(bits);
	assert(bits.to_string() == "11111111");
	bits.resize(10);
	assert(bits.to_string() == "0011111111");
	auto low = bits.slice(0, 4);
	assert(low.to_string() == "1111");
	bits.copy_range(2, bits, 0, 6);
	assert(bits.count() == 8);
}

コピーした列は独立しています。ムーブ後の移動元は長さ 0 になります。words() の span と要素のプロキシは内部領域を参照するため、領域の再確保・clear・代入・破棄後に使わないでください。長さを縮めた場合は、範囲外になった添字のプロキシも使えません。メモリ確保を伴う操作では標準コンテナの例外が発生することがあります。

演算前の長さを \(n\)、ワード数を \(W=\lceil n/64\rceil\) とします。相手の列がある場合は、その長さを \(m\)、ワード数を \(V=\lceil m/64\rceil\) とします。要素は \(W\) ワードに格納し、予約領域も含む保持空間は確保済みの容量に比例します。reserve や過去の長さによる余剰領域がなければ \(O(W)\) です。以下はワードの論理演算・popcount・ビット位置の検索を定数時間とする計算量です。

操作	時間・追加空間
長さを指定した構築・全体更新・全体個数・差集合・比較・検索・select	最悪 \(O(W)\) 時間。新しい列を返す演算は \(O(W)\) 追加空間、それ以外は \(O(1)\)
a & b / a &= b / count_and(b)	\(O(\min(W,V))\) 時間。a & b は \(O(\min(W,V))\) 追加空間、それ以外は \(O(1)\)
a \| b / a ^ b	\(O(\max(W,V))\) 時間・追加空間
a \|= b / a ^= b	最悪 \(O(\max(W,V))\) 時間・追加空間。再確保がなければ \(O(V)\) 時間・\(O(1)\) 追加空間
count_or(b) / count_xor(b)	\(O(\max(W,V))\) 時間・\(O(1)\) 追加空間
文字列からの構築・to_string	\(O(n)\) 時間・空間
一点の取得・更新、size・empty・words・swap	\(O(1)\) 時間・追加空間
区間の更新・個数・rank	対象区間に触れるワード数に比例する時間、\(O(1)\) 追加空間
for_each	対象ワード数と列挙数の合計に比例する時間、\(O(1)\) 追加空間
シフト・or_shift_left・or_shift_right・順序反転・巡回移動	\(O(W)\) 時間。追加空間は通常の破壊的シフト・シフトとの OR・順序反転が \(O(1)\)、コピーを返すシフトと巡回移動が \(O(W)\)
copy_range(dst,source,l,r)	対象ワード数に比例する時間、自己参照でも \(O(1)\) 追加空間
append(other)	元のワード数と追加するワード数の合計に対して最悪線形時間・追加空間。再確保がなければ追加ワード数に比例する時間、\(O(1)\) 追加空間
resize	再確保が発生するときは元のワード数と変更後のワード数の合計に対して最悪線形時間・追加空間
reserve	再確保が発生するときは予約するワード数に対して最悪線形時間・追加空間
slice(l,r)	\(O(\lceil(r-l)/64\rceil)\) 時間・追加空間

any・all・検索・比較は結果が決まった時点で走査を終えます。両方が空の演算・空区間・シフト量 0 などの何もしない場合は定数時間です。再確保のない resize は、追加・初期化するワード数に比例する時間で、縮小時は定数時間です。再確保のない reserve は定数時間です。push_back は償却 \(O(1)\)、pop_back は \(O(1)\) です。コピーは \(O(W)\)、ムーブ構築は \(O(1)\) で、代入には旧領域の解放も加わります。clear は定数時間です。

依存ライブラリ

• Bitset Word Operations

検証コード

• test/dynamic_bitset_matrix_product.test.cpp

コード

#ifndef DYNAMIC_BITSET_HPP
#define DYNAMIC_BITSET_HPP

#include "../components/bitset_ops.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <stdexcept>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

class [[nodiscard, gnu::warn_unused]] DynamicBitset {
	using Word = std::uint64_t;
	using Operation = bitset_ops_detail::Operation;
	std::vector<Word> data_;
	int n_ = 0;
	static std::size_t word_count(int n) { return (std::size_t(n) + 63) / 64; }
	static Word mask(int n) { return n == 64 ? ~Word(0) : (Word(1) << n) - 1; }
	void trim() { if (n_ & 63) data_.back() &= mask(n_ & 63); }
	void check([[maybe_unused]] int p) const { assert(0 <= p && p < n_); }
	void check_range([[maybe_unused]] int l, [[maybe_unused]] int r) const { assert(0 <= l && l <= r && r <= n_); }
	void check_size([[maybe_unused]] const DynamicBitset &other) const { assert(n_ == other.n_); }
	Word chosen(std::size_t i, bool value) const {
		Word x = value ? data_[i] : ~data_[i];
		if (!value && i + 1 == data_.size() && (n_ & 63)) x &= mask(n_ & 63);
		return x;
	}
	Word extract(int p, int length) const {
		std::size_t w = unsigned(p) / 64;
		int offset = p & 63;
		Word x = data_[w] >> offset;
		if (offset && length > 64 - offset) x |= data_[w + 1] << (64 - offset);
		return x & mask(length);
	}
	template <class F> void update_range(int l, int r, F apply) {
		check_range(l, r);
		if (l == r) return;
		std::size_t first = unsigned(l) / 64, last = unsigned(r - 1) / 64;
		Word left = ~Word(0) << (l & 63), right = mask(((r - 1) & 63) + 1);
		if (first == last) { apply(data_[first], left & right); return; }
		apply(data_[first], left);
		for (auto i = first + 1; i < last; ++i) apply(data_[i], ~Word(0));
		apply(data_[last], right);
	}
	template <Operation Op> int count_with(const DynamicBitset &other) const {
		if constexpr (Op == Operation::identity) return int(bitset_ops_detail::count<Op>(data_.data(), nullptr, data_.size()));
		if constexpr (Op == Operation::and_not) check_size(other);
		std::size_t common = std::min(data_.size(), other.data_.size());
		int result = 0;
		if (common >= 8) result = int(bitset_ops_detail::count<Op>(data_.data(), other.data_.data(), common));
		else for (std::size_t i = 0; i < common; ++i) result += std::popcount(bitset_ops_detail::combine<Op>(data_[i], other.data_[i]));
		if constexpr (Op == Operation::bit_or || Op == Operation::bit_xor) {
			const auto &tail = data_.size() > other.data_.size() ? data_ : other.data_;
			if (common < tail.size()) result += int(bitset_ops_detail::count<Operation::identity>(tail.data() + common, nullptr, tail.size() - common));
		}
		return result;
	}
	template <Operation Op> static DynamicBitset binary(const DynamicBitset &a, const DynamicBitset &b) {
		bool first = Op == Operation::bit_and ? a.n_ <= b.n_ : a.n_ >= b.n_;
		DynamicBitset result = first ? a : b;
		const auto &other = first ? b : a;
		bitset_ops_detail::apply<Op>(result.data_.data(), other.data_.data(), std::min(result.data_.size(), other.data_.size()));
		return result;
	}
	template <bool Left, bool Or> DynamicBitset &shift(std::size_t amount) {
		if (amount >= std::size_t(n_)) { if constexpr (!Or) reset_all(); return *this; }
		if (!amount) return *this;
		std::size_t skip = amount / 64, length = data_.size();
		unsigned bits = amount & 63;
		if constexpr (Left) {
			for (std::size_t i = length; i-- > skip;) {
				Word x = data_[i - skip] << bits;
				if (bits && i > skip) x |= data_[i - skip - 1] >> (64 - bits);
				if constexpr (Or) data_[i] |= x;
				else data_[i] = x;
			}
			if constexpr (!Or) std::fill(data_.begin(), data_.begin() + skip, 0);
		} else {
			for (std::size_t i = 0; i < length - skip; ++i) {
				Word x = data_[i + skip] >> bits;
				if (bits && i + skip + 1 < length) x |= data_[i + skip + 1] << (64 - bits);
				if constexpr (Or) data_[i] |= x;
				else data_[i] = x;
			}
			if constexpr (!Or) std::fill(data_.end() - skip, data_.end(), 0);
		}
		trim();
		return *this;
	}
	static Word reverse_word(Word x) {
		x = ((x >> 1) & 0x5555555555555555ULL) | ((x & 0x5555555555555555ULL) << 1);
		x = ((x >> 2) & 0x3333333333333333ULL) | ((x & 0x3333333333333333ULL) << 2);
		x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL) | ((x & 0x0f0f0f0f0f0f0f0fULL) << 4);
		return std::byteswap(x);
	}

  public:
	class reference {
		Word *word_;
		Word mask_;
		friend class DynamicBitset;
		reference(Word &word, int bit) : word_(&word), mask_(Word(1) << bit) {}
	  public:
		reference(const reference &) = default;
		operator bool() const { return (*word_ & mask_) != 0; }
		reference &operator=(bool value) { if (value) *word_ |= mask_; else *word_ &= ~mask_; return *this; }
		reference &operator=(const reference &other) { return *this = bool(other); }
		reference &flip() { *word_ ^= mask_; return *this; }
	};
	DynamicBitset() = default;
	explicit DynamicBitset(int n, bool value = false) : n_(n) {
		assert(n >= 0);
		data_.assign(word_count(n), value ? ~Word(0) : 0); trim();
	}
	explicit DynamicBitset(std::string_view text) {
		assert(text.size() <= std::size_t(std::numeric_limits<int>::max()));
		n_ = int(text.size()); data_.resize(word_count(n_));
		for (int i = 0; i < n_; ++i) {
			char c = text[std::size_t(n_ - 1 - i)];
			if (c != '0' && c != '1') throw std::invalid_argument("DynamicBitset");
			if (c == '1') data_[unsigned(i) / 64] |= Word(1) << (i & 63);
		}
	}
	DynamicBitset(const DynamicBitset &) = default;
	DynamicBitset &operator=(const DynamicBitset &) = default;
	DynamicBitset(DynamicBitset &&other) noexcept { swap(other); }
	DynamicBitset &operator=(DynamicBitset &&other) noexcept {
		if (this != &other) { DynamicBitset moved(std::move(other)); swap(moved); } return *this;
	}
	static DynamicBitset from_words(int n, std::span<const Word> words) {
		assert(n >= 0 && words.size() == word_count(n));
		DynamicBitset result; result.data_.assign(words.begin(), words.end()); result.n_ = n; result.trim(); return result;
	}
	void swap(DynamicBitset &other) noexcept { data_.swap(other.data_); std::swap(n_, other.n_); }
	[[nodiscard]] int size() const { return n_; }
	[[nodiscard]] bool empty() const { return !n_; }
	[[nodiscard]] std::span<const Word> words() const { return data_; }
	[[nodiscard]] bool test(int p) const { check(p); return (data_[unsigned(p) / 64] >> (p & 63)) & 1; }
	[[nodiscard]] bool operator[](int p) const { return test(p); }
	[[nodiscard]] reference operator[](int p) { check(p); return reference(data_[unsigned(p) / 64], p & 63); }
	DynamicBitset &set(int p, bool value = true) { (*this)[p] = value; return *this; }
	DynamicBitset &reset(int p) { return set(p, false); }
	DynamicBitset &flip(int p) { (*this)[p].flip(); return *this; }
	DynamicBitset &set_all(bool value = true) { std::fill(data_.begin(), data_.end(), value ? ~Word(0) : 0); trim(); return *this; }
	DynamicBitset &reset_all() { return set_all(false); }
	DynamicBitset &flip_all() { for (auto &x : data_) x = ~x; trim(); return *this; }
	DynamicBitset &set_range(int l, int r, bool value = true) {
		update_range(l, r, [value](Word &x, Word m) { if (value) x |= m; else x &= ~m; }); return *this;
	}
	DynamicBitset &reset_range(int l, int r) { return set_range(l, r, false); }
	DynamicBitset &flip_range(int l, int r) { update_range(l, r, [](Word &x, Word m) { x ^= m; }); return *this; }
	void reserve(int n) { assert(n >= 0); data_.reserve(word_count(n)); }
	void resize(int n, bool value = false) {
		assert(n >= 0);
		int old = n_;
		data_.resize(word_count(n), 0); n_ = n;
		if (n > old && value) set_range(old, n); else trim();
	}
	void push_back(bool value) { assert(n_ < std::numeric_limits<int>::max()); int p = n_; resize(n_ + 1); set(p, value); }
	void pop_back() { assert(n_); resize(n_ - 1); }
	void clear() { data_.clear(); n_ = 0; }
	[[nodiscard]] int count() const { return count_with<Operation::identity>(*this); }
	[[nodiscard]] int count(int l, int r) const {
		check_range(l, r); if (l == r) return 0;
		std::size_t first = unsigned(l) / 64, last = unsigned(r - 1) / 64;
		Word left = ~Word(0) << (l & 63), right = mask(((r - 1) & 63) + 1);
		if (first == last) return std::popcount(data_[first] & left & right);
		int result = std::popcount(data_[first] & left) + std::popcount(data_[last] & right);
		result += int(bitset_ops_detail::count<Operation::identity>(data_.data() + first + 1, nullptr, last - first - 1));
		return result;
	}
	[[nodiscard]] int rank(int r) const { return count(0, r); }
	[[nodiscard]] bool any() const { for (auto x : data_) if (x) return true; return false; }
	[[nodiscard]] bool none() const { return !any(); }
	[[nodiscard]] bool all() const {
		std::size_t full = unsigned(n_) / 64;
		for (std::size_t i = 0; i < full; ++i) if (data_[i] != ~Word(0)) return false;
		return !(n_ & 63) || data_[full] == mask(n_ & 63);
	}
	[[nodiscard]] int count_and(const DynamicBitset &other) const { return count_with<Operation::bit_and>(other); }
	[[nodiscard]] int count_or(const DynamicBitset &other) const { return count_with<Operation::bit_or>(other); }
	[[nodiscard]] int count_xor(const DynamicBitset &other) const { return count_with<Operation::bit_xor>(other); }
	[[nodiscard]] int count_and_not(const DynamicBitset &other) const { return count_with<Operation::and_not>(other); }
	[[nodiscard]] bool intersection_parity(const DynamicBitset &other) const {
		check_size(other); Word x = 0;
		for (std::size_t i = 0; i < data_.size(); ++i) x ^= data_[i] & other.data_[i];
		return std::popcount(x) & 1;
	}
	[[nodiscard]] bool intersects(const DynamicBitset &other) const { check_size(other); for (std::size_t i = 0; i < data_.size(); ++i) if (data_[i] & other.data_[i]) return true; return false; }
	[[nodiscard]] bool is_subset_of(const DynamicBitset &other) const { check_size(other); for (std::size_t i = 0; i < data_.size(); ++i) if (data_[i] & ~other.data_[i]) return false; return true; }
	[[nodiscard]] bool is_proper_subset_of(const DynamicBitset &other) const { return is_subset_of(other) && *this != other; }
	[[nodiscard]] int compare(const DynamicBitset &other) const {
		check_size(other); for (auto i = data_.size(); i-- > 0;) if (data_[i] != other.data_[i]) return data_[i] < other.data_[i] ? -1 : 1; return 0;
	}
	[[nodiscard]] int find_next(int p, bool value = true) const {
		assert(-1 <= p && p < n_); ++p;
		if (p == n_) return n_;
		std::size_t i = unsigned(p) / 64;
		Word x = chosen(i, value) & (~Word(0) << (p & 63));
		for (;;) {
			if (x) return int(i * 64 + std::countr_zero(x));
			if (++i == data_.size()) return n_;
			x = chosen(i, value);
		}
	}
	[[nodiscard]] int find_prev(int p, bool value = true) const {
		assert(0 <= p && p <= n_); if (!p) return n_; --p;
		std::size_t i = unsigned(p) / 64;
		Word x = chosen(i, value) & mask((p & 63) + 1);
		for (;;) {
			if (x) return int(i * 64 + 63 - std::countl_zero(x));
			if (!i) return n_;
			x = chosen(--i, value);
		}
	}
	[[nodiscard]] int find_first(bool value = true) const { return n_ ? find_next(-1, value) : 0; }
	[[nodiscard]] int find_last(bool value = true) const { return find_prev(n_, value); }
	[[nodiscard]] int select(int k, bool value = true) const {
		assert(k >= 0);
		for (std::size_t i = 0; i < data_.size(); ++i) {
			Word x = chosen(i, value); int c = std::popcount(x);
			if (k < c) { while (k--) x &= x - 1; return int(i * 64 + std::countr_zero(x)); }
			k -= c;
		}
		return n_;
	}
	template <class F> void for_each(int l, int r, F &&emit) const {
		check_range(l, r); if (l == r) return;
		for (std::size_t i = unsigned(l) / 64, last = unsigned(r - 1) / 64; i <= last; ++i) {
			Word x = data_[i];
			if (i == unsigned(l) / 64) x &= ~Word(0) << (l & 63);
			if (i == last) x &= mask(((r - 1) & 63) + 1);
			while (x) { emit(int(i * 64 + std::countr_zero(x))); x &= x - 1; }
		}
	}
	template <class F> void for_each(F &&emit) const { for_each(0, n_, std::forward<F>(emit)); }
	DynamicBitset &operator&=(const DynamicBitset &other) {
		if (n_ > other.n_) resize(other.n_);
		bitset_ops_detail::apply<Operation::bit_and>(data_.data(), other.data_.data(), data_.size()); return *this;
	}
	DynamicBitset &operator|=(const DynamicBitset &other) {
		if (n_ < other.n_) resize(other.n_);
		bitset_ops_detail::apply<Operation::bit_or>(data_.data(), other.data_.data(), other.data_.size()); return *this;
	}
	DynamicBitset &operator^=(const DynamicBitset &other) {
		if (n_ < other.n_) resize(other.n_);
		bitset_ops_detail::apply<Operation::bit_xor>(data_.data(), other.data_.data(), other.data_.size()); return *this;
	}
	DynamicBitset &operator-=(const DynamicBitset &other) { check_size(other); bitset_ops_detail::apply<Operation::and_not>(data_.data(), other.data_.data(), data_.size()); return *this; }
	friend DynamicBitset operator&(const DynamicBitset &a, const DynamicBitset &b) { return binary<Operation::bit_and>(a, b); }
	friend DynamicBitset operator|(const DynamicBitset &a, const DynamicBitset &b) { return binary<Operation::bit_or>(a, b); }
	friend DynamicBitset operator^(const DynamicBitset &a, const DynamicBitset &b) { return binary<Operation::bit_xor>(a, b); }
	friend DynamicBitset operator-(DynamicBitset a, const DynamicBitset &b) { a -= b; return a; }
	DynamicBitset operator~() const { auto result = *this; result.flip_all(); return result; }
	[[nodiscard]] bool operator==(const DynamicBitset &) const = default;
	DynamicBitset &operator<<=(std::size_t k) { return shift<true, false>(k); }
	DynamicBitset &operator>>=(std::size_t k) { return shift<false, false>(k); }
	friend DynamicBitset operator<<(DynamicBitset a, std::size_t k) { a <<= k; return a; }
	friend DynamicBitset operator>>(DynamicBitset a, std::size_t k) { a >>= k; return a; }
	DynamicBitset &or_shift_left(std::size_t k) { return shift<true, true>(k); }
	DynamicBitset &or_shift_right(std::size_t k) { return shift<false, true>(k); }
	void copy_range(int dst, const DynamicBitset &source, int l, int r) {
		source.check_range(l, r); assert(0 <= dst && r - l <= n_ - dst);
		int length = r - l;
		auto copy = [&](int offset, int count) {
			Word x = source.extract(l + offset, count);
			int p = dst + offset; Word m = mask(count) << (p & 63);
			auto &target = data_[unsigned(p) / 64]; target = (target & ~m) | (x << (p & 63));
		};
		if (this == &source && dst > l) {
			while (length) { int count = std::min(length, ((dst + length - 1) & 63) + 1); length -= count; copy(length, count); }
		} else {
			for (int offset = 0; offset < length;) { int count = std::min(length - offset, 64 - ((dst + offset) & 63)); copy(offset, count); offset += count; }
		}
	}
	DynamicBitset slice(int l, int r) const { check_range(l, r); DynamicBitset result(r - l); result.copy_range(0, *this, l, r); return result; }
	void append(const DynamicBitset &other) {
		int length = other.n_, old = n_; assert(length <= std::numeric_limits<int>::max() - old);
		resize(old + length); copy_range(old, other, 0, length);
	}
	DynamicBitset &reverse() {
		std::reverse(data_.begin(), data_.end()); for (auto &x : data_) x = reverse_word(x);
		if (n_ & 63) {
			unsigned bits = 64 - (n_ & 63);
			for (std::size_t i = 0; i < data_.size(); ++i)
				data_[i] = (data_[i] >> bits) | (i + 1 < data_.size() ? data_[i + 1] << (64 - bits) : 0);
		}
		return *this;
	}
	DynamicBitset &rotate_left(std::size_t amount) {
		if (!n_ || !(amount %= std::size_t(n_))) return *this;
		auto wrap = *this; wrap >>= std::size_t(n_) - amount; *this <<= amount; return *this |= wrap;
	}
	DynamicBitset &rotate_right(std::size_t amount) { if (n_ && (amount %= std::size_t(n_))) rotate_left(std::size_t(n_) - amount); return *this; }
	[[nodiscard]] std::string to_string() const {
		std::string result(n_, '0'); for_each([&](int p) { result[std::size_t(n_ - 1 - p)] = '1'; }); return result;
	}
};

#endif

Back to top page