1 #include <bf/bitvector.h>
7 typedef bitvector::size_type size_type;
8 typedef bitvector::block_type block_type;
12 uint8_t count_table[] =
14 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
15 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
16 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
17 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
18 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
19 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
20 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
21 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
22 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
23 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
31 , mask_(block_type(1) << i)
33 assert(i < bits_per_block);
42 bitvector::reference::operator bool()
const
44 return (block_ & mask_) != 0;
47 bool bitvector::reference::operator~()
const
49 return (block_ & mask_) == 0;
52 bitvector::reference& bitvector::reference::operator=(
bool x)
54 x ? block_ |= mask_ : block_ &= ~mask_;
58 bitvector::reference& bitvector::reference::operator=(reference
const& other)
60 other ? block_ |= mask_ : block_ &= ~mask_;
64 bitvector::reference& bitvector::reference::operator|=(
bool x)
71 bitvector::reference& bitvector::reference::operator&=(
bool x)
78 bitvector::reference& bitvector::reference::operator^=(
bool x)
85 bitvector::reference& bitvector::reference::operator-=(
bool x)
99 : bits_(bits_to_blocks(size), value ? ~block_type(0) : 0)
106 , num_bits_(other.num_bits_)
111 : bits_(std::move(other.bits_))
112 , num_bits_(other.num_bits_)
133 swap(x.bits_, y.bits_);
134 swap(x.num_bits_, y.num_bits_);
137 bitvector bitvector::operator<<(size_type n)
const
143 bitvector bitvector::operator>>(size_type n)
const
149 bitvector& bitvector::operator<<=(size_type n)
157 auto div = n / bits_per_block;
165 for (size_type i = last - div; i > 0; --i)
166 b[i + div] = (b[i] << r) | (b[i - 1] >> (bits_per_block - r));
171 for (size_type i = last-div; i > 0; --i)
176 std::fill_n(b, div, block_type(0));
183 bitvector& bitvector::operator>>=(size_type n)
191 auto div = n / bits_per_block;
199 for (size_type i = last - div; i > 0; --i)
200 b[i - div] = (b[i] >> r) | (b[i + 1] << (bits_per_block - r));
201 b[last - div] = b[last] >> r;
205 for (size_type i = div; i <= last; ++i)
209 std::fill_n(b + (
blocks() - div), div, block_type(0));
215 bitvector& bitvector::operator&=(bitvector
const& other)
217 assert(
size() >= other.size());
218 for (size_type i = 0; i <
blocks(); ++i)
219 bits_[i] &= other.bits_[i];
223 bitvector& bitvector::operator|=(bitvector
const& other)
225 assert(
size() >= other.size());
226 for (size_type i = 0; i <
blocks(); ++i)
227 bits_[i] |= other.bits_[i];
231 bitvector& bitvector::operator^=(bitvector
const& other)
233 assert(
size() >= other.size());
234 for (size_type i = 0; i <
blocks(); ++i)
235 bits_[i] ^= other.bits_[i];
239 bitvector& bitvector::operator-=(bitvector
const& other)
241 assert(
size() >= other.size());
242 for (size_type i = 0; i <
blocks(); ++i)
243 bits_[i] &= ~other.bits_[i];
247 bitvector operator&(bitvector
const& x, bitvector
const& y)
253 bitvector operator|(bitvector
const& x, bitvector
const& y)
259 bitvector operator^(bitvector
const& x, bitvector
const& y)
265 bitvector operator-(bitvector
const& x, bitvector
const& y)
271 bool operator==(bitvector
const& x, bitvector
const& y)
273 return x.num_bits_ == y.num_bits_ && x.bits_ == y.bits_;
276 bool operator!=(bitvector
const& x, bitvector
const& y)
281 bool operator<(bitvector
const& x, bitvector
const& y)
283 assert(x.size() == y.size());
284 for (size_type r = x.blocks(); r > 0; --r)
287 if (x.bits_[i] < y.bits_[i])
289 else if (x.bits_[i] > y.bits_[i])
299 auto block_value = value ? ~block_type(0) : block_type(0);
302 bits_.resize(required, block_value);
305 bits_[old - 1] |= (block_value <<
extra_bits());
329 assert(! bits_.empty());
330 bits_.push_back(block >> (bits_per_block - excess));
331 bits_[bits_.size() - 2] |= (block << excess);
335 bits_.push_back(block);
337 num_bits_ += bits_per_block;
342 assert(i < num_bits_);
354 std::fill(bits_.begin(), bits_.end(), ~block_type(0));
361 assert(i < num_bits_);
368 std::fill(bits_.begin(), bits_.end(), block_type(0));
374 assert(i < num_bits_);
381 for (size_type i = 0; i <
blocks(); ++i)
382 bits_[i] = ~bits_[i];
389 assert(i < num_bits_);
395 assert(i < num_bits_);
401 auto first = bits_.begin();
410 n += count_table[block & ((1u << 8) - 1)];
431 return bits_.empty();
441 if (i >= (
size() - 1) ||
size() == 0)
445 auto block = bits_[bi] & (~block_type(0) <<
bit_index(i));
451 auto x = block - (block & (block - 1));
463 void bitvector::zero_unused_bits()
466 bits_.back() &= ~(~block_type(0) <<
extra_bits());
471 while (i <
blocks() && bits_[i] == 0)
475 return i * bits_per_block +
lowest_bit(bits_[i]);
478 std::string to_string(
bitvector const& b,
484 auto str_size = all ? bitvector::bits_per_block * b.
blocks() : b.
size();
485 if (cut_off == 0 || str_size <= cut_off)
487 str.assign(str_size,
'0');
491 str.assign(cut_off + 2,
'0');
492 str[cut_off + 0] =
'.';
493 str[cut_off + 1] =
'.';
497 for (bitvector::size_type i = 0; i < std::min(str_size, b.
size()); ++i)
499 str[msb_to_lsb ? str_size - i - 1 : i] =
'1';