47 const Bitvector::IntType Bitvector::all_1_ = (((1ul << 32) - 1) << 32) + ((1ul << 32) - 1);
49 const std::array<Bitvector::IntType, Bitvector::IntSize> Bitvector::bit_mask_ =
51 1ul << 0, 1ul << 1, 1ul << 2, 1ul << 3, 1ul << 4, 1ul << 5, 1ul << 6, 1ul << 7,
52 1ul << 8, 1ul << 9, 1ul << 10, 1ul << 11, 1ul << 12, 1ul << 13, 1ul << 14, 1ul << 15,
53 1ul << 16, 1ul << 17, 1ul << 18, 1ul << 19, 1ul << 20, 1ul << 21, 1ul << 22, 1ul << 23,
54 1ul << 24, 1ul << 25, 1ul << 26, 1ul << 27, 1ul << 28, 1ul << 29, 1ul << 30, 1ul << 31,
55 1ul << 32, 1ul << 33, 1ul << 34, 1ul << 35, 1ul << 36, 1ul << 37, 1ul << 38, 1ul << 39,
56 1ul << 40, 1ul << 41, 1ul << 42, 1ul << 43, 1ul << 44, 1ul << 45, 1ul << 46, 1ul << 47,
57 1ul << 48, 1ul << 49, 1ul << 50, 1ul << 51, 1ul << 52, 1ul << 53, 1ul << 54, 1ul << 55,
58 1ul << 56, 1ul << 57, 1ul << 58, 1ul << 59, 1ul << 60, 1ul << 61, 1ul << 62, 1ul << 63
61 const std::array<Bitvector::IntType, Bitvector::IntSize> Bitvector::ones_mask_ =
63 Bitvector::all_1_, Bitvector::all_1_ >> 63, Bitvector::all_1_ >> 62, Bitvector::all_1_ >> 61,
64 Bitvector::all_1_ >> 60, Bitvector::all_1_ >> 59, Bitvector::all_1_ >> 58, Bitvector::all_1_ >> 57,
65 Bitvector::all_1_ >> 56, Bitvector::all_1_ >> 55, Bitvector::all_1_ >> 54, Bitvector::all_1_ >> 53,
66 Bitvector::all_1_ >> 52, Bitvector::all_1_ >> 51, Bitvector::all_1_ >> 50, Bitvector::all_1_ >> 49,
67 Bitvector::all_1_ >> 48, Bitvector::all_1_ >> 47, Bitvector::all_1_ >> 46, Bitvector::all_1_ >> 45,
68 Bitvector::all_1_ >> 44, Bitvector::all_1_ >> 43, Bitvector::all_1_ >> 42, Bitvector::all_1_ >> 41,
69 Bitvector::all_1_ >> 40, Bitvector::all_1_ >> 39, Bitvector::all_1_ >> 38, Bitvector::all_1_ >> 37,
70 Bitvector::all_1_ >> 36, Bitvector::all_1_ >> 35, Bitvector::all_1_ >> 34, Bitvector::all_1_ >> 33,
71 Bitvector::all_1_ >> 32, Bitvector::all_1_ >> 31, Bitvector::all_1_ >> 30, Bitvector::all_1_ >> 29,
72 Bitvector::all_1_ >> 28, Bitvector::all_1_ >> 27, Bitvector::all_1_ >> 26, Bitvector::all_1_ >> 25,
73 Bitvector::all_1_ >> 24, Bitvector::all_1_ >> 23, Bitvector::all_1_ >> 22, Bitvector::all_1_ >> 21,
74 Bitvector::all_1_ >> 20, Bitvector::all_1_ >> 19, Bitvector::all_1_ >> 18, Bitvector::all_1_ >> 17,
75 Bitvector::all_1_ >> 16, Bitvector::all_1_ >> 15, Bitvector::all_1_ >> 14, Bitvector::all_1_ >> 13,
76 Bitvector::all_1_ >> 12, Bitvector::all_1_ >> 11, Bitvector::all_1_ >> 10, Bitvector::all_1_ >> 9,
77 Bitvector::all_1_ >> 8, Bitvector::all_1_ >> 7, Bitvector::all_1_ >> 6, Bitvector::all_1_ >> 5,
78 Bitvector::all_1_ >> 4, Bitvector::all_1_ >> 3, Bitvector::all_1_ >> 2, Bitvector::all_1_ >> 1
81 const std::array<Bitvector::IntType, 4> Bitvector::count_mask_ =
96 for(
size_t i = 0; i < values.size(); ++i ) {
104 throw std::invalid_argument(
105 "Cannot construct Bitvector from std::string that contains characters "
106 "other than 0 and 1."
114 if( max_size > other.
size() ) {
115 max_size = other.
size();
118 auto const ds = (size_ /
IntSize) + (size_ %
IntSize == 0 ? 0 : 1);
119 assert( ds <= other.data_.size() );
120 data_ = std::vector<IntType>( other.data_.begin(), other.data_.begin() + ds );
130 if( size_ != rhs.size_ ) {
131 throw std::runtime_error(
132 "Cannot use operator `&` or `&=` on Bitvectors of different size. "
133 "Use bitwise_and() instead."
137 for (
size_t i = 0; i < data_.size(); ++i) {
138 data_[i] &= rhs.data_[i];
145 if( size_ != rhs.size_ ) {
146 throw std::runtime_error(
147 "Cannot use operator `|` or `|=` on Bitvectors of different size. "
148 "Use bitwise_or() instead."
152 for (
size_t i = 0; i < data_.size(); ++i) {
153 data_[i] |= rhs.data_[i];
160 if( size_ != rhs.size_ ) {
161 throw std::runtime_error(
162 "Cannot use operator `^` or `^=` on Bitvectors of different size. "
163 "Use bitwise_xor() instead."
167 for (
size_t i = 0; i < data_.size(); ++i) {
168 data_[i] ^= rhs.data_[i];
203 if (size_ != other.size_) {
206 for (
size_t i = 0; i < data_.size(); ++i) {
207 if (data_[i] != other.data_[i]) {
216 return !(*
this == other);
228 x -= (x >> 1) & count_mask_[0];
231 x = (x & count_mask_[1]) + ((x >> 2) & count_mask_[1]);
234 x = (x + (x >> 4)) & count_mask_[2];
237 res += (x * count_mask_[3]) >> 56;
255 for(
auto const& d : data_ ) {
264 for(
auto const& d : data_ ) {
273 for (
size_t i = 0; i < data_.size(); ++i) {
274 data_[i] = ~ data_[i];
283 if (size_ > 0 &&
get(0)) {
291 const auto v = value ? all_1_ : all_0_;
292 for (
size_t i = 0; i < data_.size(); ++i) {
302 void Bitvector::unset_padding_()
311 assert( size_ %
IntSize < ones_mask_.size() );
312 data_.back() &= ones_mask_[ size_ %
IntSize ];
330 for (
size_t i = 0; i < size_; ++i) {
331 res += (*this)[i] ?
"1" :
"0";
332 if ((i+1) % 64 == 0) {
334 }
else if ((i+1) % 8 == 0) {
343 std::string res =
"";
344 for (
size_t i = 0; i <
IntSize; ++i) {
345 res += (x & bit_mask_[i] ?
"1" :
"0");
346 if ((i+1) % 8 == 0) {