BitVector.hpp

A drop-in replacement for std::vector<bool>, with additional bitwise logic features. Status: RELEASE.

Todo:

Most of the operators don’t check to make sure that both BitVectors are the same size. We should create versions (Intersection() and Union()?) that adjust sizes if needed.

For large BitVectors we can use a factory to preserve/adjust bit info. That should be just as efficient than a reserve, but without the need to store extra in-class info.

Implement append(), resize(), push_bit(), insert(), remove()

Think about how iterators should work for BitVector. It should probably go bit-by-bit, but there are very few circumstances where that would be useful. Going through the positions of all ones would be more useful, but perhaps less intuitive.

Todo:: Do small BitVector optimization. Currently we have number of bits (8 bytes) and a pointer to the memory for the bitset (another 8 bytes), but we could use those 16 bytes as 1 byte of size info followed by 15 bytes of bitset (120 bits!)

Note

Compile with -O3 and -msse4.2 for fast bit counting.

Note

This class is 15-20% slower than BitSet, but more flexible & run-time configurable.

template<> struct hash<old::BitVector>

#include <BitVector.hpp>

Hash function to allow BitVector to be used with maps and sets. This is added to the std namespace so that BitVectors can be used in data structures that require hashing (such as unordered_map)

Public Functions

inline std::size_t operator()(const old::BitVector &bv) const

namespace old

class BitVector

#include <BitVector.hpp>

A drop-in replacement for std::vector<bool>, but with extra bitwise logic features.

This class stores an arbitrary number of bits in a set of “fields” (typically 32 bits or 64 bits per field, depending on which should be faster.) Individual bits can be extracted, -or- bitwise logic (including more complex bit magic) can be used on the groups of bits.

Public Functions

inline BitVector(size_t in_num_bits = 0, bool init_val = false): Build a new BitVector with specified bit count (default 0) and initialization (default 0)

template<typename T, typename std::enable_if<std::is_arithmetic<T>::value, int>::type = 0> inline BitVector(T in_num_bits): Anything not otherwise defined for first argument, convert to size_t.

inline BitVector(const BitVector &in): Copy constructor of existing bit field.

inline BitVector(BitVector &&in): Move constructor of existing bit field.

template<size_t NUM_BITS> inline explicit BitVector(const std::bitset<NUM_BITS> &bitset): Constructor to generate a BitVector from a std::bitset.

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

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

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

inline BitVector(size_t in_num_bits, Random &random, const double p1): Constructor to generate a random BitVector with provided prob of 1’s.

inline BitVector(size_t in_num_bits, Random &random, const size_t target_ones): Constructor to generate a random BitVector with provided number of 1’s.

inline BitVector(size_t in_num_bits, Random &random, const int target_ones): Constructor to generate a random BitVector with provided number of 1’s.

template<typename T> inline BitVector(const std::initializer_list<T> l): Initializer list constructor.

inline BitVector(const BitVector &in, size_t new_size): Copy, but with a resize.

inline ~BitVector(): Destructor.

inline BitVector &operator=(const BitVector &in) &: Assignment operator.

inline BitVector &operator=(BitVector &&in) &: Move operator.

template<size_t NUM_BITS> inline BitVector &operator=(const std::bitset<NUM_BITS> &bitset) &: Assignment operator from a std::bitset.

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

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

inline BitVector &Import(const BitVector &from_bv, const size_t from_bit = 0)

Assignment from another BitVector without changing size.

Assign from a BitVector of a different size.

inline BitVector Export(size_t out_size, size_t start_bit = 0) const

Convert to a BitVector of a different size.

Convert to a Bitset of a different size.

inline bool OK() const

inline size_t GetSize() const: How many bits do we currently have?

inline size_t GetNumBytes() const: How many bytes are in this BitVector? (includes empty field space)

inline double GetNumStates() const: How many distinct values could be held in this BitVector?

inline bool Get(size_t index) const: Retrieve the bit value from the specified index.

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

inline BitVector &Set(size_t index, bool value = true): Update the bit value at the specified index.

inline BitVector &SetAll(): Set all bits to 1.

inline BitVector &SetRange(size_t start, size_t stop, bool value = true): Set a range of bits to value (default one): [start, stop)

inline BitVector &Clear(): Set all bits to 0.

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

inline BitVector &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: Const index operator — return the bit at the specified position.

inline BitProxy<BitVector> operator[](size_t index): Index operator — return a proxy to the bit at the specified position so it can be an lvalue.

inline BitVector &Toggle(): Change every bit in the sequence.

inline BitVector &Toggle(size_t index): Change a specified bit to the opposite value.

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

inline bool Any() const: Return true if ANY bits are set to 1, otherwise return false.

inline bool None() const: Return true if NO bits are set to 1, otherwise return false.

inline bool All() const: Return true if ALL bits are set to 1, otherwise return false.

