BitArray.hpp

An Array of a fixed number of bits; similar to std::bitset, but with extra bit magic. Status: RELEASE.

Todo:: Some of the functions allow a start bit and end bit; each of these should be checked to make sure that they will work if the start and end are part of the same byte. One option is to do this well ONCE with a macro that properly fills in the details.

namespace old

Functions

template<size_t NUM_BITS1, size_t NUM_BITS2> BitArray<NUM_BITS1 + NUM_BITS2> join(const BitArray<NUM_BITS1> &in1, const BitArray<NUM_BITS2> &in2)

template<size_t NUM_BITS, bool ZERO_LEFT> double SimpleMatchCoeff(const BitArray<NUM_BITS, ZERO_LEFT> &in1, const BitArray<NUM_BITS, ZERO_LEFT> &in2): Computes simple matching coefficient (https://en.wikipedia.org/wiki/Simple_matching_coefficient).

template<size_t NUM_BITS, bool ZERO_LEFT = true> class BitArray

#include <BitArray.hpp>

A fixed-sized (but arbitrarily large) array of bits, and optimizes operations on those bits to be as fast as possible.

Template Parameters:

NUM_BITS – is the fixed number of bits in this BitArray.
ZERO_LEFT – indicates the side that bit zero will be located.

Public Functions

inline explicit BitArray(bool init_val = false) noexcept: Constructor: Assume all bits set to zero.

inline BitArray(const this_t &_in) noexcept

explicit BitArray(const std::bitset<NUM_BITS> &bitset): Constructor to generate a BitArray from a std::bitset.

BitArray(const std::string &bitstring): Constructor to generate a BitArray from a string of ‘0’s and ‘1’s.

inline BitArray(const char *bitstring): Constructor to generate a BitArray from a literal string of ‘0’s and ‘1’s.

inline BitArray(Random &random): Constructor to generate a random BitArray (with equal prob of 0 or 1).

inline BitArray(Random &random, double p1): Constructor to generate a random BitArray with provided PROBABILITY of 1’s.

inline BitArray(Random &random, size_t num_ones): Constructor to generate a random BitArray with provided NUMBER of 1’s.

inline BitArray(Random &random, int num_ones): Constructor to generate a random BitArray with provided NUMBER of 1’s.

template<typename T> BitArray(const std::initializer_list<T> l): Constructor to fill in a bit array from a vector.

~BitArray() = default: Destructor.

inline BitArray &operator=(const this_t &in_bits) & noexcept: Assignment operator (no separate move operator since no resources to move…)

BitArray &operator=(const std::bitset<NUM_BITS> &bitset) &: Assignment operator from a std::bitset.

BitArray &operator=(const std::string &bitstring) &: Assignment operator from a string of ‘0’s and ‘1’s.

inline BitArray &operator=(const char *bitstring) &: Assignment operator from a literal string of ‘0’s and ‘1’s.

template<size_t FROM_BITS, bool FROM_LEFT> BitArray &Import(const BitArray<FROM_BITS, FROM_LEFT> &from_bits, const size_t from_bit = 0): Assignment from another BitArray of a different size.

template<size_t TO_BITS, bool TO_LEFT = ZERO_LEFT> BitArray<TO_BITS, TO_LEFT> Export(size_t start_bit = 0) const: Convert to a BitArray of a different size.

bool OK() const: For debugging: make sure that there are no obvious problems with a BitArray object.

bool Get(size_t index) const: Retrieve the bit as a specified index.

inline bool Has(size_t index) const: A safe version of Get() for indexing out of range. Useful for representing collections.

BitArray &Set(size_t index, bool value = true): Set the bit at a specified index.

BitArray &SetAll() noexcept: Set all bits to one.

inline BitArray &SetRange(size_t start, size_t stop): Set a range of bits to one: [start, stop)

inline BitArray &Clear() noexcept: Set all bits to zero.

inline BitArray &Clear(size_t index): Set specific bit to 0.

inline BitArray &Clear(const size_t start, const size_t stop): Set bits to 0 in the range [start, stop)

inline bool operator[](size_t index) const: Index into a const BitArray (i.e., cannot be set this way.)

inline BitProxy<this_t> operator[](size_t index): Index into a BitArray, returning a proxy that will allow bit assignment to work.

inline BitArray &Toggle(): Flip all bits in this BitArray.

BitArray &Toggle(size_t index): Flip a single bit.

inline BitArray &Toggle(size_t start, size_t stop): Flips all the bits in a range [start, stop)

inline bool Any() const: Return true if ANY bits in the BitArray are one, else return false.

inline bool None() const: Return true if NO bits in the BitArray are one, else return false.

inline bool All() const: Return true if ALL bits in the BitArray are one, else return false.

BitArray &Randomize(Random &random): Set all bits randomly, with a 50% probability of being a 0 or 1.

template<Random::Prob P> BitArray &RandomizeP(Random &random, const size_t start_pos = 0, const size_t stop_pos = NUM_BITS): Set all bits randomly, with probability specified at compile time.

BitArray &Randomize(Random &random, const double p, const size_t start_pos = 0, const size_t stop_pos = NUM_BITS): Set all bits randomly, with a given probability of being a one.

BitArray &ChooseRandom(Random &random, const size_t target_ones, const size_t start_pos = 0, const size_t stop_pos = NUM_BITS): Set all bits randomly, with a fixed number of them being ones.

BitArray &FlipRandom(Random &random, const double p, const size_t start_pos = 0, const size_t stop_pos = NUM_BITS): Flip random bits with a given probability.

BitArray &SetRandom(Random &random, const double p, const size_t start_pos = 0, const size_t stop_pos = NUM_BITS): Set random bits with a given probability (does not check if already set.)

BitArray &ClearRandom(Random &random, const double p, const size_t start_pos = 0, const size_t stop_pos = NUM_BITS): Unset random bits with a given probability (does not check if already zero.)

BitArray &FlipRandomCount(Random &random, const size_t num_bits): Flip a specified number of random bits.

Note

: This was previously called Mutate.

BitArray &SetRandomCount(Random &random, const size_t num_bits): Set a specified number of random bits (does not check if already set.)

BitArray &ClearRandomCount(Random &random, const size_t num_bits): Unset a specified number of random bits (does not check if already zero.)

template<size_t T2, bool L2> bool operator==(const BitArray<T2, L2> &in) const: Test if two BitArray objects are identical.

template<size_t T2, bool L2> inline bool operator!=(const BitArray<T2, L2> &in) const

template<size_t T2, bool L2> bool operator<(const BitArray<T2, L2> &in) const: Compare two BitArray objects, based on the associated binary value.

template<size_t T2, bool L2> inline bool operator>(const BitArray<T2, L2> &in) const

template<size_t T2, bool L2> inline bool operator<=(const BitArray<T2, L2> &in) const

template<size_t T2, bool L2> inline bool operator>=(const BitArray<T2, L2> &in) const

inline explicit operator bool() const: Casting a BitArray to bool identifies if ANY bits are set to 1.

uint8_t GetByte(size_t index) const: Retrieve the byte at the specified byte index.

std::span<const std::byte> GetBytes() const

Get a read-only view into the internal array used by BitArray.

Returns:: Read-only span of BitArray’s bytes.

inline Ptr<const unsigned char> RawBytes() const

Get a read-only pointer to the internal array used by BitArray.

Returns:: Read-only pointer to BitArray’s bytes.

void SetByte(size_t index, uint8_t value): Update the byte at the specified byte index.

double GetValue() const: Get the overall value of this BitArray, using a uint encoding, but including all bits and returning the value as a double.

template<typename T> T GetValueAtIndex(const size_t index) const: Get specified type at a given index (in steps of that type size)

inline std::size_t GetSizeT(size_t index) const: Retrieve a ‘size_t’ chunk from the current bits at the specified index.

inline uint8_t GetUInt8(size_t index) const: Retrieve the 8-bit uint from the specified uint index.

inline uint16_t GetUInt16(size_t index) const: Retrieve the 16-bit uint from the specified uint index.

inline uint32_t GetUInt32(size_t index) const: Retrieve the 32-bit uint from the specified uint index.

inline uint64_t GetUInt64(size_t index) const: Retrieve the 64-bit uint from the specified uint index.

inline uint32_t GetUInt(size_t index) const: By default, retrieve the 32-bit uint from the specified uint index.

template<typename T> void SetValueAtIndex(const size_t index, T value): Set specified type at a given index (in steps of that type size)

inline void SetUInt8(const size_t index, uint8_t value): Update the 8-bit uint at the specified uint index.

inline void SetUInt16(const size_t index, uint16_t value): Update the 16-bit uint at the specified uint index.

inline void SetUInt32(const size_t index, uint32_t value): Update the 32-bit uint at the specified uint index.

inline void SetUInt64(const size_t index, uint64_t value): Update the 64-bit uint at the specified uint index.

inline void SetUInt(const size_t index, uint32_t value): By default, update the 32-bit uint at the specified uint index.

template<typename T> T GetValueAtBit(const size_t index) const: Get specified type starting at a given BIT position.

inline uint8_t GetUInt8AtBit(size_t index) const: Retrieve the 8-bit uint from the specified uint index.

inline uint16_t GetUInt16AtBit(size_t index) const: Retrieve the 16-bit uint from the specified uint index.

inline uint32_t GetUInt32AtBit(size_t index) const: Retrieve the 32-bit uint from the specified uint index.

inline uint64_t GetUInt64AtBit(size_t index) const: Retrieve the 64-bit uint from the specified uint index.

inline uint32_t GetUIntAtBit(size_t index) const: By default, retrieve the 32-bit uint from the specified uint index.

template<typename T> void SetValueAtBit(const size_t index, T value)

inline void SetUInt8AtBit(const size_t index, uint8_t value): Update the 8-bit uint at the specified uint index.

inline void SetUInt16AtBit(const size_t index, uint16_t value): Update the 16-bit uint at the specified uint index.

inline void SetUInt32AtBit(const size_t index, uint32_t value): Update the 32-bit uint at the specified uint index.

inline void SetUInt64AtBit(const size_t index, uint64_t value): Update the 64-bit uint at the specified uint index.

inline void SetUIntAtBit(const size_t index, uint32_t value): By default, update the 32-bit uint at the specified uint index.

std::size_t Hash() const noexcept: A simple hash function for bit vectors.

size_t CountOnes() const: Count the number of ones in the BitArray.

size_t CountOnes_Sparse() const: Faster counting of ones for very sparse bit vectors.

inline size_t CountZeros() const: Count the number of zeros in the BitArray.

int FindOne() const: Return the position of the first one; return -1 if no ones in vector.

inline int FindBit() const: Deprecated: Return the position of the first one; return -1 if no ones in vector.

int FindOne(const size_t start_pos) const

Return the position of the first one after start_pos; return -1 if no ones in vector. You can loop through all 1-bit positions of a BitArray “bits” with:

for (int pos = bits.FindOne(); pos >= 0; pos = bits.FindOne(pos+1)) { … }

int FindBit(const size_t start_pos) const: Deprecated version of FindOne().

int FindMaxOne() const: Find the most-significant set-bit.

int PopOne(): Return the position of the first one and change it to a zero. Return -1 if no ones.

inline int PopBit(): Deprecated version of PopOne().

vector<size_t> GetOnes() const: Return positions of all ones.

size_t LongestSegmentOnes() const: Find the length of the longest continuous series of ones.

inline char GetAsChar(size_t id) const: Convert a specified bit to a character.

std::string ToString() const: Convert this BitArray to a string.

std::string ToArrayString() const: Convert this BitArray to an array-based string [index 0 on left].

std::string ToBinaryString() const: Convert this BitArray to a numerical string [index 0 on right].

std::string ToIDString(const std::string &spacer = " ") const: Convert this BitArray to a series of IDs.

std::string ToRangeString(const std::string &spacer = ",", const std::string &ranger = "-") const: Convert this BitArray to a series of IDs with ranges condensed.

inline void Print(std::ostream &out = std::cout) const: Regular print function (from least significant bit to most)

inline void PrintBinary(std::ostream &out = std::cout) const: Numerical print function (from most significant bit to least)

inline void PrintArray(std::ostream &out = std::cout) const: Print from smallest bit position to largest.

void PrintFields(std::ostream &out = std::cout, const std::string &spacer = " ") const: Print a space between each field (or other provided spacer)

void PrintDebug(std::ostream &out = std::cout) const: Print out details about the internals of the BitArray.

void PrintOneIDs(std::ostream &out = std::cout, const std::string &spacer = " ") const: Print the locations of all one bits, using the provided spacer (default is a single space)

void PrintAsRange(std::ostream &out = std::cout, const std::string &spacer = ",", const std::string &ranger = "-") const: Print the ones in a range format. E.g., 2-5,7,10-15.

BitArray &NOT_SELF(): Perform a Boolean NOT on this BitArray, store result here, and return this object.

BitArray &AND_SELF(const BitArray &array2): Perform a Boolean AND with a second BitArray, store result here, and return this object.

BitArray &OR_SELF(const BitArray &array2): Perform a Boolean OR with a second BitArray, store result here, and return this object.

BitArray &NAND_SELF(const BitArray &array2): Perform a Boolean NAND with a second BitArray, store result here, and return this object.

BitArray &NOR_SELF(const BitArray &array2): Perform a Boolean NOR with a second BitArray, store result here, and return this object.

BitArray &XOR_SELF(const BitArray &array2): Perform a Boolean XOR with a second BitArray, store result here, and return this object.

BitArray &EQU_SELF(const BitArray &array2): Perform a Boolean EQU with a second BitArray, store result here, and return this object.

inline BitArray NOT() const: Perform a Boolean NOT on this BitArray and return the result.

inline BitArray AND(const BitArray &in) const: Perform a Boolean AND with a second BitArray and return the result.

inline BitArray OR(const BitArray &in) const: Perform a Boolean OR with a second BitArray and return the result.

inline BitArray NAND(const BitArray &in) const: Perform a Boolean NAND with a second BitArray and return the result.

inline BitArray NOR(const BitArray &in) const: Perform a Boolean NOR with a second BitArray and return the result.

inline BitArray XOR(const BitArray &in) const: Perform a Boolean XOR with a second BitArray and return the result.

inline BitArray EQU(const BitArray &in) const: Perform a Boolean EQU with a second BitArray and return the result.

BitArray SHIFT(const int shift_size) const: Positive shifts go right and negative shifts go left (0 does nothing); return result.

BitArray &SHIFT_SELF(const int shift_size): Positive shifts go right and negative shifts go left (0 does nothing); store result here, and return this object.

BitArray &REVERSE_SELF(): Reverse the order of bits in the BitArray.

BitArray REVERSE() const: Reverse order of bits in the BitArray.

BitArray ROTATE(const int rotate_size) const: Positive rotates go left and negative rotates go left (0 does nothing); return result.

BitArray &ROTATE_SELF(const int rotate_size): Positive rotates go right and negative rotates go left (0 does nothing); store result here, and return this object.

template<size_t shift_size_raw> BitArray &ROTL_SELF(): Helper: call ROTATE with negative number instead.

template<size_t shift_size_raw> BitArray &ROTR_SELF(): Helper for calling ROTATE with positive number.

BitArray ADD(const BitArray &array2) const: Addition of two BitArrays. Wraps if it overflows. Returns result.

BitArray &ADD_SELF(const BitArray &array2): Addition of two BitArrays. Wraps if it overflows. Returns this object.

BitArray SUB(const BitArray &array2) const: Subtraction of two BitArrays. Wraps around if it underflows. Returns result.

BitArray &SUB_SELF(const BitArray &array2): Subtraction of two BitArrays. Wraps if it underflows. Returns this object.

inline BitArray operator~() const: Operator bitwise NOT…

inline BitArray operator&(const BitArray &ar2) const: Operator bitwise AND…

inline BitArray operator|(const BitArray &ar2) const: Operator bitwise OR…

inline BitArray operator^(const BitArray &ar2) const: Operator bitwise XOR…

inline BitArray operator<<(const size_t shift_size) const: Operator shift left…

inline BitArray operator>>(const size_t shift_size) const: Operator shift right…

inline BitArray &operator&=(const BitArray &ar2): Compound operator bitwise AND…

inline BitArray &operator|=(const BitArray &ar2): Compound operator bitwise OR…

inline BitArray &operator^=(const BitArray &ar2): Compound operator bitwise XOR…

inline BitArray &operator<<=(const size_t shift_size): Compound operator shift left…

inline BitArray &operator>>=(const size_t shift_size): Compound operator shift right…

inline BitArray operator+(const BitArray &ar2) const: Operator plus…

inline BitArray operator-(const BitArray &ar2) const: Operator minus…

inline const BitArray &operator+=(const BitArray &ar2): Compound operator plus…

inline const BitArray &operator-=(const BitArray &ar2): Compound operator minus…

inline bool all() const

inline bool any() const

inline bool none() const

inline size_t count() const

inline BitArray &flip()

inline BitArray &flip(size_t pos)

inline BitArray &flip(size_t start, size_t stop)

inline void reset()

inline void reset(size_t id)

inline void set()

inline void set(size_t id)

inline bool test(size_t index) const

template<class Archive> inline void serialize(Archive &ar)

template<typename FUN_T> BitArray<NUM_BITS, ZERO_LEFT> &ApplyRange(const FUN_T &fun, size_t start, size_t stop)

Public Static Functions

static inline constexpr size_t GetSize(): How many bits are in this BitArray?

static inline constexpr size_t GetNumBytes(): How many bytes are in this BitArray?

static inline constexpr double GetNumStates(): How many distinct values could be held in this BitArray?

static inline constexpr size_t size(): STL COMPATIBILITY A set of functions to allow drop-in replacement with std::bitset.

Private Types

using this_t = BitArray<NUM_BITS, ZERO_LEFT>

using field_t = typename uint_bit_count_t<NUM_BITS, size_t>

Private Functions

template<size_t IN_FIELDS, size_t COPY_FIELDS = NUM_FIELDS> inline BitArray &Copy(const field_t in_bits[IN_FIELDS]) noexcept

inline void ClearExcessBits() noexcept

template<typename FUN_T> inline BitArray &ApplyRange(const FUN_T &fun, size_t start, size_t stop)

inline Ptr<const unsigned char> BytePtr() const

inline Ptr<unsigned char> BytePtr()

void ShiftLeft(const size_t shift_size)

void ShiftRight(const size_t shift_size)

void RotateLeft(const size_t shift_size_raw): Helper: call ROTATE with negative number instead.

void RotateRight(const size_t shift_size_raw): Helper for calling ROTATE with positive number.

Private Members

field_t bits[NUM_FIELDS]: Fields to hold the actual bits for this BitArray.

Private Static Functions

static inline size_t FieldID(const size_t index)

static inline size_t ByteID(const size_t index)

static inline size_t FieldPos(const size_t index)

static inline size_t BytePos(const size_t index)

static inline size_t Byte2Field(const size_t index)

static inline size_t Byte2FieldPos(const size_t index)

Private Static Attributes

static constexpr size_t FIELD_BITS = 8 * sizeof(field_t)

static constexpr size_t NUM_FIELDS = (1 + ((NUM_BITS - 1) / FIELD_BITS))

static constexpr size_t TOTAL_BYTES = 1 + ((NUM_BITS - 1) >> 3)

static constexpr size_t LAST_FIELD = NUM_FIELDS - 1

static constexpr size_t FIELD_LOG2 = Log2(FIELD_BITS)

static constexpr field_t FIELD_LOG2_MASK = MaskLow<field_t>(FIELD_LOG2)

static constexpr size_t NUM_END_BITS = NUM_BITS & (FIELD_BITS - 1)

static constexpr size_t END_GAP = NUM_END_BITS ? (FIELD_BITS - NUM_END_BITS) : 0

static constexpr field_t END_MASK = MaskLow<field_t>(NUM_END_BITS)

static constexpr field_t FIELD_0 = (field_t)0: All bits in a field set to 0.

static constexpr field_t FIELD_1 = (field_t)1: Least significant bit set to 1.

static constexpr field_t FIELD_255 = (field_t)255: Least significant 8 bits set to 1.

static constexpr field_t FIELD_ALL = ~FIELD_0 : All bits in a field set to 1.

Friends

inline friend std::ostream &operator<<(std::ostream &out, const BitArray &bs): Overload ostream operator to return Print.