dynamic_bitset.hpp¶
Resizable packed bitset with bitwise operations, shifts, population count, and efficient iteration over set bits.
提供运行时长度的位集及位运算、移位和查找置位；适合状态长度不在编译期确定的 bitset 优化。
Implementation¶
#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 bits_per_word = 64;
std::size_t bit_size = 0;
std::vector<word_type> words;
dynamic_bitset() = default;
explicit dynamic_bitset(std::size_t size, bool value = false)
: bit_size(size), words(word_count(size), value ? ~word_type{} : 0) {
trim();
}
std::size_t size() const { return bit_size; }
bool empty() const { return bit_size == 0; }
bool test(std::size_t position) const {
assert(position < bit_size);
return (words[position / bits_per_word] >> (position % bits_per_word)) & 1;
}
bool operator[](std::size_t position) const { return test(position); }
dynamic_bitset &set(std::size_t position, bool value = true) {
assert(position < bit_size);
word_type mask = word_type(1) << (position % bits_per_word);
if (value) {
words[position / bits_per_word] |= mask;
} else {
words[position / bits_per_word] &= ~mask;
}
return *this;
}
dynamic_bitset &reset(std::size_t position) { return set(position, false); }
dynamic_bitset &flip(std::size_t position) {
assert(position < bit_size);
words[position / bits_per_word] ^=
word_type(1) << (position % bits_per_word);
return *this;
}
dynamic_bitset &set() {
std::fill(words.begin(), words.end(), ~word_type{});
trim();
return *this;
}
dynamic_bitset &reset() {
std::fill(words.begin(), words.end(), word_type{});
return *this;
}
dynamic_bitset &flip() {
for (word_type &word : words) {
word = ~word;
}
trim();
return *this;
}
std::size_t count() const {
std::size_t result = 0;
for (word_type word : words) {
result += std::popcount(word);
}
return result;
}
bool any() const {
return std::any_of(words.begin(), words.end(),
[](word_type word) { return word != 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 position) const {
if (position >= bit_size) {
return bit_size;
}
std::size_t index = position / bits_per_word;
word_type word =
words[index] & (~word_type{} << (position % bits_per_word));
if (word != 0) {
return std::min(bit_size,
index * bits_per_word + std::size_t(std::countr_zero(word)));
}
for (index++; index < words.size(); index++) {
if (words[index] != 0) {
return std::min(
bit_size, index * bits_per_word +
std::size_t(std::countr_zero(words[index])));
}
}
return bit_size;
}
std::size_t find_first() const { return find_next(0); }
dynamic_bitset &operator&=(const dynamic_bitset &other) {
check_same_size(other);
for (std::size_t i = 0; i < words.size(); i++) {
words[i] &= other.words[i];
}
return *this;
}
dynamic_bitset &operator|=(const dynamic_bitset &other) {
check_same_size(other);
for (std::size_t i = 0; i < words.size(); i++) {
words[i] |= other.words[i];
}
return *this;
}
dynamic_bitset &operator^=(const dynamic_bitset &other) {
check_same_size(other);
for (std::size_t i = 0; i < words.size(); i++) {
words[i] ^= other.words[i];
}
return *this;
}
dynamic_bitset &operator<<=(std::size_t shift) {
if (shift >= bit_size) {
return reset();
}
std::size_t whole = shift / bits_per_word;
int part = int(shift % bits_per_word);
for (std::size_t i = words.size(); i-- > 0;) {
word_type value = 0;
if (i >= whole) {
value = words[i - whole] << part;
if (part != 0 && i > whole) {
value |= words[i - whole - 1] >> (bits_per_word - part);
}
}
words[i] = value;
}
trim();
return *this;
}
dynamic_bitset &operator>>=(std::size_t shift) {
if (shift >= bit_size) {
return reset();
}
std::size_t whole = shift / bits_per_word;
int part = int(shift % bits_per_word);
for (std::size_t i = 0; i < words.size(); i++) {
word_type value = 0;
if (i + whole < words.size()) {
value = words[i + whole] >> part;
if (part != 0 && i + whole + 1 < words.size()) {
value |= words[i + whole + 1] << (bits_per_word - part);
}
}
words[i] = value;
}
return *this;
}
friend dynamic_bitset operator&(dynamic_bitset first,
const dynamic_bitset &second) {
return first &= second;
}
friend dynamic_bitset operator|(dynamic_bitset first,
const dynamic_bitset &second) {
return first |= second;
}
friend dynamic_bitset operator^(dynamic_bitset first,
const dynamic_bitset &second) {
return first ^= second;
}
friend dynamic_bitset operator<<(dynamic_bitset value, std::size_t shift) {
return value <<= shift;
}
friend dynamic_bitset operator>>(dynamic_bitset value, std::size_t shift) {
return value >>= shift;
}
friend dynamic_bitset operator~(dynamic_bitset value) { return value.flip(); }
friend bool operator==(const dynamic_bitset &, const dynamic_bitset &) =
default;
private:
static std::size_t word_count(std::size_t size) {
return (size + bits_per_word - 1) / bits_per_word;
}
void trim() {
if (!words.empty() && bit_size % bits_per_word != 0) {
words.back() &=
(word_type(1) << (bit_size % bits_per_word)) - word_type(1);
}
}
void check_same_size(const dynamic_bitset &other) const {
assert(bit_size == other.bit_size);
}
};
} // 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 bits_per_word = 64;
std::size_t bit_size = 0;
std::vector<word_type> words;
dynamic_bitset() = default;
explicit dynamic_bitset(std::size_t size, bool value = false)
: bit_size(size), words(word_count(size), value ? ~word_type{} : 0) {
trim();
}
std::size_t size() const { return bit_size; }
bool empty() const { return bit_size == 0; }
bool test(std::size_t position) const {
assert(position < bit_size);
return (words[position / bits_per_word] >> (position % bits_per_word)) & 1;
}
bool operator[](std::size_t position) const { return test(position); }
dynamic_bitset &set(std::size_t position, bool value = true) {
assert(position < bit_size);
word_type mask = word_type(1) << (position % bits_per_word);
if (value) {
words[position / bits_per_word] |= mask;
} else {
words[position / bits_per_word] &= ~mask;
}
return *this;
}
dynamic_bitset &reset(std::size_t position) { return set(position, false); }
dynamic_bitset &flip(std::size_t position) {
assert(position < bit_size);
words[position / bits_per_word] ^=
word_type(1) << (position % bits_per_word);
return *this;
}
dynamic_bitset &set() {
std::fill(words.begin(), words.end(), ~word_type{});
trim();
return *this;
}
dynamic_bitset &reset() {
std::fill(words.begin(), words.end(), word_type{});
return *this;
}
dynamic_bitset &flip() {
for (word_type &word : words) {
word = ~word;
}
trim();
return *this;
}
std::size_t count() const {
std::size_t result = 0;
for (word_type word : words) {
result += std::popcount(word);
}
return result;
}
bool any() const {
return std::any_of(words.begin(), words.end(),
[](word_type word) { return word != 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 position) const {
if (position >= bit_size) {
return bit_size;
}
std::size_t index = position / bits_per_word;
word_type word =
words[index] & (~word_type{} << (position % bits_per_word));
if (word != 0) {
return std::min(bit_size,
index * bits_per_word + std::size_t(std::countr_zero(word)));
}
for (index++; index < words.size(); index++) {
if (words[index] != 0) {
return std::min(
bit_size, index * bits_per_word +
std::size_t(std::countr_zero(words[index])));
}
}
return bit_size;
}
std::size_t find_first() const { return find_next(0); }
dynamic_bitset &operator&=(const dynamic_bitset &other) {
check_same_size(other);
for (std::size_t i = 0; i < words.size(); i++) {
words[i] &= other.words[i];
}
return *this;
}
dynamic_bitset &operator|=(const dynamic_bitset &other) {
check_same_size(other);
for (std::size_t i = 0; i < words.size(); i++) {
words[i] |= other.words[i];
}
return *this;
}
dynamic_bitset &operator^=(const dynamic_bitset &other) {
check_same_size(other);
for (std::size_t i = 0; i < words.size(); i++) {
words[i] ^= other.words[i];
}
return *this;
}
dynamic_bitset &operator<<=(std::size_t shift) {
if (shift >= bit_size) {
return reset();
}
std::size_t whole = shift / bits_per_word;
int part = int(shift % bits_per_word);
for (std::size_t i = words.size(); i-- > 0;) {
word_type value = 0;
if (i >= whole) {
value = words[i - whole] << part;
if (part != 0 && i > whole) {
value |= words[i - whole - 1] >> (bits_per_word - part);
}
}
words[i] = value;
}
trim();
return *this;
}
dynamic_bitset &operator>>=(std::size_t shift) {
if (shift >= bit_size) {
return reset();
}
std::size_t whole = shift / bits_per_word;
int part = int(shift % bits_per_word);
for (std::size_t i = 0; i < words.size(); i++) {
word_type value = 0;
if (i + whole < words.size()) {
value = words[i + whole] >> part;
if (part != 0 && i + whole + 1 < words.size()) {
value |= words[i + whole + 1] << (bits_per_word - part);
}
}
words[i] = value;
}
return *this;
}
friend dynamic_bitset operator&(dynamic_bitset first,
const dynamic_bitset &second) {
return first &= second;
}
friend dynamic_bitset operator|(dynamic_bitset first,
const dynamic_bitset &second) {
return first |= second;
}
friend dynamic_bitset operator^(dynamic_bitset first,
const dynamic_bitset &second) {
return first ^= second;
}
friend dynamic_bitset operator<<(dynamic_bitset value, std::size_t shift) {
return value <<= shift;
}
friend dynamic_bitset operator>>(dynamic_bitset value, std::size_t shift) {
return value >>= shift;
}
friend dynamic_bitset operator~(dynamic_bitset value) { return value.flip(); }
friend bool operator==(const dynamic_bitset &, const dynamic_bitset &) =
default;
private:
static std::size_t word_count(std::size_t size) {
return (size + bits_per_word - 1) / bits_per_word;
}
void trim() {
if (!words.empty() && bit_size % bits_per_word != 0) {
words.back() &=
(word_type(1) << (bit_size % bits_per_word)) - word_type(1);
}
}
void check_same_size(const dynamic_bitset &other) const {
assert(bit_size == other.bit_size);
}
};
} // namespace noya