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) {
Bitvector & operator^=(Bitvector const &rhs)
std::size_t hash_combine(std::size_t seed, T const &value)
Combine a seed value (e.g., another hash) with the hash of a given type.
Bitvector & operator&=(Bitvector const &rhs)
size_t count() const
Count the number of set bits in the Bitvector, that is, its Hamming weight, or population count (popc...
IntType x_hash() const
Return a hash value of type IntType that is quicker to calculate than hash().
static const size_t IntSize
Bitvector()=default
Default constructor. Creates an empty Bitvector of size 0.
Bitvector operator~() const
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
Provides some valuable additions to STD.
void negate()
Flip all bits.
friend Bitvector operator&(Bitvector const &lhs, Bitvector const &rhs)
bool operator==(const Bitvector &other) const
bool operator!=(const Bitvector &other) const
friend Bitvector operator^(Bitvector const &lhs, Bitvector const &rhs)
void normalize()
Bring the Bitvector in a normalized form, where the first bit is always zero.
Bitvector & operator|=(Bitvector const &rhs)
std::string dump_int(IntType x) const
std::shared_ptr< BaseOutputTarget > to_string(std::string &target_string)
Obtain an output target for writing to a string.
void set_all(const bool value=false)
Set all the bits to a specified value.
size_t hash() const
Return an std::hash value for the Bitvector.
size_t size() const
Return the size (number of bits) of this Bitvector.
friend Bitvector operator|(Bitvector const &lhs, Bitvector const &rhs)