Empirical
BitSet.h
Go to the documentation of this file.
1 
16 #ifndef EMP_BIT_SET_H
17 #define EMP_BIT_SET_H
18 
19 #include <iostream>
20 
21 #include "../base/assert.h"
22 #include "../base/vector.h"
23 
24 #include "bitset_utils.h"
25 #include "functions.h"
26 #include "math.h"
27 #include "Random.h"
28 
29 namespace emp {
30 
33  template <size_t NUM_BITS> class BitSet {
34  private:
36  static const uint32_t NUM_FIELDS = 1 + ((NUM_BITS - 1) >> 5);
37 
39  static const uint32_t LAST_BIT = NUM_BITS & 31;
40 
42  static const uint32_t NUM_BYTES = 1 + ((NUM_BITS - 1) >> 3);
43 
44  uint32_t bit_set[NUM_FIELDS];
45 
47  class BitProxy {
48  private:
49  BitSet<NUM_BITS> & bit_set;
50  size_t index;
51  public:
52  BitProxy(BitSet<NUM_BITS> & _set, size_t _idx) : bit_set(_set), index(_idx) {
53  emp_assert(_idx < bit_set.size());
54  }
55 
57  BitProxy & operator=(bool b) { // lvalue handling...
58  bit_set.Set(index, b);
59  return *this;
60  }
61 
63  operator bool() const { // rvalue handling...
64  return bit_set.Get(index);
65  }
66 
68  BitProxy & Toggle() { bit_set.Toggle(index); return *this; }
69  };
70  friend class BitProxy;
71 
72  inline static size_t FieldID(const size_t index) {
73  emp_assert((index >> 5) < NUM_FIELDS);
74  return index >> 5;
75  }
76  inline static size_t FieldPos(const size_t index) { return index & 31; }
77 
78  inline static size_t Byte2Field(const size_t index) { return index/4; }
79  inline static size_t Byte2FieldPos(const size_t index) { return (index & 3) << 3; }
80 
81  inline void Copy(const uint32_t in_set[NUM_FIELDS]) {
82  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = in_set[i];
83  }
84 
86  void ShiftLeft(const uint32_t shift_size) {
87  const int field_shift = shift_size / 32;
88  const int bit_shift = shift_size % 32;
89  const int bit_overflow = 32 - bit_shift;
90 
91  // Loop through each field, from L to R, and update it.
92  if (field_shift) {
93  for (int i = NUM_FIELDS - 1; i >= field_shift; --i) {
94  bit_set[i] = bit_set[i - field_shift];
95  }
96  for (int i = field_shift - 1; i >= 0; i--) bit_set[i] = 0;
97  }
98 
99  // account for bit_shift
100  if (bit_shift) {
101  for (int i = NUM_FIELDS - 1; i > field_shift; --i) {
102  bit_set[i] <<= bit_shift;
103  bit_set[i] |= (bit_set[i-1] >> bit_overflow);
104  }
105  // Handle final field (field_shift position)
106  bit_set[field_shift] <<= bit_shift;
107  }
108 
109  // Mask out any bits that have left-shifted away
110  if (LAST_BIT) { bit_set[NUM_FIELDS - 1] &= (1U << LAST_BIT) - 1U; }
111  }
112 
113 
115  void ShiftRight(const uint32_t shift_size) {
116  emp_assert(shift_size > 0);
117  const uint32_t field_shift = shift_size / 32;
118  const uint32_t bit_shift = shift_size % 32;
119  const uint32_t bit_overflow = 32 - bit_shift;
120 
121  // account for field_shift
122  if (field_shift) {
123  for (size_t i = 0; i < (NUM_FIELDS - field_shift); ++i) {
124  bit_set[i] = bit_set[i + field_shift];
125  }
126  for (size_t i = NUM_FIELDS - field_shift; i < NUM_FIELDS; i++) bit_set[i] = 0;
127  }
128 
129  // account for bit_shift
130  if (bit_shift) {
131  for (size_t i = 0; i < (NUM_FIELDS - 1 - field_shift); ++i) {
132  bit_set[i] >>= bit_shift;
133  bit_set[i] |= (bit_set[i+1] << bit_overflow);
134  }
135  bit_set[NUM_FIELDS - 1 - field_shift] >>= bit_shift;
136  }
137  }
138 
139  public:
141  BitSet() { Clear(); }
142 
144  BitSet(const BitSet & in_set) { Copy(in_set.bit_set); }
145 
147  BitSet(Random & random, const double p1=0.5) { Randomize(random, p1); }
148 
150  ~BitSet() = default;
151 
153  BitSet & operator=(const BitSet<NUM_BITS> & in_set) {
154  Copy(in_set.bit_set);
155  return *this;
156  }
157 
159  void Randomize(Random & random, const double p1=0.5) {
160  for (size_t i = 0; i < NUM_BITS; i++) Set(i, random.P(p1));
161  }
162 
164  template <size_t NUM_BITS2>
165  BitSet & Import(const BitSet<NUM_BITS2> & in_set) {
166  static const size_t NUM_FIELDS2 = 1 + ((NUM_BITS2 - 1) >> 5);
167  static const size_t MIN_FIELDS = (NUM_FIELDS < NUM_FIELDS2) ? NUM_FIELDS : NUM_FIELDS2;
168  for (size_t i = 0; i < MIN_FIELDS; i++) bit_set[i] = in_set.GetUInt(i); // Copy avail fields
169  for (size_t i = MIN_FIELDS; i < NUM_FIELDS; i++) bit_set[i] = 0; // Zero extra fields
170  return *this;
171  }
172 
174  template <size_t NUM_BITS2>
176  static const size_t NUM_FIELDS2 = 1 + ((NUM_BITS2 - 1) >> 5);
177  static const size_t MIN_FIELDS = (NUM_FIELDS < NUM_FIELDS2) ? NUM_FIELDS : NUM_FIELDS2;
178  BitSet<NUM_BITS2> out_bits;
179  for (size_t i = 0; i < MIN_FIELDS; i++) out_bits.SetUInt(i, bit_set[i]); // Copy avail fields
180  for (size_t i = MIN_FIELDS; i < NUM_FIELDS; i++) out_bits.SetUInt(i, 0); // Zero extra fields
181  return out_bits;
182  }
183 
185  bool operator==(const BitSet & in_set) const {
186  for (size_t i = 0; i < NUM_FIELDS; ++i) {
187  if (bit_set[i] != in_set.bit_set[i]) return false;
188  }
189  return true;
190  }
191 
193  bool operator<(const BitSet & in_set) const {
194  for (int i = NUM_FIELDS-1; i >= 0; --i) { // Start loop at the largest field.
195  if (bit_set[i] == in_set.bit_set[i]) continue; // If same, keep looking!
196  return (bit_set[i] < in_set.bit_set[i]); // Otherwise, do comparison
197  }
198  return false;
199  }
200 
202  bool operator<=(const BitSet & in_set) const {
203  for (int i = NUM_FIELDS-1; i >= 0; --i) { // Start loop at the largest field.
204  if (bit_set[i] == in_set.bit_set[i]) continue; // If same, keep looking!
205  return (bit_set[i] < in_set.bit_set[i]); // Otherwise, do comparison
206  }
207  return true;
208  }
209 
211  bool operator!=(const BitSet & in_set) const { return !operator==(in_set); }
212 
214  bool operator>(const BitSet & in_set) const { return !operator<=(in_set); }
215 
217  bool operator>=(const BitSet & in_set) const { return !operator<(in_set); }
218 
220  constexpr static size_t GetSize() { return NUM_BITS; }
221 
223  bool Get(size_t index) const {
224  emp_assert(index >= 0 && index < NUM_BITS);
225  const size_t field_id = FieldID(index);
226  const size_t pos_id = FieldPos(index);
227  return (bit_set[field_id] & (1 << pos_id)) != 0;
228  }
229 
231  void Set(size_t index, bool value) {
232  emp_assert(index < NUM_BITS);
233  const size_t field_id = FieldID(index);
234  const size_t pos_id = FieldPos(index);
235  const uint32_t pos_mask = 1 << pos_id;
236 
237  if (value) bit_set[field_id] |= pos_mask;
238  else bit_set[field_id] &= ~pos_mask;
239  }
240 
242  BitSet & Toggle() { return NOT_SELF(); }
243 
245  BitSet & Toggle(size_t index) {
246  emp_assert(index >= 0 && index < NUM_BITS);
247  const size_t field_id = FieldID(index);
248  const size_t pos_id = FieldPos(index);
249  (bit_set[field_id] ^= (1 << pos_id));
250  return *this;
251  }
252 
254  BitSet & Toggle(size_t start, size_t end) {
255  emp_assert(start <= end && end <= NUM_BITS);
256  for(size_t index = start; index < end; index++) {
257  Toggle(index);
258  }
259  return *this;
260  }
261 
263  uint8_t GetByte(size_t index) const {
264  emp_assert(index < NUM_BYTES);
265  const size_t field_id = Byte2Field(index);
266  const size_t pos_id = Byte2FieldPos(index);
267  return (bit_set[field_id] >> pos_id) & 255;
268  }
269 
271  void SetByte(size_t index, uint8_t value) {
272  emp_assert(index < NUM_BYTES);
273  const size_t field_id = Byte2Field(index);
274  const size_t pos_id = Byte2FieldPos(index);
275  const uint32_t val_uint = value;
276  bit_set[field_id] = (bit_set[field_id] & ~(255U << pos_id)) | (val_uint << pos_id);
277  }
278 
280  uint32_t GetUInt(size_t index) const {
281  emp_assert(index < NUM_FIELDS);
282  return bit_set[index];
283  }
284 
286  void SetUInt(size_t index, uint32_t value) {
287  emp_assert(index < NUM_FIELDS);
288  bit_set[index] = value;
289  }
290 
292  uint32_t GetUIntAtBit(size_t index) {
293  emp_assert(index < NUM_BITS);
294  const size_t field_id = FieldID(index);
295  const size_t pos_id = FieldPos(index);
296  if (pos_id == 0) return bit_set[field_id];
297  return (bit_set[field_id] >> pos_id) |
298  ((field_id+1 < NUM_FIELDS) ? bit_set[field_id+1] << (32-pos_id) : 0);
299  }
300 
302  template <size_t OUT_BITS>
303  uint32_t GetValueAtBit(size_t index) {
304  static_assert(OUT_BITS <= 32, "Requesting too many bits to fit in a UInt");
305  return GetUIntAtBit(index) & MaskLow<uint32_t>(OUT_BITS);
306  }
307 
309  bool Any() const { for (auto i : bit_set) if (i) return true; return false; }
310 
312  bool None() const { return !Any(); }
313 
315  bool All() const { return (~(*this)).None(); }
316 
318  bool operator[](size_t index) const { return Get(index); }
319 
321  BitProxy operator[](size_t index) { return BitProxy(*this, index); }
322 
324  void Clear() { for (auto & i : bit_set) i = 0U; }
325 
327  void SetAll() {
328  for (auto & i : bit_set) i = ~0U;
329  if (LAST_BIT > 0) { bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT); }
330  }
331 
333  void Print(std::ostream & out=std::cout) const {
334  for (size_t i = NUM_BITS; i > 0; i--) { out << Get(i-1); }
335  }
336 
338  void PrintArray(std::ostream & out=std::cout) const {
339  for (size_t i = 0; i < NUM_BITS; i++) out << Get(i);
340  }
341 
343  void PrintOneIDs(std::ostream & out=std::cout, char spacer=' ') const {
344  for (size_t i = 0; i < NUM_BITS; i++) { if (Get(i)) out << i << spacer; }
345  }
346 
348  size_t CountOnes_Sparse() const {
349  size_t bit_count = 0;
350  for (auto i : bit_set) {
351  while (i) {
352  i &= (i-1); // Peel off a single 1.
353  bit_count++; // And increment the counter
354  }
355  }
356  return bit_count;
357  }
358 
360  size_t CountOnes_Mixed() const {
361  size_t bit_count = 0;
362  for (const auto v : bit_set) {
363  const uint32_t t1 = v - ((v >> 1) & 0x55555555);
364  const uint32_t t2 = (t1 & 0x33333333) + ((t1 >> 2) & 0x33333333);
365  bit_count += (((t2 + (t2 >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
366  }
367  return bit_count;
368  }
369 
371  size_t CountOnes() const { return CountOnes_Mixed(); }
372 
374  int FindBit() const {
375  size_t field_id = 0;
376  while (field_id < NUM_FIELDS && bit_set[field_id]==0) field_id++;
377  return (field_id < NUM_FIELDS) ? (int) (find_bit(bit_set[field_id]) + (field_id << 5)) : -1;
378  }
379 
381  int PopBit() {
382  size_t field_id = 0;
383  while (field_id < NUM_FIELDS && bit_set[field_id]==0) field_id++;
384  if (field_id == NUM_FIELDS) return -1; // Failed to find bit!
385 
386  const int pos_found = (int) find_bit(bit_set[field_id]);
387  bit_set[field_id] &= ~(1U << pos_found);
388  return pos_found + (int)(field_id << 5);
389  }
390 
392  int FindBit(const size_t start_pos) const {
393  // @CAO -- There are better ways to do this with bit tricks
394  // (but start_pos is tricky...)
395  for (size_t i = start_pos; i < NUM_BITS; i++) {
396  if (Get(i)) return (int) i;
397  }
398  return -1;
399  }
400 
403  // @CAO -- There are better ways to do this with bit tricks.
404  emp::vector<size_t> out_set(CountOnes());
405  size_t cur_pos = 0;
406  for (size_t i = 0; i < NUM_BITS; i++) {
407  if (Get(i)) out_set[cur_pos++] = i;
408  }
409  return out_set;
410  }
411 
413  BitSet NOT() const {
414  BitSet out_set(*this);
415  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = ~bit_set[i];
416  if (LAST_BIT > 0) out_set.bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT);
417  return out_set;
418  }
419 
421  BitSet AND(const BitSet & set2) const {
422  BitSet out_set(*this);
423  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] & set2.bit_set[i];
424  return out_set;
425  }
426 
428  BitSet OR(const BitSet & set2) const {
429  BitSet out_set(*this);
430  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] | set2.bit_set[i];
431  return out_set;
432  }
433 
435  BitSet NAND(const BitSet & set2) const {
436  BitSet out_set(*this);
437  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = ~(bit_set[i] & set2.bit_set[i]);
438  if (LAST_BIT > 0) out_set.bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT);
439  return out_set;
440  }
441 
443  BitSet NOR(const BitSet & set2) const {
444  BitSet out_set(*this);
445  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = ~(bit_set[i] | set2.bit_set[i]);
446  if (LAST_BIT > 0) out_set.bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT);
447  return out_set;
448  }
449 
451  BitSet XOR(const BitSet & set2) const {
452  BitSet out_set(*this);
453  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] ^ set2.bit_set[i];
454  return out_set;
455  }
456 
458  BitSet EQU(const BitSet & set2) const {
459  BitSet out_set(*this);
460  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = ~(bit_set[i] ^ set2.bit_set[i]);
461  if (LAST_BIT > 0) out_set.bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT);
462  return out_set;
463  }
464 
465 
468  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~bit_set[i];
469  if (LAST_BIT > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT);
470  return *this;
471  }
472 
474  BitSet & AND_SELF(const BitSet & set2) {
475  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] & set2.bit_set[i];
476  return *this;
477  }
478 
480  BitSet & OR_SELF(const BitSet & set2) {
481  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] | set2.bit_set[i];
482  return *this;
483  }
484 
486  BitSet & NAND_SELF(const BitSet & set2) {
487  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~(bit_set[i] & set2.bit_set[i]);
488  if (LAST_BIT > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT);
489  return *this;
490  }
491 
493  BitSet & NOR_SELF(const BitSet & set2) {
494  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~(bit_set[i] | set2.bit_set[i]);
495  if (LAST_BIT > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT);
496  return *this;
497  }
498 
500  BitSet & XOR_SELF(const BitSet & set2) {
501  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] ^ set2.bit_set[i];
502  return *this;
503  }
504 
506  BitSet & EQU_SELF(const BitSet & set2) {
507  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~(bit_set[i] ^ set2.bit_set[i]);
508  if (LAST_BIT > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT);
509  return *this;
510  }
511 
513  BitSet SHIFT(const int shift_size) const {
514  BitSet out_set(*this);
515  if (shift_size > 0) out_set.ShiftRight((uint32_t) shift_size);
516  else if (shift_size < 0) out_set.ShiftLeft((uint32_t) (-shift_size));
517  return out_set;
518  }
519 
521  BitSet & SHIFT_SELF(const int shift_size) {
522  if (shift_size > 0) ShiftRight((uint32_t) shift_size);
523  else if (shift_size < 0) ShiftLeft((uint32_t) -shift_size);
524  return *this;
525  }
526 
528  BitSet operator~() const { return NOT(); }
529 
531  BitSet operator&(const BitSet & ar2) const { return AND(ar2); }
532 
534  BitSet operator|(const BitSet & ar2) const { return OR(ar2); }
535 
537  BitSet operator^(const BitSet & ar2) const { return XOR(ar2); }
538 
540  BitSet operator<<(const size_t shift_size) const { return SHIFT(-(int)shift_size); }
541 
543  BitSet operator>>(const size_t shift_size) const { return SHIFT((int)shift_size); }
544 
546  const BitSet & operator&=(const BitSet & ar2) { return AND_SELF(ar2); }
547 
549  const BitSet & operator|=(const BitSet & ar2) { return OR_SELF(ar2); }
550 
552  const BitSet & operator^=(const BitSet & ar2) { return XOR_SELF(ar2); }
553 
555  const BitSet & operator<<=(const size_t shift_size) { return SHIFT_SELF(-(int)shift_size); }
556 
558  const BitSet & operator>>=(const size_t shift_size) { return SHIFT_SELF((int)shift_size); }
559 
561  constexpr static size_t size() { return NUM_BITS; }
562 
564  inline bool all() const { return All(); }
565 
567  inline bool any() const { return Any(); }
568 
570  inline bool none() const { return !Any(); }
571 
573  inline size_t count() const { return CountOnes_Mixed(); }
574 
576  inline BitSet & flip() { return Toggle(); }
577 
579  inline BitSet & flip(size_t pos) { return Toggle(pos); }
580 
582  inline BitSet & flip(size_t start, size_t end) { return Toggle(start, end); }
583  };
584 
585  template <size_t NUM_BITS1, size_t NUM_BITS2>
588  out_bits.Import(in2);
589  out_bits <<= NUM_BITS1;
590  out_bits |= in2.template Export<NUM_BITS1+NUM_BITS2>();
591  }
592 
594  template <size_t NUM_BITS>
595  double SimpleMatchCoeff(const BitSet<NUM_BITS> & in1, const BitSet<NUM_BITS> & in2) {
596  emp_assert(NUM_BITS > 0); // TODO: can be done with XOR
597  return (double)((in1 & in2).CountOnes() + (~in1 & ~in2).CountOnes()) / (double)NUM_BITS;
598  }
599 
600 }
601 
602 template <size_t NUM_BITS> std::ostream & operator<<(std::ostream & out, const emp::BitSet<NUM_BITS> & _bit_set) {
603  _bit_set.Print(out);
604  return out;
605 }
606 
607 
608 
609 #endif
Useful mathematical functions (that are constexpr when possible.)
BitSet operator&(const BitSet &ar2) const
Operator bitwise AND...
Definition: BitSet.h:531
bool All() const
Return true if ALL bits in the BitSet are one, else return false.
Definition: BitSet.h:315
size_t CountOnes_Sparse() const
Count 1&#39;s by looping through once for each bit equal to 1.
Definition: BitSet.h:348
void SetByte(size_t index, uint8_t value)
Set the full byte starting at the bit at the specified index.
Definition: BitSet.h:271
BitSet & EQU_SELF(const BitSet &set2)
Perform a Boolean EQU with a second BitSet, store result here, and return this object.
Definition: BitSet.h:506
bool operator>=(const BitSet &in_set) const
Compare two BitSet objects, based on the associated binary value.
Definition: BitSet.h:217
bool Get(size_t index) const
Retrieve the bit as a specified index.
Definition: BitSet.h:223
void Set(size_t index, bool value)
Set the bit as a specified index.
Definition: BitSet.h:231
bool operator<=(const BitSet &in_set) const
Compare two BitSet objects, based on the associated binary value.
Definition: BitSet.h:202
BitSet operator~() const
Operator bitwise NOT...
Definition: BitSet.h:528
BitSet operator|(const BitSet &ar2) const
Operator bitwise OR...
Definition: BitSet.h:534
bool any() const
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:567
BitSet(const BitSet &in_set)
Copy constructor from another BitSet.
Definition: BitSet.h:144
BitSet & AND_SELF(const BitSet &set2)
Perform a Boolean AND with a second BitSet, store result here, and return this object.
Definition: BitSet.h:474
size_t CountOnes() const
Count the number of ones in the BitSet using bit tricks for a speedup.
Definition: BitSet.h:371
size_t count() const
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:573
BitSet & NAND_SELF(const BitSet &set2)
Perform a Boolean NAND with a second BitSet, store result here, and return this object.
Definition: BitSet.h:486
void PrintArray(std::ostream &out=std::cout) const
Print all bits from smallest to largest, as if this were an array, not a bit representation.
Definition: BitSet.h:338
BitSet NAND(const BitSet &set2) const
Perform a Boolean NAND with a second BitSet and return the result.
Definition: BitSet.h:435
void Randomize(Random &random, const double p1=0.5)
Set all bits randomly, with a given probability of being a 1.
Definition: BitSet.h:159
BitSet XOR(const BitSet &set2) const
Perform a Boolean XOR with a second BitSet and return the result.
Definition: BitSet.h:451
BitSet< NUM_BITS2 > Export() const
Convert to a Bitset of a different size.
Definition: BitSet.h:175
A versatile and non-patterned pseudo-random-number generator (Mersenne Twister).
Definition: ce_random.h:52
BitSet operator^(const BitSet &ar2) const
Operator bitwise XOR...
Definition: BitSet.h:537
BitSet & Toggle()
Flip all bits in this BitSet.
Definition: BitSet.h:242
bool operator==(const BitSet &in_set) const
Test if two BitSet objects are identical.
Definition: BitSet.h:185
A set of simple functions to manipulate bitsets.
static constexpr size_t GetSize()
How many bits are in this BitSet?
Definition: BitSet.h:220
uint32_t GetUInt(size_t index) const
Get the 32-bit unsigned int; index in in 32-bit jumps (i.e., this is a field ID not bit id) ...
Definition: BitSet.h:280
bool operator<(const BitSet &in_set) const
Compare two BitSet objects, based on the associated binary value.
Definition: BitSet.h:193
BitSet & flip()
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:576
int PopBit()
Return index of first one in sequence (or -1 if no ones); change this position to zero...
Definition: BitSet.h:381
Definition: BitSet.h:33
emp::vector< size_t > GetOnes() const
Return a vector indicating the posistions of all ones in the BitSet.
Definition: BitSet.h:402
const BitSet & operator<<=(const size_t shift_size)
Compound operator shift left...
Definition: BitSet.h:555
BitSet & NOR_SELF(const BitSet &set2)
Perform a Boolean NOR with a second BitSet, store result here, and return this object.
Definition: BitSet.h:493
bool all() const
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:564
BitSet()
Constructor: Assume all zeroes in set.
Definition: BitSet.h:141
uint32_t GetUIntAtBit(size_t index)
Get the full 32-bit unsigned int starting from the bit at a specified index.
Definition: BitSet.h:292
BitSet & Toggle(size_t start, size_t end)
Flips all the bits in a range [start, end)
Definition: BitSet.h:254
bool operator>(const BitSet &in_set) const
Compare two BitSet objects, based on the associated binary value.
Definition: BitSet.h:214
bool Any() const
Return true if ANY bits in the BitSet are one, else return false.
Definition: BitSet.h:309
BitSet & SHIFT_SELF(const int shift_size)
Positive shifts go left and negative go right; store result here, and return this object...
Definition: BitSet.h:521
bool None() const
Return true if NO bits in the BitSet are one, else return false.
Definition: BitSet.h:312
BitSet & OR_SELF(const BitSet &set2)
Perform a Boolean OR with a second BitSet, store result here, and return this object.
Definition: BitSet.h:480
BitSet & flip(size_t pos)
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:579
uint8_t GetByte(size_t index) const
Get the full byte starting from the bit at a specified index.
Definition: BitSet.h:263
BitSet operator<<(const size_t shift_size) const
Operator shift left...
Definition: BitSet.h:540
void Print(std::ostream &out=std::cout) const
Print all bits to the provided output stream.
Definition: BitSet.h:333
BitSet & operator=(const BitSet< NUM_BITS > &in_set)
Assignment operator.
Definition: BitSet.h:153
A versatile and non-patterned pseudo-random-number generator.
BitSet & flip(size_t start, size_t end)
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:582
bool none() const
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:570
BitSet AND(const BitSet &set2) const
Perform a Boolean AND with a second BitSet and return the result.
Definition: BitSet.h:421
uint32_t GetValueAtBit(size_t index)
Get OUT_BITS bits starting from the bit at a specified index (max 32)
Definition: BitSet.h:303
void SetUInt(size_t index, uint32_t value)
Set the 32-bit unsigned int; index in in 32-bit jumps (i.e., this is a field ID not bit id) ...
Definition: BitSet.h:286
int FindBit() const
Return the index of the first one in the sequence; return -1 if no ones are available.
Definition: BitSet.h:374
BitSet EQU(const BitSet &set2) const
Perform a Boolean EQU with a second BitSet and return the result.
Definition: BitSet.h:458
BitSet(Random &random, const double p1=0.5)
Constructor to generate a random BitSet.
Definition: BitSet.h:147
BitSet & Import(const BitSet< NUM_BITS2 > &in_set)
Assign from a BitSet of a different size.
Definition: BitSet.h:165
static constexpr size_t size()
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:561
double SimpleMatchCoeff(const BitSet< NUM_BITS > &in1, const BitSet< NUM_BITS > &in2)
Computes simple matching coefficient (https://en.wikipedia.org/wiki/Simple_matching_coefficient).
Definition: BitSet.h:595
If we are in emscripten, make sure to include the header.
Definition: array.h:37
const BitSet & operator^=(const BitSet &ar2)
Compound operator bitwise XOR...
Definition: BitSet.h:552
bool operator!=(const BitSet &in_set) const
Test if two BitSet objects are different.
Definition: BitSet.h:211
BitSet OR(const BitSet &set2) const
Perform a Boolean OR with a second BitSet and return the result.
Definition: BitSet.h:428
BitSet< NUM_BITS1+NUM_BITS2 > join(const BitSet< NUM_BITS1 > &in1, const BitSet< NUM_BITS2 > &in2)
Definition: BitSet.h:586
void SetAll()
Set all bits to one.
Definition: BitSet.h:327
~BitSet()=default
Destructor.
#define emp_assert(...)
Definition: assert.h:199
constexpr size_t find_bit(const uint64_t &val)
Return the position of the first one bit (in a 64-bit unsigned int)
Definition: bitset_utils.h:61
const BitSet & operator|=(const BitSet &ar2)
Compound operator bitwise OR...
Definition: BitSet.h:549
void PrintOneIDs(std::ostream &out=std::cout, char spacer=' ') const
Print the locations of all one bits, using the provided spacer (default is a single space) ...
Definition: BitSet.h:343
int FindBit(const size_t start_pos) const
Return index of first one in sequence AFTER start_pos (or -1 if no ones)
Definition: BitSet.h:392
BitSet & XOR_SELF(const BitSet &set2)
Perform a Boolean XOR with a second BitSet, store result here, and return this object.
Definition: BitSet.h:500
const BitSet & operator&=(const BitSet &ar2)
Compound operator bitwise AND...
Definition: BitSet.h:546
friend class BitProxy
Definition: BitSet.h:70
BitSet NOR(const BitSet &set2) const
Perform a Boolean NOR with a second BitSet and return the result.
Definition: BitSet.h:443
size_t CountOnes_Mixed() const
Count 1&#39;s in semi-parallel; fastest for even 0&#39;s & 1&#39;s.
Definition: BitSet.h:360
constexpr bool P(const double _p)
Definition: ce_random.h:216
BitSet operator>>(const size_t shift_size) const
Operator shift right...
Definition: BitSet.h:543
bool operator[](size_t index) const
Index into a const BitSet (i.e., cannot be set this way.)
Definition: BitSet.h:318
void Clear()
Set all bits to zero.
Definition: BitSet.h:324
BitSet & Toggle(size_t index)
Flip a single bit.
Definition: BitSet.h:245
BitSet & NOT_SELF()
Perform a Boolean NOT on this BitSet, store result here, and return this object.
Definition: BitSet.h:467
const BitSet & operator>>=(const size_t shift_size)
Compound operator shift right...
Definition: BitSet.h:558
BitSet SHIFT(const int shift_size) const
Positive shifts go left and negative go right (0 does nothing); return result.
Definition: BitSet.h:513
BitSet NOT() const
Perform a Boolean NOT on this BitSet and return the result.
Definition: BitSet.h:413
BitProxy operator[](size_t index)
Index into a BitSet, returning a proxy that will allow bit assignment to work.
Definition: BitSet.h:321