21 #include "../base/assert.h" 22 #include "../base/vector.h" 33 template <
size_t NUM_BITS>
class BitSet {
36 static const uint32_t NUM_FIELDS = 1 + ((NUM_BITS - 1) >> 5);
39 static const uint32_t LAST_BIT = NUM_BITS & 31;
42 static const uint32_t NUM_BYTES = 1 + ((NUM_BITS - 1) >> 3);
44 uint32_t bit_set[NUM_FIELDS];
58 bit_set.
Set(index, b);
63 operator bool()
const {
64 return bit_set.
Get(index);
72 inline static size_t FieldID(
const size_t index) {
76 inline static size_t FieldPos(
const size_t index) {
return index & 31; }
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; }
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];
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;
93 for (
int i = NUM_FIELDS - 1; i >= field_shift; --i) {
94 bit_set[i] = bit_set[i - field_shift];
96 for (
int i = field_shift - 1; i >= 0; i--) bit_set[i] = 0;
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);
106 bit_set[field_shift] <<= bit_shift;
110 if (LAST_BIT) { bit_set[NUM_FIELDS - 1] &= (1U << LAST_BIT) - 1U; }
115 void ShiftRight(
const uint32_t shift_size) {
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;
123 for (
size_t i = 0; i < (NUM_FIELDS - field_shift); ++i) {
124 bit_set[i] = bit_set[i + field_shift];
126 for (
size_t i = NUM_FIELDS - field_shift; i < NUM_FIELDS; i++) bit_set[i] = 0;
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);
135 bit_set[NUM_FIELDS - 1 - field_shift] >>= bit_shift;
154 Copy(in_set.bit_set);
160 for (
size_t i = 0; i < NUM_BITS; i++)
Set(i, random.
P(p1));
164 template <
size_t NUM_BITS2>
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);
169 for (
size_t i = MIN_FIELDS; i < NUM_FIELDS; i++) bit_set[i] = 0;
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;
179 for (
size_t i = 0; i < MIN_FIELDS; i++) out_bits.
SetUInt(i, bit_set[i]);
180 for (
size_t i = MIN_FIELDS; i < NUM_FIELDS; i++) out_bits.
SetUInt(i, 0);
186 for (
size_t i = 0; i < NUM_FIELDS; ++i) {
187 if (bit_set[i] != in_set.bit_set[i])
return false;
194 for (
int i = NUM_FIELDS-1; i >= 0; --i) {
195 if (bit_set[i] == in_set.bit_set[i])
continue;
196 return (bit_set[i] < in_set.bit_set[i]);
203 for (
int i = NUM_FIELDS-1; i >= 0; --i) {
204 if (bit_set[i] == in_set.bit_set[i])
continue;
205 return (bit_set[i] < in_set.bit_set[i]);
220 constexpr
static size_t GetSize() {
return NUM_BITS; }
223 bool Get(
size_t index)
const {
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;
231 void Set(
size_t index,
bool value) {
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;
237 if (value) bit_set[field_id] |= pos_mask;
238 else bit_set[field_id] &= ~pos_mask;
247 const size_t field_id = FieldID(index);
248 const size_t pos_id = FieldPos(index);
249 (bit_set[field_id] ^= (1 << pos_id));
256 for(
size_t index = start; index < end; index++) {
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;
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);
282 return bit_set[index];
288 bit_set[index] = value;
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);
302 template <
size_t OUT_BITS>
304 static_assert(OUT_BITS <= 32,
"Requesting too many bits to fit in a UInt");
305 return GetUIntAtBit(index) & MaskLow<uint32_t>(OUT_BITS);
309 bool Any()
const {
for (
auto i : bit_set)
if (i)
return true;
return false; }
315 bool All()
const {
return (~(*
this)).None(); }
324 void Clear() {
for (
auto & i : bit_set) i = 0U; }
328 for (
auto & i : bit_set) i = ~0U;
329 if (LAST_BIT > 0) { bit_set[NUM_FIELDS - 1] &= MaskLow<uint32_t>(LAST_BIT); }
333 void Print(std::ostream & out=std::cout)
const {
334 for (
size_t i = NUM_BITS; i > 0; i--) { out <<
Get(i-1); }
339 for (
size_t i = 0; i < NUM_BITS; i++) out <<
Get(i);
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; }
349 size_t bit_count = 0;
350 for (
auto i : bit_set) {
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;
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;
383 while (field_id < NUM_FIELDS && bit_set[field_id]==0) field_id++;
384 if (field_id == NUM_FIELDS)
return -1;
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);
395 for (
size_t i = start_pos; i < NUM_BITS; i++) {
396 if (
Get(i))
return (
int) i;
406 for (
size_t i = 0; i < NUM_BITS; i++) {
407 if (
Get(i)) out_set[cur_pos++] = i;
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);
423 for (
size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] & set2.bit_set[i];
430 for (
size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] | set2.bit_set[i];
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);
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);
453 for (
size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] ^ set2.bit_set[i];
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);
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);
475 for (
size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] & set2.bit_set[i];
481 for (
size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] | set2.bit_set[i];
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);
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);
501 for (
size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] ^ set2.bit_set[i];
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);
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));
522 if (shift_size > 0) ShiftRight((uint32_t) shift_size);
523 else if (shift_size < 0) ShiftLeft((uint32_t) -shift_size);
561 constexpr
static size_t size() {
return NUM_BITS; }
564 inline bool all()
const {
return All(); }
567 inline bool any()
const {
return Any(); }
585 template <
size_t NUM_BITS1,
size_t NUM_BITS2>
589 out_bits <<= NUM_BITS1;
590 out_bits |= in2.template Export<NUM_BITS1+NUM_BITS2>();
594 template <
size_t NUM_BITS>
597 return (
double)((in1 & in2).
CountOnes() + (~in1 & ~in2).
CountOnes()) / (
double)NUM_BITS;
602 template <
size_t NUM_BITS> std::ostream & operator<<(std::ostream & out, const emp::BitSet<NUM_BITS> & _bit_set) {
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'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
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's in semi-parallel; fastest for even 0's & 1'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