inline BitVector &Resize(size_t new_bits): Resize this BitVector to have the specified number of bits.

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

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

inline BitVector &Randomize(Random &random, const double p, const size_t start_pos = 0, size_t stop_pos = MAX_BITS)

Set all bits randomly, with a given probability of being a one.

Set all bits randomly, with a given probability of being on.

inline BitVector &ChooseRandom(Random &random, const size_t target_ones, const size_t start_pos = 0, size_t stop_pos = MAX_BITS)

Set all bits randomly, with a given number of ones.

Set all bits randomly, with a given number of them being on.

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

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

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

inline BitVector &FlipRandomCount(Random &random, const size_t target_bits): Flip a specified number of random bits.

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

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

inline bool operator==(const BitVector &in) const: Test if two bit vectors are identical.

inline bool operator!=(const BitVector &in) const

inline bool operator<(const BitVector &in) const: Compare the would-be numerical values of two bit vectors.

inline bool operator>(const BitVector &in) const

inline bool operator<=(const BitVector &in) const

inline bool operator>=(const BitVector &in) const

template<typename T> inline operator vector<T>(): Automatically convert BitVector to other vector types.

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

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

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

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

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

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

Get a read-only pointer to the internal array used by BitVector. (note that bits are NOT in order at the byte level!)

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

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

inline double GetValue() const

Get the overall value of this BitVector, using a uint encoding, but including all bits and returning the value as a double.

Get the overall value of this BitSet, using a uint encoding, but including all bits and returning the value as a double.

inline std::span<field_t> FieldSpan(): Return a span with all fields in order.

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

inline uint8_t GetUInt8(size_t index) const

inline uint16_t GetUInt16(size_t index) const

inline uint32_t GetUInt32(size_t index) const

inline uint64_t GetUInt64(size_t index) const

inline uint32_t GetUInt(size_t index) const

template<typename T> inline 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> inline T GetValueAtBit(const size_t index) const

Get specified type starting at a given BIT position.

Get the specified type starting from a given BIT position.

inline uint8_t GetUInt8AtBit(size_t index) const

inline uint16_t GetUInt16AtBit(size_t index) const

inline uint32_t GetUInt32AtBit(size_t index) const

inline uint64_t GetUInt64AtBit(size_t index) const

inline uint32_t GetUIntAtBit(size_t index) const

template<typename T> inline void SetValueAtBit(const size_t index, T value): Set the specified type starting from a given BIT position.

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.

inline std::size_t Hash(size_t start_field = 0) const: A simple hash function for bit vectors.

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

inline 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 BitVector.

inline bool PopBack()

Pop the last bit in the vector.

Returns:: value of the popped bit.

inline void PushBack(const bool bit = true, const size_t num = 1)

Push given bit(s) onto the back of a vector.

Parameters:

bit – value of bit to be pushed.
num – number of bits to be pushed.

inline void Insert(const size_t index, const bool val = true, const size_t num = 1)

Insert bit(s) into any index of vector using bit magic. Blog post on implementation reasoning: https://devolab.org/?p=2249

Parameters:

index – location to insert bit(s).
val – value of bit(s) to insert.
num – number of bits to insert, default 1.

inline void Delete(const size_t index, const size_t num = 1)

Delete bits from any index in a vector. TODO: consider a bit magic approach here.

Parameters:

index – location to delete bit(s).
num – number of bits to delete, default 1.

inline 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.

inline 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 BitVector “bv” with:

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

inline int FindOne(int start_pos) const: Special version of FindOne takes int; most common way to call.

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

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

inline 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().

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

template<typename T> inline vector<T> &GetOnes(vector<T> &out_vals) const

Collect positions of ones in the provided vector (allows id type choice)

Return positions of all ones using a specified type.

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

inline bool HasOverlap(const BitVector &in) const: Return true if any ones are in common with another BitVector.

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

inline std::string ToString() const

Convert this BitVector to a vector string [index 0 on left].

Convert this BitVector to a vector string [0 index on left].

inline std::string ToBinaryString() const

Convert this BitVector to a numerical string [index 0 on right].

Convert this BitVector to a numerical string [0 index on right].

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

inline std::string ToRangeString(const std::string &spacer = ",", const std::string &ranger = "-") const: Convert this BitVector 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.

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

inline void PrintDebug(std::ostream &out = std::cout) const

Print out details about the internals of the BitVector.

Print a space between each field (or other provided spacer)

inline void PrintOneIDs(std::ostream &out = std::cout, const std::string &spacer = " ") const: Print the positions of all one bits, spaces are the default separator.

inline 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.

inline BitVector &NOT_SELF(): Perform a Boolean NOT with this BitVector, store result here, and return this object.

inline BitVector &AND_SELF(const BitVector &bv2): Perform a Boolean AND with this BitVector, store result here, and return this object.

