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.
- 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!)
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.
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)
-
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.
-
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()
Destructor.
-
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 &SetRange(size_t start, size_t stop, bool value = true)
Set a range of bits to value (default one): [start, stop)
-
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 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
Compare the would-be numerical values of two bit vectors.
-
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.
-
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 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().
-
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 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 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 size_t size() const
-
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 void reset()
-
inline void reset(size_t id)
-
inline void set()
-
inline void set(size_t id)
-
inline bool test(size_t index) const
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 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 size_t from_start, const size_t from_stop, const size_t to)
-
inline void ClearExcessBits()
-
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.
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 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)
-
inline BitVector(size_t in_num_bits = 0, bool init_val = false)
-
class BitVector