inline BitVector &OR_SELF(const BitVector &bv2): Perform a Boolean OR with this BitVector, store result here, and return this object.

inline BitVector &NAND_SELF(const BitVector &bv2): Perform a Boolean NAND with this BitVector, store result here, and return this object.

inline BitVector &NOR_SELF(const BitVector &bv2): Perform a Boolean NOR with this BitVector, store result here, and return this object.

inline BitVector &XOR_SELF(const BitVector &bv2): Perform a Boolean XOR with this BitVector, store result here, and return this object.

inline BitVector &EQU_SELF(const BitVector &bv2): Perform a Boolean EQU with this BitVector, store result here, and return this object.

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

inline BitVector AND(const BitVector &bv2) const: Perform a Boolean AND on this BitVector and return the result.

inline BitVector OR(const BitVector &bv2) const: Perform a Boolean OR on this BitVector and return the result.

inline BitVector NAND(const BitVector &bv2) const: Perform a Boolean NAND on this BitVector and return the result.

inline BitVector NOR(const BitVector &bv2) const: Perform a Boolean NOR on this BitVector and return the result.

inline BitVector XOR(const BitVector &bv2) const: Perform a Boolean XOR on this BitVector and return the result.

inline BitVector EQU(const BitVector &bv2) const: Perform a Boolean EQU on this BitVector and return the result.

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

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

inline BitVector &REVERSE_SELF(): Reverse the order of bits in the bitset.

inline BitVector REVERSE() const: Reverse order of bits in the bitset.

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

inline BitVector &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> inline BitVector &ROTL_SELF(): Helper: call ROTATE with negative number instead.

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

inline BitVector ADD(const BitVector &set2) const

Addition of two BitVectors. Wraps if it overflows. Returns result.

Addition of two Bitsets. Wraps if it overflows. Returns result.

inline BitVector &ADD_SELF(const BitVector &set2)

Addition of two BitVectors. Wraps if it overflows. Returns this object.

Addition of two Bitsets. Wraps if it overflows. Returns this object.

inline BitVector SUB(const BitVector &set2) const

Subtraction of two BitVectors. Wraps around if it underflows. Returns result.

Subtraction of two Bitsets. Wraps around if it underflows. Returns result.

inline BitVector &SUB_SELF(const BitVector &set2)

Subtraction of two BitVectors. Wraps if it underflows. Returns this object.

Subtraction of two Bitsets. Wraps if it underflows. Returns this object.

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

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

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

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

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

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

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

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

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

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

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

inline size_t size() const

inline void resize(std::size_t new_size)

inline void push_back(bool value)

inline auto at(size_t pos)

inline auto at(size_t pos) const

inline auto front()

inline auto front() const

inline auto back()

inline auto back() const

inline bool all() const

inline bool any() const

inline bool none() const

inline size_t count() const

inline BitVector &flip()

inline BitVector &flip(size_t pos)

inline BitVector &flip(size_t start, size_t end)

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<size_t NUM_BITS> BitVector &operator=(const std::bitset<NUM_BITS> &bitset) &: Assignment operator from a std::bitset.

Private Types

using field_t = size_t

Private Functions

inline size_t NumEndBits() const: Num bits used in partial field at the end; 0 if perfect fit.

inline size_t EndGap() const: How many EXTRA bits are leftover in the gap at the end?

inline field_t EndMask() const: A mask to cut off all of the final bits.

inline size_t NumFields() const: How many fields do we need for the current set of bits?

inline size_t LastField() const: What is the ID of the last occupied field?

inline size_t NumBytes() const: How many bytes are used for the current set of bits? (rounded up!)

inline size_t TotalBytes() const: How many bytes are allocated? (rounded up!)

inline void RawCopy(const Ptr<field_t> in)

inline void RawCopy(const size_t from_start, const size_t from_stop, const size_t to)

inline Ptr<unsigned char> BytePtr()

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

inline void ClearExcessBits()

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

inline void ShiftLeft(const size_t shift_size)

inline void ShiftRight(const size_t shift_size)

inline void RotateLeft(const size_t shift_size_raw)

Helper: call ROTATE with negative number instead.

Helper: call ROTATE with negative number.

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

Private Members

size_t num_bits: Total number of bits are we using.

Ptr<field_t> bits: Pointer to array with the status of each bit.

Private Static Functions

static inline constexpr size_t FieldID(const size_t index)

static inline constexpr size_t FieldPos(const size_t index)

static inline constexpr size_t Byte2Field(const size_t index)

static inline constexpr size_t Byte2FieldPos(const size_t index)

Private Static Attributes

static constexpr size_t FIELD_BITS = sizeof(field_t) * 8: Number of bits in a field.

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.

static constexpr size_t MAX_BITS = (size_t)-1: Value larger than any bit ID.

static constexpr size_t FIELD_LOG2 = static_cast<size_t>(Log2(FIELD_BITS))

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

Friends

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