GF2++
Loading...
Searching...
No Matches
gf2

The namespace for the gf2 library. More...

Classes

class  BitGauss
 The BitGauss class is a Gaussian elimination solver for systems of linear equations over GF(2).
It solves systems of the form \(A \cdot x = b\) where A is a square matrix, x is a vector of unknowns, and b is the known right-hand side vector. More...
class  BitLU
 The BitLU class provides the LU decomposition for bit-matrices. More...
class  BitMat
 A dynamically-sized matrix over GF(2) stored as a vector of bit-vectors representing the rows of the matrix. The row elements are compactly stored in standard vectors of primitive unsigned words whose type is given by the template parameter Word. More...
class  BitPoly
 A BitPoly represents a polynomial over GF(2) where we store the polynomial coefficients in a bit-vector.
The template parameter Word sets the unsigned word type used by the BitVec that stores the coefficients. More...
class  BitRef
 A BitRef is a proxy class to reference a single bit in a bit-store. More...
class  BitSet
 A fixed-size vector over GF(2) with N bit elements compactly stored in a standard vector of primitive unsigned words whose type is given by the template parameter Word. The elements in a bitset are initially all set to 0. More...
class  BitSpan
 A bit_span is a non-owning view of contiguous bits in a bit-store.
. More...
class  BitVec
 A dynamically-sized vector over GF(2) with bit elements compactly stored in a standard vector of primitive unsigned words whose type is given by the template parameter Word. More...
class  BitsIter
 Two iterators over all the bits in a bit-store — one const and the other non-const.
The BitStore::bits() & BitStore::bits() const methods return the appropriate iterator type. More...
class  SetBitsIter
 An iterator over the index locations of the set bits in a bit-store.
You get this iterator by calling the BitStore::set_bits() method. More...
class  UnsetBitsIter
 An iterator over the index locations of the unset bits in a bit-store.
You get this iterator by calling the BitStore::unset_bits() method. More...
class  WordsIter
 An iterator over the "words" underlying a bit-store.
You get this iterator by calling the BitStore::store_words() method. More...

Concepts

concept  BitStore
 A concept that is satisfied by all bit-vector-like types, which we refer to as bit-stores.
concept  Unsigned
 The Unsigned concept is the same as std::unsigned_integral. It is satisfied by all primitive unsigned integer types.

Typedefs

Shorthand Type Aliases.
using u8 = std::uint8_t
 Word type alias for an 8-bit unsigned integer.
using u16 = std::uint16_t
 Word type alias for a 16-bit unsigned integer.
using u32 = std::uint32_t
 Word type alias for a 32-bit unsigned integer.
using u64 = std::uint64_t
 Word type alias for a 64-bit unsigned integer.
using usize = std::size_t
 Word type alias for the platform's "native"-sized unsigned integer.

Functions

template<Unsigned Word, BitStore Rhs>
requires std::same_as<typename Rhs::word_type, Word>
constexpr auto dot (BitMat< Word > const &lhs, Rhs const &rhs)
 Bit-matrix, bit-store multiplication, M * v, returning a new bit-vector.
template<Unsigned Word, BitStore Rhs>
requires std::same_as<typename Rhs::word_type, Word>
constexpr auto operator* (BitMat< Word > const &lhs, Rhs const &rhs)
 Operator form for bit-matrix, bit-store multiplication, M * v, returning a new bit-vector.
template<Unsigned Word, BitStore Lhs>
requires std::same_as<typename Lhs::word_type, Word>
constexpr auto dot (Lhs const &lhs, BitMat< Word > const &rhs)
 Bit-vector, bit-matrix multiplication, v * M`, returning a new bit-vector.
template<Unsigned Word, BitStore Lhs>
requires std::same_as<typename Lhs::word_type, Word>
constexpr auto operator* (Lhs const &lhs, BitMat< Word > const &rhs)
 Operator form for bit-vector, bit-matrix multiplication, v * M, returning a new bit-vector.
template<Unsigned Word>
constexpr auto dot (BitMat< Word > const &lhs, BitMat< Word > const &rhs)
 Bit-matrix, bit-matrix multiplication, M * N, returning a new bit-matrix.
template<Unsigned Word>
constexpr auto operator* (BitMat< Word > const &lhs, BitMat< Word > const &rhs)
 Operator form for bit-matrix, bit-matrix multiplication, M * N, returning a new bit-matrix.
template<Unsigned Word, BitStore Rhs>
requires std::same_as<typename Rhs::word_type, Word>
std::string string_for (BitMat< Word > const &A, Rhs const &b)
 Returns a string that shows a bit-matrix and a bit-vector side-by-side.
template<Unsigned Word, BitStore Rhs>
requires std::same_as<typename Rhs::word_type, Word>
std::string string_for (BitMat< Word > const &A, Rhs const &b, Rhs const &c)
 Returns a string that shows a bit-matrix and two bit-vectors side-by-side.
template<Unsigned Word, BitStore Rhs>
requires std::same_as<typename Rhs::word_type, Word>
std::string string_for (BitMat< Word > const &A, Rhs const &b, Rhs const &c, Rhs const &d)
 Returns a string that shows a bit-matrix and three bit-vectors side-by-side.
template<Unsigned Word>
std::string string_for (BitMat< Word > const &A, BitMat< Word > const &B)
 Returns a string that shows two bit-matrices side-by-side.
template<Unsigned Word>
std::string string_for (BitMat< Word > const &A, BitMat< Word > const &B, BitMat< Word > const &C)
 Returns a string that shows three bit-matrices side-by-side.
Bit Access Functions:
template<BitStore Store>
constexpr bool get (Store const &store, usize i)
 Returns the bool value of the bit at index i in the given bit-store.
template<BitStore Store>
constexpr auto ref (Store &store, usize i)
 Returns a "reference" to the bit element i in the given bit-store.
template<BitStore Store>
constexpr bool front (Store const &store)
 Returns true if the first bit element is set, false otherwise.
template<BitStore Store>
constexpr bool back (Store const &store)
 Returns true if the final bit element is set, false otherwise.
template<BitStore Store>
constexpr auto & set (Store &store, usize i, bool value=true)
 Sets the bit-element at the given index to the specified boolean value and returns the store for chaining. The default value for value is true.
template<BitStore Store>
constexpr auto & flip (Store &store, usize i)
 Flips the value of the bit-element at the given index and returns the store for chaining.
template<BitStore Store>
constexpr auto & swap (Store &store, usize i0, usize i1)
 Swaps the bits in the bit-store at indices i0 and i1 and returns the store for chaining.
Store Queries:
template<BitStore Store>
constexpr bool is_empty (Store const &store)
 Returns true if the store is empty, false otherwise.
template<BitStore Store>
constexpr bool any (Store const &store)
 Returns true if at least one bit in the store is set, false otherwise.
template<BitStore Store>
constexpr bool all (Store const &store)
 Returns true if all bits in the store are set, false otherwise.
template<BitStore Store>
constexpr bool none (Store const &store)
 Returns true if no bits in the store are set, false otherwise.
Store Mutators:
template<BitStore Store>
constexpr auto & set_all (Store &store, bool value=true)
 Sets the bits in the store to the boolean value and returns the store for chaining.
template<BitStore Store>
constexpr auto & flip_all (Store &store)
 Flips the value of the bits in the store and returns the store for chaining.
Store Fills:
template<Unsigned Src, BitStore Store>
constexpr auto & copy (Src src, Store &store)
 Copies the bits from an unsigned integral src value and returns the store for chaining.
template<BitStore Src, BitStore Store>
constexpr auto & copy (Src const &src, Store &store)
 Copies the bits from an equal-sized src store and returns the store for chaining.
template<usize N, BitStore Store>
constexpr auto & copy (std::bitset< N > const &src, Store &store)
 Copies the bits of an equal-sized std::bitset and returns the store for chaining.
template<BitStore Store>
constexpr auto & copy (Store &store, std::invocable< usize > auto f)
 Fill the store by repeatedly calling f(i) and returns the store for chaining.
template<BitStore Store>
constexpr auto & random_fill (Store &store, double p=0.5, u64 seed=0)
 Fill the store with random bits and returns the store for chaining.
Bit Counts:
template<BitStore Store>
constexpr usize count_ones (Store const &store)
 Returns the number of set bits in the store.
template<BitStore Store>
constexpr usize count_zeros (Store const &store)
 Returns the number of unset bits in the store.
template<BitStore Store>
constexpr usize leading_zeros (Store const &store)
 Returns the number of leading zeros in the store.
template<BitStore Store>
constexpr usize trailing_zeros (Store const &store)
 Returns the number of trailing zeros in the store.
template<Unsigned Word>
constexpr u8 count_ones (Word word)
 Returns the number of set bits in an Unsigned.
template<Unsigned Word>
constexpr u8 count_zeros (Word word)
 Returns the number of unset bits in an Unsigned.
template<Unsigned Word>
constexpr u8 trailing_zeros (Word word)
 Returns the number of trailing zeros in an Unsigned.
template<Unsigned Word>
constexpr u8 leading_zeros (Word word)
 Returns the number of leading zeros in an Unsigned.
template<Unsigned Word>
constexpr u8 trailing_ones (Word word)
 Returns the number of trailing ones in an Unsigned.
template<Unsigned Word>
constexpr u8 leading_ones (Word word)
 Returns the number of leading ones in an Unsigned.
template<Unsigned Word>
constexpr std::optional< u8 > lowest_set_bit (Word word)
 Returns the index of the lowest set bit in an Unsigned or std::nullopt if no bits are set.
Set-bit indices:
template<BitStore Store>
constexpr std::optional< usize > first_set (Store const &store)
 Returns the index of the first set bit in the bit-store or {} if no bits are set.
template<BitStore Store>
constexpr std::optional< usize > last_set (Store const &store)
 Returns the index of the last set bit in the bit-store or {} if no bits are set.
template<BitStore Store>
constexpr std::optional< usize > next_set (Store const &store, usize index)
 Returns the index of the next set bit after index in the store or {} if no more set bits exist.
template<BitStore Store>
constexpr std::optional< usize > previous_set (Store const &store, usize index)
 Returns the index of the previous set bit before index in the store or {} if there are none.
Unset-bit Indices:
template<BitStore Store>
constexpr std::optional< usize > first_unset (Store const &store)
 Returns the index of the first unset bit in the bit-store or {} if no bits are unset.
template<BitStore Store>
constexpr std::optional< usize > last_unset (Store const &store)
 Returns the index of the last unset bit in the bit-store or {} if no bits are unset.
template<BitStore Store>
constexpr std::optional< usize > next_unset (Store const &store, usize index)
 Returns the index of the next unset bit after index in the store or {} if no more unset bits exist.
template<BitStore Store>
constexpr std::optional< usize > previous_unset (Store const &store, usize index)
 Returns the index of the previous unset bit before index in the store or {} if no more unset bits exist.
Store Iterators:
template<BitStore Store>
constexpr auto bits (Store const &store)
 Returns a const iterator over the bool values of the bits in the const bit-store.
template<BitStore Store>
constexpr auto bits (Store &store)
 Returns a non-const iterator over the values of the bits in the mutable bit-store.
template<BitStore Store>
constexpr auto set_bits (Store const &store)
 Returns an iterator over the indices of any set bits in the bit-store.
template<BitStore Store>
constexpr auto unset_bits (Store const &store)
 Returns an iterator over the indices of any unset bits in the bit-store.
template<BitStore Store>
constexpr auto store_words (Store const &store)
 Returns a const iterator over all the words underlying the bit-store.
template<BitStore Store>
constexpr auto to_words (Store const &store)
 Returns a copy of the words underlying this bit-store.
Store Spans:
template<BitStore Store>
static constexpr auto span (Store const &store, usize begin, usize end)
 Constructs a read-only bit-span over the const bit-store store for its bits in the range [begin, end).
template<BitStore Store>
static constexpr auto span (Store &store, usize begin, usize end)
 Constructs a bit-span over the bit-store store for its bits in the range [begin, end). This span allows modification of the underlying bits (unless its created from a span that is itself const).
Sub-vectors:
template<BitStore Store>
constexpr auto sub (Store const &store, usize begin, usize end)
 Returns a clone of the elements in the half-open range [begin, end) as a new bit-vector.
Store Splits and Joins:
template<BitStore Store>
constexpr void split (Store const &store, usize at, BitVec< typename Store::word_type > &left, BitVec< typename Store::word_type > &right)
 Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively. Clones of the parts are stored in the passed bit-vectors left and right.
template<BitStore Store>
constexpr auto split (Store const &store, usize at)
 Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively. Clones of the parts are returned as a pair of new bit-vectors [left, right].
template<BitStore Lhs, BitStore Rhs>
auto join (Lhs const &lhs, Rhs const &rhs)
 Returns a new bit-vector formed by joining two bit-stores lhs and rhs.
Interleaving With Zeros:
template<BitStore Store>
constexpr void riffle (Store const &store, BitVec< typename Store::word_type > &dst)
 Interleaves the bits of a bit-store with zeros storing the result into the passed bit-vector dst.
template<BitStore Store>
constexpr auto riffle (Store const &store)
 Returns a new bit-vector that is the result of riffling the bits in this bit-store with zeros.
String Representations:
template<BitStore Store>
static std::string to_binary_string (Store const &store, std::string_view sep="", std::string_view pre="", std::string_view post="")
 Returns a binary string representation of a store.
template<BitStore Store>
static std::string to_string (Store const &store, std::string_view sep="", std::string_view pre="", std::string_view post="")
 Returns a binary string representation of a store.
template<BitStore Store>
static std::string to_pretty_string (Store const &store)
 Returns a "pretty" string representation of a store.
template<BitStore Store>
static std::string to_hex_string (Store const &store)
 Returns the "hex" string representation of the bits in the bit-store.
template<BitStore Store>
static std::string describe (Store const &store)
 Detailed Description of a Bit-Store.
template<BitStore Store>
std::ostream & operator<< (Store const &store, std::ostream &s)
 The usual output stream operator for a bit-store.
The Equality Operator:
template<BitStore Lhs, BitStore Rhs>
constexpr bool operator== (Lhs const &lhs, Rhs const &rhs)
 Checks that any pair of bit-stores are equal in content.
In-place Bit Shifts:
template<BitStore Store>
constexpr void operator<<= (Store &store, usize shift)
 In-place left shift of a bit-store by shift bits.
template<BitStore Store>
constexpr void operator>>= (Store &store, usize shift)
 In-place right shift of a store by shift bits.
Out-of-place Bit Shifts:
template<BitStore Store>
constexpr auto operator<< (Store const &store, usize shift)
 Returns a new bit-vector that is the store shifted left by shift bits.
template<BitStore Store>
constexpr auto operator>> (Store const &store, usize shift)
 Returns a new bit-vector that is lhs shifted right by shift bits.
In-place Bitwise Operations:
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void operator^= (Lhs &lhs, Rhs const &rhs)
 In-place XOR of one bit-store with an equal-sized bit-store.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void operator&= (Lhs &lhs, Rhs const &rhs)
 In-place AND of one bit-store with an equal-sized bit-store.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void operator|= (Lhs &lhs, Rhs const &rhs)
 In-place OR of one bit-store with an equal-sized bit-store.
Out-of-place Bitwise Operations:
template<BitStore Store>
constexpr auto operator~ (Store const &store)
 Returns a new bit-vector that has the same bits as a bit-store but with all the bits flipped.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto operator^ (Lhs const &lhs, Rhs const &rhs)
 Returns the XOR of two equal-sized bit-stores as a new bit-vector.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto operator& (Lhs const &lhs, Rhs const &rhs)
 Returns the AND of two equal-sized bit-stores as a new bit-vector.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto operator| (Lhs const &lhs, Rhs const &rhs)
 Returns the OR of two equal-sized bit-stores as a new bit-vector.
In-place Arithmetic Operations:
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void operator+= (Lhs &lhs, Rhs const &rhs)
 In-place addition of one bit-store with an equal-sized bit-store.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void operator-= (Lhs &lhs, Rhs const &rhs)
 In-place difference of one bit-store with an equal-sized bit-store.
Out-of-place Arithmetic Operations:
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto operator+ (Lhs const &lhs, Rhs const &rhs)
 Adds two equal-sized bit-stores and returns the result as a new bit-vector.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto operator- (Lhs const &lhs, Rhs const &rhs)
 Subtracts two equal-sized bit-stores and returns the result as a new bit-vector.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr bool dot (Lhs const &lhs, Rhs const &rhs)
 Dot Products:
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr bool operator* (Lhs const &lhs, Rhs const &rhs)
 Operator * returns the dot product of lhs and rhs as a boolean value.
template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
auto convolve (Lhs const &lhs, Rhs const &rhs)
 Convolutions:
Constructors:
template<Unsigned Word>
constexpr Word with_set_bits (u8 begin, u8 end)
 Returns an Unsigned with the bits in the half-open range [begin, end) set to 1 and the others set to 0.
template<Unsigned Word>
constexpr Word with_unset_bits (u8 begin, u8 end)
 Returns an Unsigned with the bits in the half-open range [begin, end) set to 0 and the others set to 1.
Bit mutators:
template<Unsigned Word>
constexpr void set_bits (Word &word, u8 begin, u8 end)
 Sets the bits in the half-open range [begin, end) of word to one, leaving the others unchanged.
template<Unsigned Word>
constexpr void reset_bits (Word &word, u8 begin, u8 end)
 Resets the bits in the half-open range [begin, end) of word to zero, leaving the others unchanged.
template<Unsigned Word>
constexpr void set_except_bits (Word &word, u8 begin, u8 end)
 Sets the bits of word to 1 except for those in the half-open range [begin, end) which are unchanged.
template<Unsigned Word>
constexpr void reset_except_bits (Word &word, u8 begin, u8 end)
 Sets the bits of word to 0 except for those in the half-open range [begin, end) which are unchanged.
template<Unsigned Word>
constexpr Word reverse_bits (Word word)
 Returns a copy of word with all its bits reversed.
template<Unsigned Word, typename Other>
requires std::convertible_to<Other, Word>
constexpr void replace_bits (Word &word, u8 begin, u8 end, Other other)
 Replace the bits of word in the range [begin, end) with the bits from other leaving the rest unchanged.
Bit Riffling:
template<Unsigned Word>
constexpr std::pair< Word, Word > riffle (Word word)
 Riffles an Unsigned into a pair of others containing the bits in the original word interleaved with zeros.
Searches:
template<Unsigned Word>
constexpr std::optional< u8 > highest_set_bit (Word word)
 Returns the index of the highest set bit in an Unsigned or std::nullopt if no bits are set.
template<Unsigned Word>
constexpr std::optional< u8 > lowest_unset_bit (Word word)
 Returns the index of the lowest unset bit in an Unsigned or std::nullopt if there are no unset bits.
template<Unsigned Word>
constexpr std::optional< u8 > highest_unset_bit (Word word)
 Returns the index of the highest unset bit in an Unsigned or std::nullopt if there are none.
Stringification:
template<Unsigned Word>
static std::string to_binary_string (Word word)
 Returns the binary string representation of an Unsigned showing all the bits.
template<Unsigned Word>
static std::string to_hex_string (Word word)
 Returns the hex string representation of an Unsigned showing all the bits.
Bit Locations:
template<Unsigned Word>
constexpr usize words_needed (usize n_bits)
 Returns the number of Unsigneds needed to store n_bits bits.
template<Unsigned Word>
constexpr usize word_index (usize i)
 Returns the index of the Unsigned word holding bit element i.
template<Unsigned Word>
constexpr u8 bit_offset (usize i)
 Returns the bit position within the containing word for bit element i.
template<Unsigned Word>
constexpr std::pair< usize, u8 > index_and_offset (usize i)
 Returns a pair of the index of the word and the bit position within the word for bit element i.
template<Unsigned Word>
constexpr std::pair< usize, Word > index_and_mask (usize i)
 Returns a pair of the index of the word and a mask isolating bit element i.

Variables

static auto exit_on_assert_failure = true
 By default, all failed confirmations exit the program.
You can set this variable to false to prevent this behavior (useful for unit tests).
Variables:
template<Unsigned Word>
constexpr u8 BITS = std::numeric_limits<Word>::digits
 The number of bits in an Unsigned returned as a u8.
template<Unsigned Word>
constexpr Word ZERO = Word{0}
 The zero value for an Unsigned type.
template<Unsigned Word>
constexpr Word ONE = Word{1}
 The one value for an Unsigned type.
template<Unsigned Word>
constexpr Word MAX = std::numeric_limits<Word>::max()
 The Unsigned instance with all its bits set to 1.
template<Unsigned Word>
constexpr Word ALTERNATING = MAX<Word> / 3
 The Unsigned instance with alternating bits set to 0 and 1.

Detailed Description

The namespace for the gf2 library.

Function Documentation

◆ all()

template<BitStore Store>
bool gf2::all ( Store const & store)
constexpr

Returns true if all bits in the store are set, false otherwise.

Note
Empty stores have no set bits (logical connective for all is AND with identity true).

Example

BitVec v{3};
assert_eq(all(v), false);
set(v, 0);
set(v, 1);
set(v, 2);
assert_eq(all(v), true);
gf2::BitVec
A dynamically-sized vector over GF(2) with bit elements compactly stored in a standard vector of prim...
Definition BitVec.h:23
gf2::all
constexpr bool all(Store const &store)
Returns true if all bits in the store are set, false otherwise.
Definition BitStore.h:375
gf2::set
constexpr auto & set(Store &store, usize i, bool value=true)
Sets the bit-element at the given index to the specified boolean value and returns the store for chai...
Definition BitStore.h:244

◆ any()

template<BitStore Store>
bool gf2::any ( Store const & store)
constexpr

Returns true if at least one bit in the store is set, false otherwise.

Note
Empty stores have no set bits (logical connective for any is OR with identity false).

Example

BitVec v{10};
assert_eq(any(v), false);
set(v, 0);
assert_eq(any(v), true);
gf2::any
constexpr bool any(Store const &store)
Returns true if at least one bit in the store is set, false otherwise.
Definition BitStore.h:354

◆ back()

template<BitStore Store>
bool gf2::back ( Store const & store)
constexpr

Returns true if the final bit element is set, false otherwise.

Note
In debug mode the method panics of the store is empty.

Example

auto v = BitVec<>::ones(10);
assert_eq(back(v), true);
set_all(v, false);
assert_eq(back(v), false);
gf2::BitVec::ones
static constexpr BitVec ones(usize n)
Factory method to generate a bit-vector of length n where the elements are all 1.
Definition BitVec.h:202
gf2::back
constexpr bool back(Store const &store)
Returns true if the final bit element is set, false otherwise.
Definition BitStore.h:225
gf2::set_all
constexpr auto & set_all(Store &store, bool value=true)
Sets the bits in the store to the boolean value and returns the store for chaining.
Definition BitStore.h:428

◆ bit_offset()

template<Unsigned Word>
u8 gf2::bit_offset ( usize i)
constexpr

Returns the bit position within the containing word for bit element i.

Assumes we are holding bits in a sequence of Unsigned words.

Example

assert_eq(bit_offset<u8>(0), 0);
assert_eq(bit_offset<u8>(8), 0);
assert_eq(bit_offset<u8>(19), 3);
gf2::bit_offset
constexpr u8 bit_offset(usize i)
Returns the bit position within the containing word for bit element i.
Definition Unsigned.h:556

◆ bits() [1/2]

template<BitStore Store>
auto gf2::bits ( Store & store)
constexpr

Returns a non-const iterator over the values of the bits in the mutable bit-store.

You can use this iterator to iterate over the bits in the store to get or set the value of each bit.

Note
For the most part, try to avoid iterating through individual bits. It is much more efficient to use methods that work on whole words of bits at a time.

Example

auto v = BitVec<u8>::zeros(10);
for (auto&& bit : bits(v)) bit = true;
assert_eq(to_string(v), "1111111111");
gf2::BitVec::zeros
static constexpr BitVec zeros(usize n)
Factory method to generate a bit-vector of length n where the elements are all 0.
Definition BitVec.h:194
gf2::to_string
static std::string to_string(Store const &store, std::string_view sep="", std::string_view pre="", std::string_view post="")
Returns a binary string representation of a store.
Definition BitStore.h:1482
gf2::bits
constexpr auto bits(Store const &store)
Returns a const iterator over the bool values of the bits in the const bit-store.
Definition BitStore.h:1061

◆ bits() [2/2]

template<BitStore Store>
auto gf2::bits ( Store const & store)
constexpr

Returns a const iterator over the bool values of the bits in the const bit-store.

You can use this iterator to iterate over the bits in the store and get the values of each bit as a bool.

Note
For the most part, try to avoid iterating through individual bits. It is much more efficient to use methods that work on whole words of bits at a time.

Example

auto u = BitVec<u8>::ones(10);
for (auto&& bit : bits(u)) assert_eq(bit, true);

◆ convolve()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
auto gf2::convolve ( Lhs const & lhs,
Rhs const & rhs )

Convolutions:

Returns the convolution of two bit-stores as a new bit-vector.

The convolution of \(u\) and \(v\) is a vector with the elements \( (u * v)_k = \sum_j u_j v_{k-j+1} \) where the sum is taken over all \(j\) such that the indices in the formula are valid.

Example

auto lhs = BitVec<>::ones(3);
auto rhs = BitVec<>::ones(2);
auto result = convolve(lhs, rhs);
assert_eq(to_string(result), "1001");
gf2::convolve
auto convolve(Lhs const &lhs, Rhs const &rhs)
Convolutions:
Definition BitStore.h:2106

◆ copy() [1/4]

template<BitStore Src, BitStore Store>
auto & gf2::copy ( Src const & src,
Store & store )
constexpr

Copies the bits from an equal-sized src store and returns the store for chaining.

Note:

This is one of the few methods in the library that doesn't require the two stores to have the same word_type. You can use it to convert between different word_type stores (e.g., from BitVec<u32> to BitVec<u8>) as long as the sizes match.

Example

auto v = BitVec<u64>::ones(10);
assert_eq(to_string(v), "1111111111");
copy(BitVec<u8>::alternating(10), v);
assert_eq(to_string(v), "1010101010");
gf2::BitVec::alternating
static constexpr BitVec alternating(usize n)
Factory method to generate a bit-vector of length n looking like 101010....
Definition BitVec.h:237
gf2::copy
constexpr auto & copy(Src src, Store &store)
Copies the bits from an unsigned integral src value and returns the store for chaining.
Definition BitStore.h:474

◆ copy() [2/4]

template<Unsigned Src, BitStore Store>
auto & gf2::copy ( Src src,
Store & store )
constexpr

Copies the bits from an unsigned integral src value and returns the store for chaining.

Notes:

  1. The size of the store must match the number of bits in the source integer type.
  2. We allow any unsigned integral source, e.g. copying a single u64 into a BitVec<u8> of size 64.
  3. The least-significant bit of the source becomes the bit at index 0 in the store.

Example

BitVec<u8> v{16};
u16 src = 0b1010101010101010;
copy(src, v);
assert_eq(to_string(v), "0101010101010101");
BitVec<u32> w{16};
copy(src, w);
assert_eq(to_string(w), "0101010101010101");
gf2::u16
std::uint16_t u16
Word type alias for a 16-bit unsigned integer.
Definition Unsigned.h:33

◆ copy() [3/4]

template<usize N, BitStore Store>
auto & gf2::copy ( std::bitset< N > const & src,
Store & store )
constexpr

Copies the bits of an equal-sized std::bitset and returns the store for chaining.

Note
std::bitset prints its bit elements in bit-order which is the reverse of our convention.

Example

std::bitset<10> src{0b1010101010};
BitVec v{10};
copy(src, v);
assert_eq(to_string(v), "0101010101");

◆ copy() [4/4]

template<BitStore Store>
auto & gf2::copy ( Store & store,
std::invocable< usize > auto f )
constexpr

Fill the store by repeatedly calling f(i) and returns the store for chaining.

Example

BitVec v{10};
copy(v, [](usize i) { return i % 2 == 0; });
assert_eq(v.size(), 10);
assert_eq(to_string(v), "1010101010");
gf2::BitVec::size
constexpr usize size() const
Returns the number of bit-elements in the bit-vector.
Definition BitVec.h:50
gf2::usize
std::size_t usize
Word type alias for the platform's "native"-sized unsigned integer.
Definition Unsigned.h:42

◆ count_ones() [1/2]

template<BitStore Store>
usize gf2::count_ones ( Store const & store)
constexpr

Returns the number of set bits in the store.

Example

BitVec v{10};
assert_eq(count_ones(v), 0);
set(v, 0);
assert_eq(count_ones(v), 1);
gf2::count_ones
constexpr usize count_ones(Store const &store)
Returns the number of set bits in the store.
Definition BitStore.h:674

◆ count_ones() [2/2]

template<Unsigned Word>
u8 gf2::count_ones ( Word word)
constexpr

Returns the number of set bits in an Unsigned.

Example

assert_eq(count_ones(u8{0b0000'0000}), 0);
assert_eq(count_ones(u8{0b0000'0001}), 1);
assert_eq(count_ones(u8{0b0000'0010}), 1);
assert_eq(count_ones(u8{0b1111'1111}), 8);
gf2::u8
std::uint8_t u8
Word type alias for an 8-bit unsigned integer.
Definition Unsigned.h:30

◆ count_zeros() [1/2]

template<BitStore Store>
usize gf2::count_zeros ( Store const & store)
constexpr

Returns the number of unset bits in the store.

Example

BitVec v{10};
assert_eq(count_zeros(v), 10);
set(v, 0);
assert_eq(count_zeros(v), 9);
gf2::count_zeros
constexpr usize count_zeros(Store const &store)
Returns the number of unset bits in the store.
Definition BitStore.h:691

◆ count_zeros() [2/2]

template<Unsigned Word>
u8 gf2::count_zeros ( Word word)
constexpr

Returns the number of unset bits in an Unsigned.

Example

assert_eq(count_zeros(u8{0b0000'0000}), 8);
assert_eq(count_zeros(u8{0b0000'0001}), 7);
assert_eq(count_zeros(u8{0b0000'0010}), 7);
assert_eq(count_zeros(u8{0b1111'1111}), 0);

◆ describe()

template<BitStore Store>
std::string gf2::describe ( Store const & store)
static

Detailed Description of a Bit-Store.

This method is useful for debugging but you should not rely on the output format which may change.

◆ dot() [1/2]

template<Unsigned Word, BitStore Lhs>
requires std::same_as<typename Lhs::word_type, Word>
auto gf2::dot ( Lhs const & lhs,
BitMat< Word > const & rhs )
constexpr

Bit-vector, bit-matrix multiplication, v * M`, returning a new bit-vector.

Note
We store bit-matrices by rows so dot(BitMat, BitVec) will generally be faster than this.

◆ dot() [2/2]

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
bool gf2::dot ( Lhs const & lhs,
Rhs const & rhs )
constexpr

Dot Products:

Returns the dot product of lhs and rhs as a boolean value.

For any pair of vector-like types, the dot product is: \(u * v = \sum_i u_i v_i \) where the sum is over all the indices so the two operands must have the same length. In GF(2) the sum is modulo 2 and, by convention, the scalar output is a boolean value.

Note
In debug mode, this methods panics if the lengths of lhs and rhs do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
auto v2 = ~v1;
assert_eq(dot(v1, v1), true);
assert_eq(dot(v1, v2), false);
gf2::dot
constexpr auto dot(BitMat< Word > const &lhs, Rhs const &rhs)
Bit-matrix, bit-store multiplication, M * v, returning a new bit-vector.
Definition BitMat.h:2523

◆ first_set()

template<BitStore Store>
std::optional< usize > gf2::first_set ( Store const & store)
constexpr

Returns the index of the first set bit in the bit-store or {} if no bits are set.

Example

auto v = BitVec<u8>::zeros(37);
assert(first_set(v) == std::optional<usize>{});
set(v, 2);
assert(first_set(v) == std::optional<usize>{2});
set(v, 2, false);
assert(first_set(v) == std::optional<usize>{});
set(v, 27);
assert(first_set(v) == std::optional<usize>{27});
BitVec empty;
assert(first_set(empty) == std::optional<usize>{});
gf2::first_set
constexpr std::optional< usize > first_set(Store const &store)
Returns the index of the first set bit in the bit-store or {} if no bits are set.
Definition BitStore.h:770

◆ first_unset()

template<BitStore Store>
std::optional< usize > gf2::first_unset ( Store const & store)
constexpr

Returns the index of the first unset bit in the bit-store or {} if no bits are unset.

Example

auto v = BitVec<u8>::ones(37);
assert(first_unset(v) == std::optional<usize>{});
set(v,2,false);
assert(first_unset(v) == std::optional<usize>{2});
set(v,2);
assert(first_unset(v) == std::optional<usize>{});
set(v,27,false);
assert(first_unset(v) == std::optional<usize>{27});
BitVec empty;
assert(empty.first_unset() == std::optional<usize>{});
gf2::first_unset
constexpr std::optional< usize > first_unset(Store const &store)
Returns the index of the first unset bit in the bit-store or {} if no bits are unset.
Definition BitStore.h:903

◆ flip()

template<BitStore Store>
auto & gf2::flip ( Store & store,
usize i )
constexpr

Flips the value of the bit-element at the given index and returns the store for chaining.

Note
In debug mode the index is bounds-checked.

Example

auto v = BitVec<u8>::ones(10);
flip(v, 0);
assert_eq(to_string(v), "0111111111");
flip(v, 1);
assert_eq(to_string(v), "0011111111");
flip(v, 9);
assert_eq(to_string(v), "0011111110");
gf2::flip
constexpr auto & flip(Store &store, usize i)
Flips the value of the bit-element at the given index and returns the store for chaining.
Definition BitStore.h:269

◆ flip_all()

template<BitStore Store>
auto & gf2::flip_all ( Store & store)
constexpr

Flips the value of the bits in the store and returns the store for chaining.

Example

auto v = BitVec<u8>::zeros(10);
flip_all(v);
assert_eq(to_string(v), "1111111111");
gf2::flip_all
constexpr auto & flip_all(Store &store)
Flips the value of the bits in the store and returns the store for chaining.
Definition BitStore.h:445

◆ front()

template<BitStore Store>
bool gf2::front ( Store const & store)
constexpr

Returns true if the first bit element is set, false otherwise.

Note
In debug mode the method panics of the store is empty.

Example

auto v = BitVec<>::ones(10);
assert_eq(front(v), true);
set_all(v, false);
assert_eq(front(v), false);
gf2::front
constexpr bool front(Store const &store)
Returns true if the first bit element is set, false otherwise.
Definition BitStore.h:207

◆ get()

template<BitStore Store>
bool gf2::get ( Store const & store,
usize i )
constexpr

Returns the bool value of the bit at index i in the given bit-store.

Note
In debug mode the index i is bounds-checked.

Example

BitVec v{10};
assert_eq(get(v, 0), false);
set(v, 0);
assert_eq(get(v, 0), true);
gf2::get
constexpr bool get(Store const &store, usize i)
Returns the bool value of the bit at index i in the given bit-store.
Definition BitStore.h:163

◆ highest_set_bit()

template<Unsigned Word>
std::optional< u8 > gf2::highest_set_bit ( Word word)
constexpr

Returns the index of the highest set bit in an Unsigned or std::nullopt if no bits are set.

Example

assert(highest_set_bit(u8{0b0000'0000}) == std::optional<u8>{});
assert(highest_set_bit(u8{0b0000'0001}) == std::optional<u8>{0});
assert(highest_set_bit(u8{0b0000'0010}) == std::optional<u8>{1});
assert(highest_set_bit(u8{0b1000'0000}) == std::optional<u8>{7});
gf2::highest_set_bit
constexpr std::optional< u8 > highest_set_bit(Word word)
Returns the index of the highest set bit in an Unsigned or std::nullopt if no bits are set.
Definition Unsigned.h:438

◆ highest_unset_bit()

template<Unsigned Word>
std::optional< u8 > gf2::highest_unset_bit ( Word word)
constexpr

Returns the index of the highest unset bit in an Unsigned or std::nullopt if there are none.

Example

assert(highest_unset_bit(u8{0b1111'1111}) == std::optional<u8>{});
assert(highest_unset_bit(u8{0b1100'0000}) == std::optional<u8>{5});
assert(highest_unset_bit(u8{0b0001'0011}) == std::optional<u8>{7});
assert(highest_unset_bit(u8{0b1000'0000}) == std::optional<u8>{6});
gf2::highest_unset_bit
constexpr std::optional< u8 > highest_unset_bit(Word word)
Returns the index of the highest unset bit in an Unsigned or std::nullopt if there are none.
Definition Unsigned.h:470

◆ index_and_mask()

template<Unsigned Word>
std::pair< usize, Word > gf2::index_and_mask ( usize i)
constexpr

Returns a pair of the index of the word and a mask isolating bit element i.

Example

assert_eq(index_and_mask<u8>(0), (std::pair{0, 1}));
assert_eq(index_and_mask<u8>(8), (std::pair{1, 1}));
assert_eq(index_and_mask<u8>(19), (std::pair{2, 1 << 3}));
gf2::index_and_mask
constexpr std::pair< usize, Word > index_and_mask(usize i)
Returns a pair of the index of the word and a mask isolating bit element i.
Definition Unsigned.h:590

◆ index_and_offset()

template<Unsigned Word>
std::pair< usize, u8 > gf2::index_and_offset ( usize i)
constexpr

Returns a pair of the index of the word and the bit position within the word for bit element i.

  • Assumes we are holding bits in a sequence of Unsigned words.
  • Use with structured binding e.g. auto [index, offset] = gf2::index_and_offset<gf::u8>(i);

Example

assert_eq(index_and_offset<u8>(0), (std::pair{0, 0}));
assert_eq(index_and_offset<u8>(8), (std::pair{1, 0}));
assert_eq(index_and_offset<u8>(19), (std::pair{2, 3}));
gf2::index_and_offset
constexpr std::pair< usize, u8 > index_and_offset(usize i)
Returns a pair of the index of the word and the bit position within the word for bit element i.
Definition Unsigned.h:573

◆ is_empty()

template<BitStore Store>
bool gf2::is_empty ( Store const & store)
constexpr

Returns true if the store is empty, false otherwise.

Example

BitVec v;
assert_eq(is_empty(v), true);
BitVec u{10};
assert_eq(is_empty(u), false);
gf2::is_empty
constexpr bool is_empty(Store const &store)
Returns true if the store is empty, false otherwise.
Definition BitStore.h:337

◆ join()

template<BitStore Lhs, BitStore Rhs>
auto gf2::join ( Lhs const & lhs,
Rhs const & rhs )

Returns a new bit-vector formed by joining two bit-stores lhs and rhs.

This is one of the few methods in library that allows the operands to have different word types. The returned bit-vector will use the same word type as lhs.

Example

auto lhs = BitVec<u16>::zeros(12);
auto rhs = BitVec<u8>::ones(12);
auto v = join(lhs, rhs);
assert_eq(to_string(v), "000000000000111111111111");
gf2::join
auto join(Lhs const &lhs, Rhs const &rhs)
Returns a new bit-vector formed by joining two bit-stores lhs and rhs.
Definition BitStore.h:1330

◆ last_set()

template<BitStore Store>
std::optional< usize > gf2::last_set ( Store const & store)
constexpr

Returns the index of the last set bit in the bit-store or {} if no bits are set.

Example

auto v = BitVec<u8>::zeros(37);
assert(last_set(v) == std::optional<usize>{});
set(v, 2);
assert(last_set(v) == std::optional<usize>{2});
set(v, 27);
assert(last_set(v) == std::optional<usize>{27});
BitVec empty;
assert(last_set(empty) == std::optional<usize>{});
gf2::last_set
constexpr std::optional< usize > last_set(Store const &store)
Returns the index of the last set bit in the bit-store or {} if no bits are set.
Definition BitStore.h:795

◆ last_unset()

template<BitStore Store>
std::optional< usize > gf2::last_unset ( Store const & store)
constexpr

Returns the index of the last unset bit in the bit-store or {} if no bits are unset.

Example

auto v = BitVec<u8>::ones(37);
assert(last_unset(v) == std::optional<usize>{});
set(v,2, false);
assert(last_unset(v) == std::optional<usize>{2});
set(v,2);
assert(last_unset(v) == std::optional<usize>{});
set(v,27, false);
assert(last_unset(v) == std::optional<usize>{27});
BitVec empty;
assert(empty.last_unset() == std::optional<usize>{});
gf2::last_unset
constexpr std::optional< usize > last_unset(Store const &store)
Returns the index of the last unset bit in the bit-store or {} if no bits are unset.
Definition BitStore.h:936

◆ leading_ones()

template<Unsigned Word>
u8 gf2::leading_ones ( Word word)
constexpr

Returns the number of leading ones in an Unsigned.

Example

assert_eq(leading_ones(u8{0b0000'0000}), 0);
assert_eq(leading_ones(u8{0b0000'0001}), 0);
assert_eq(leading_ones(u8{0b1000'0010}), 1);
assert_eq(leading_ones(u8{0b1111'1111}), 8);
gf2::leading_ones
constexpr u8 leading_ones(Word word)
Returns the number of leading ones in an Unsigned.
Definition Unsigned.h:403

◆ leading_zeros() [1/2]

template<BitStore Store>
usize gf2::leading_zeros ( Store const & store)
constexpr

Returns the number of leading zeros in the store.

Example

BitVec v{37};
assert_eq(leading_zeros(v), 37);
set(v, 27);
assert_eq(leading_zeros(v), 27);
auto w = BitVec<u8>::ones(10);
assert_eq(leading_zeros(w), 0);
gf2::leading_zeros
constexpr usize leading_zeros(Store const &store)
Returns the number of leading zeros in the store.
Definition BitStore.h:708

◆ leading_zeros() [2/2]

template<Unsigned Word>
u8 gf2::leading_zeros ( Word word)
constexpr

Returns the number of leading zeros in an Unsigned.

Example

assert_eq(leading_zeros(u8{0b0000'0000}), 8);
assert_eq(leading_zeros(u8{0b0000'0001}), 7);
assert_eq(leading_zeros(u8{0b0000'0010}), 6);
assert_eq(leading_zeros(u8{0b1111'1111}), 0);

◆ lowest_set_bit()

template<Unsigned Word>
std::optional< u8 > gf2::lowest_set_bit ( Word word)
constexpr

Returns the index of the lowest set bit in an Unsigned or std::nullopt if no bits are set.

Example

assert(lowest_set_bit(u8{0b0000'0000}) == std::optional<u8>{});
assert(lowest_set_bit(u8{0b0000'0001}) == std::optional<u8>{0});
assert(lowest_set_bit(u8{0b0000'0010}) == std::optional<u8>{1});
assert(lowest_set_bit(u8{0b1000'0000}) == std::optional<u8>{7});
gf2::lowest_set_bit
constexpr std::optional< u8 > lowest_set_bit(Word word)
Returns the index of the lowest set bit in an Unsigned or std::nullopt if no bits are set.
Definition Unsigned.h:418

◆ lowest_unset_bit()

template<Unsigned Word>
std::optional< u8 > gf2::lowest_unset_bit ( Word word)
constexpr

Returns the index of the lowest unset bit in an Unsigned or std::nullopt if there are no unset bits.

Example

assert(lowest_unset_bit(u8{0b1111'1111}) == std::optional<u8>{});
assert(lowest_unset_bit(u8{0b0001'1000}) == std::optional<u8>{0});
assert(lowest_unset_bit(u8{0b0000'1001}) == std::optional<u8>{1});
assert(lowest_unset_bit(u8{0b1000'1111}) == std::optional<u8>{4});
gf2::lowest_unset_bit
constexpr std::optional< u8 > lowest_unset_bit(Word word)
Returns the index of the lowest unset bit in an Unsigned or std::nullopt if there are no unset bits.
Definition Unsigned.h:454

◆ next_set()

template<BitStore Store>
std::optional< usize > gf2::next_set ( Store const & store,
usize index )
constexpr

Returns the index of the next set bit after index in the store or {} if no more set bits exist.

Example

auto v = BitVec<u8>::zeros(37);
assert(next_set(v,0) == std::optional<usize>{});
set(v,2);
set(v,27);
assert(next_set(v,0) == std::optional<usize>{2});
assert(next_set(v,2) == std::optional<usize>{27});
assert(next_set(v,27) == std::optional<usize>{});
gf2::next_set
constexpr std::optional< usize > next_set(Store const &store, usize index)
Returns the index of the next set bit after index in the store or {} if no more set bits exist.
Definition BitStore.h:819

◆ next_unset()

template<BitStore Store>
std::optional< usize > gf2::next_unset ( Store const & store,
usize index )
constexpr

Returns the index of the next unset bit after index in the store or {} if no more unset bits exist.

Example

auto v = BitVec<u8>::ones(37);
assert(v.next_unset(0) == std::optional<usize>{});
set(v,2, false);
set(v,27, false);
assert(v.next_unset(0) == std::optional<usize>{2});
assert(v.next_unset(2) == std::optional<usize>{27});
assert(v.next_unset(27) == std::optional<usize>{});
BitVec empty;
assert(empty.next_unset(0) == std::optional<usize>{});
gf2::BitVec::next_unset
constexpr std::optional< usize > next_unset(usize index) const
Returns the index of the next unset bit after index in the store or {} if no more unset bits exist.
Definition BitVec.h:1365

◆ none()

template<BitStore Store>
bool gf2::none ( Store const & store)
constexpr

Returns true if no bits in the store are set, false otherwise.

Note
Empty store have no set bits (logical connective for none is AND with identity true).

Example

BitVec v{10};
assert_eq(none(v), true);
set(v,0);
assert_eq(none(v), false);
gf2::none
constexpr bool none(Store const &store)
Returns true if no bits in the store are set, false otherwise.
Definition BitStore.h:408

◆ operator&()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
auto gf2::operator& ( Lhs const & lhs,
Rhs const & rhs )
constexpr

Returns the AND of two equal-sized bit-stores as a new bit-vector.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
auto v2 = ~v1;
auto v3 = v1 & v2;
assert_eq(to_string(v3), "0000000000");

◆ operator&=()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
void gf2::operator&= ( Lhs & lhs,
Rhs const & rhs )
constexpr

In-place AND of one bit-store with an equal-sized bit-store.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
v1 &= ~v1;
assert_eq(to_string(v1), "0000000000");

◆ operator*() [1/2]

template<Unsigned Word, BitStore Lhs>
requires std::same_as<typename Lhs::word_type, Word>
auto gf2::operator* ( Lhs const & lhs,
BitMat< Word > const & rhs )
constexpr

Operator form for bit-vector, bit-matrix multiplication, v * M, returning a new bit-vector.

Note
We store bit-matrices by rows so dot(BitMat, BitVec) will generally be faster than this.

◆ operator*() [2/2]

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
bool gf2::operator* ( Lhs const & lhs,
Rhs const & rhs )
constexpr

Operator * returns the dot product of lhs and rhs as a boolean value.

For any pair of vector-like types, the dot product is: \(u * v = \sum_i u_i v_i \) where the sum is over all the indices so the two operands must have the same length. In GF(2) the sum is modulo 2 and, by convention, the scalar output is a boolean value.

Note
In debug mode, this methods panics if the lengths of lhs and rhs do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
auto v2 = ~v1;
assert_eq(v1*v1, true);
assert_eq(v1*v2, false);

◆ operator+()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
auto gf2::operator+ ( Lhs const & lhs,
Rhs const & rhs )
constexpr

Adds two equal-sized bit-stores and returns the result as a new bit-vector.

In GF(2) addition is the same as XOR.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
auto v2 = ~v1;
auto v3 = v1 + v2;
assert_eq(to_string(v3), "1111111111");

◆ operator+=()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
void gf2::operator+= ( Lhs & lhs,
Rhs const & rhs )
constexpr

In-place addition of one bit-store with an equal-sized bit-store.

In GF(2) addition is the same as XOR.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
v1 += ~v1;
assert_eq(to_string(v1), "1111111111");

◆ operator-()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
auto gf2::operator- ( Lhs const & lhs,
Rhs const & rhs )
constexpr

Subtracts two equal-sized bit-stores and returns the result as a new bit-vector.

In GF(2) addition is the same as XOR.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
auto v2 = ~v1;
auto v3 = v1 - v2;
assert_eq(to_string(v3), "1111111111");

◆ operator-=()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
void gf2::operator-= ( Lhs & lhs,
Rhs const & rhs )
constexpr

In-place difference of one bit-store with an equal-sized bit-store.

In GF(2) difference is the same as XOR.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
v1 -= ~v1;
assert_eq(to_string(v1), "1111111111");

◆ operator<<()

template<BitStore Store>
auto gf2::operator<< ( Store const & store,
usize shift )
constexpr

Returns a new bit-vector that is the store shifted left by shift bits.

Shifting is in vector-order so if v = [v0,v1,v2,v3] then v << 1 is [v1,v2,v3,0] with zeros added to the right. Left shifting in vector-order is the same as right shifting in bit-order.

Note
Only accessible bits are affected by the shift.

Example

auto v = BitVec<u8>::ones(20);
auto w = v << 8;
assert_eq(to_string(w), "11111111111100000000");

◆ operator<<=()

template<BitStore Store>
void gf2::operator<<= ( Store & store,
usize shift )
constexpr

In-place left shift of a bit-store by shift bits.

Shifting is in vector-order so if v = [v0,v1,v2,v3] then v <<= 1 is [v1,v2,v3,0] with zeros added to the right. Left shifting in vector-order is the same as right shifting in bit-order.

Note
Only accessible bits are affected by the shift.

Example

auto v = BitVec<u8>::ones(20);
v <<= 8;
assert_eq(to_string(v), "11111111111100000000");

◆ operator==()

template<BitStore Lhs, BitStore Rhs>
bool gf2::operator== ( Lhs const & lhs,
Rhs const & rhs )
constexpr

Checks that any pair of bit-stores are equal in content.

Equality here means that the two bit-stores have identical content and also the same underlying word_type word.

auto u = BitVec<u8>::ones(55);
auto v = BitVec<u8>::ones(55);
assert(u == v);
v.set(23, false);
assert(u != v);

◆ operator>>()

template<BitStore Store>
auto gf2::operator>> ( Store const & store,
usize shift )
constexpr

Returns a new bit-vector that is lhs shifted right by shift bits.

Shifting is in vector-order so if v = [v0,v1,v2,v3] then v >>= 1 is [0,v0,v1,v2] with zeros added to the left. Right shifting in vector-order is the same as left shifting in bit-order.

Note
Only accessible bits are affected by the shift.

Example

auto v = BitVec<u8>::ones(20);
auto w = v >> 8;
assert_eq(to_string(w), "00000000111111111111");

◆ operator>>=()

template<BitStore Store>
void gf2::operator>>= ( Store & store,
usize shift )
constexpr

In-place right shift of a store by shift bits.

Shifting is in vector-order so if v = [v0,v1,v2,v3] then v >>= 1 is [0,v0,v1,v2] with zeros added to the left. Right shifting in vector-order is the same as left shifting in bit-order.

Note
Only accessible bits are affected by the shift.

Example

auto v = BitVec<u8>::ones(20);
v >>= 8;
assert_eq(to_string(v), "00000000111111111111");

◆ operator^()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
auto gf2::operator^ ( Lhs const & lhs,
Rhs const & rhs )
constexpr

Returns the XOR of two equal-sized bit-stores as a new bit-vector.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
auto v2 = ~v1;
auto v3 = v1 ^ v2;
assert_eq(to_string(v3), "1111111111");

◆ operator^=()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
void gf2::operator^= ( Lhs & lhs,
Rhs const & rhs )
constexpr

In-place XOR of one bit-store with an equal-sized bit-store.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
v1 ^= ~v1;
assert_eq(to_string(v1), "1111111111");

◆ operator|()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
auto gf2::operator| ( Lhs const & lhs,
Rhs const & rhs )
constexpr

Returns the OR of two equal-sized bit-stores as a new bit-vector.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
auto v2 = ~v1;
auto v3 = v1 | v2;
assert_eq(to_string(v3), "1111111111");

◆ operator|=()

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
void gf2::operator|= ( Lhs & lhs,
Rhs const & rhs )
constexpr

In-place OR of one bit-store with an equal-sized bit-store.

Note
In debug mode, this method panics if the lengths of the two bit-stores do not match.

Example

auto v1 = BitVec<u8>::alternating(10);
v1 |= ~v1;
assert_eq(to_string(v1), "1111111111");

◆ operator~()

template<BitStore Store>
auto gf2::operator~ ( Store const & store)
constexpr

Returns a new bit-vector that has the same bits as a bit-store but with all the bits flipped.

Example

auto v = BitVec<u8>::alternating(10);
assert_eq(to_string(v), "1010101010");
auto w = ~v;
assert_eq(to_string(w), "0101010101");

◆ previous_set()

template<BitStore Store>
std::optional< usize > gf2::previous_set ( Store const & store,
usize index )
constexpr

Returns the index of the previous set bit before index in the store or {} if there are none.

Example

auto v = BitVec<u8>::zeros(37);
assert(previous_set(v,36) == std::optional<usize>{});
set(v,2);
set(v,27);
assert(previous_set(v,36) == std::optional<usize>{27});
assert(previous_set(v,27) == std::optional<usize>{2});
assert(previous_set(v,2) == std::optional<usize>{});
gf2::previous_set
constexpr std::optional< usize > previous_set(Store const &store, usize index)
Returns the index of the previous set bit before index in the store or {} if there are none.
Definition BitStore.h:857

◆ previous_unset()

template<BitStore Store>
std::optional< usize > gf2::previous_unset ( Store const & store,
usize index )
constexpr

Returns the index of the previous unset bit before index in the store or {} if no more unset bits exist.

Example

auto v = BitVec<u8>::ones(37);
assert(v.previous_unset(0) == std::optional<usize>{});
set(v,2, false);
set(v,27, false);
assert(v.previous_unset(36) == std::optional<usize>{27});
assert(v.previous_unset(27) == std::optional<usize>{2});
assert(v.previous_unset(2) == std::optional<usize>{});
BitVec empty;
assert(empty.previous_unset(0) == std::optional<usize>{});
gf2::BitVec::previous_unset
constexpr std::optional< usize > previous_unset(usize index) const
Returns the index of the previous unset bit before index in the store or {} if no more unset bits exi...
Definition BitVec.h:1381

◆ random_fill()

template<BitStore Store>
auto & gf2::random_fill ( Store & store,
double p = 0.5,
u64 seed = 0 )
constexpr

Fill the store with random bits and returns the store for chaining.

The default call random_fill() sets each bit to 1 with probability 0.5 (fair coin).

Parameters
pThe probability of the elements being 1 (defaults to a fair coin, i.e. 50-50).
seedThe seed to use for the random number generator (defaults to 0, which means use entropy).
Note
If p < 0 then the fill is all zeros, if p > 1 then the fill is all ones.

Example

BitVec u{10}, v{10};
u64 seed = 1234567890;
random_fill(u, 0.5, seed);
random_fill(v, 0.5, seed);
assert(u == v);
gf2::random_fill
constexpr auto & random_fill(Store &store, double p=0.5, u64 seed=0)
Fill the store with random bits and returns the store for chaining.
Definition BitStore.h:631
gf2::u64
std::uint64_t u64
Word type alias for a 64-bit unsigned integer.
Definition Unsigned.h:39

◆ ref()

template<BitStore Store>
auto gf2::ref ( Store & store,
usize i )
constexpr

Returns a "reference" to the bit element i in the given bit-store.

The returned object is a BitRef reference for the bit element at index rather than a true reference.

Note
The referenced bit-store must continue to exist while the BitRef is in use.
In debug mode the index i is bounds-checked.

Example

BitVec v{10};
ref(v, 2) = true;
assert(to_string(v) == "0010000000");
auto w = BitVec<>::ones(10);
ref(v, 3) = get(w, 3);
assert(to_string(v) == "0011000000");
ref(v, 4) |= get(w, 4);
assert(to_string(v) == "0011100000");
gf2::ref
constexpr auto ref(Store &store, usize i)
Returns a "reference" to the bit element i in the given bit-store.
Definition BitStore.h:189

◆ replace_bits()

template<Unsigned Word, typename Other>
requires std::convertible_to<Other, Word>
void gf2::replace_bits ( Word & word,
u8 begin,
u8 end,
Other other )
constexpr

Replace the bits of word in the range [begin, end) with the bits from other leaving the rest unchanged.

The range is half open so the end bit is not copied.

The Other type must be convertible to Unsigned, perhaps by just removing a const qualifier.

Note
In debug mode, the range `[begin, end) is checked for validity and the program exits on failure.

Example

u8 word = 0b1111'1111;
replace_bits(word, 1, 3, 0b0000'0000);
assert_eq(word, 0b1111'1001);
gf2::replace_bits
constexpr void replace_bits(Word &word, u8 begin, u8 end, Other other)
Replace the bits of word in the range [begin, end) with the bits from other leaving the rest unchange...
Definition Unsigned.h:265

◆ reset_bits()

template<Unsigned Word>
void gf2::reset_bits ( Word & word,
u8 begin,
u8 end )
constexpr

Resets the bits in the half-open range [begin, end) of word to zero, leaving the others unchanged.

Note
In debug mode, the range `[begin, end) is checked for validity and the program exits on failure.

Example

u8 word = 0b1111'1111;
reset_bits(word, 1, 3);
assert_eq(word, 0b1111'1001);
gf2::reset_bits
constexpr void reset_bits(Word &word, u8 begin, u8 end)
Resets the bits in the half-open range [begin, end) of word to zero, leaving the others unchanged.
Definition Unsigned.h:172

◆ reset_except_bits()

template<Unsigned Word>
void gf2::reset_except_bits ( Word & word,
u8 begin,
u8 end )
constexpr

Sets the bits of word to 0 except for those in the half-open range [begin, end) which are unchanged.

Note
In debug mode, the range `[begin, end) is checked for validity and the program exits on failure.

Example

u8 word = 0b1111'1111;
reset_except_bits(word, 1, 3);
assert_eq(word, 0b000'0110);
gf2::reset_except_bits
constexpr void reset_except_bits(Word &word, u8 begin, u8 end)
Sets the bits of word to 0 except for those in the half-open range [begin, end) which are unchanged.
Definition Unsigned.h:216

◆ reverse_bits()

template<Unsigned Word>
Word gf2::reverse_bits ( Word word)
constexpr

Returns a copy of word with all its bits reversed.

Reverses the order of bits in word. The least significant bit becomes the most significant bit, second least-significant bit becomes second most-significant bit, etc.

Example

u32 n32 = 0x12345678;
auto m32 = reverse_bits(n32);
assert_eq(m32, 0x1e6a2c48);
u64 n64 = 0x1234567890123456;
auto m64 = reverse_bits(n64);
assert_eq(m64, 0x6a2c48091e6a2c48);
u16 zero = 0;
assert_eq(reverse_bits(zero), 0);
gf2::reverse_bits
constexpr Word reverse_bits(Word word)
Returns a copy of word with all its bits reversed.
Definition Unsigned.h:243
gf2::u32
std::uint32_t u32
Word type alias for a 32-bit unsigned integer.
Definition Unsigned.h:36

◆ riffle() [1/3]

template<BitStore Store>
auto gf2::riffle ( Store const & store)
constexpr

Returns a new bit-vector that is the result of riffling the bits in this bit-store with zeros.

If bit-store has the bits abcde then the output bit-vector will have the bits a0b0c0d0e.

Note
There is no last zero bit in dst.

Example

auto v = BitVec<u8>::ones(10);
auto dst = riffle(v);
assert_eq(to_string(dst), "1010101010101010101");
gf2::riffle
constexpr void riffle(Store const &store, BitVec< typename Store::word_type > &dst)
Interleaves the bits of a bit-store with zeros storing the result into the passed bit-vector dst.
Definition BitStore.h:1362

◆ riffle() [2/3]

template<BitStore Store>
void gf2::riffle ( Store const & store,
BitVec< typename Store::word_type > & dst )
constexpr

Interleaves the bits of a bit-store with zeros storing the result into the passed bit-vector dst.

On return, dst will have the bits of this bit-store interleaved with zeros. For example, if this bit-store has the bits abcde then dst will have the bits a0b0c0d0e.

Note
There is no last zero bit in dst.

Example

auto v = BitVec<u8>::ones(10);
BitVec<u8> dst;
riffle(v, dst);
assert_eq(to_string(dst), "1010101010101010101");

◆ riffle() [3/3]

template<Unsigned Word>
std::pair< Word, Word > gf2::riffle ( Word word)
constexpr

Riffles an Unsigned into a pair of others containing the bits in the original word interleaved with zeros.

For example, if self is a u8 with the binary representation abcdefgh, then on return lo will have the bits 0a0b0c0d and hi will have the bits 0e0f0g0h. The lo and hi words are returned in a tuple.

Example

u8 word = 0b1111'1111;
auto [lo, hi] = riffle(word);
assert_eq(lo, 0b0101'0101);
assert_eq(hi, 0b0101'0101);

◆ set()

template<BitStore Store>
auto & gf2::set ( Store & store,
usize i,
bool value = true )
constexpr

Sets the bit-element at the given index to the specified boolean value and returns the store for chaining. The default value for value is true.

Note
In debug mode the index is bounds-checked.

Example

BitVec v{10};
assert_eq(get(v, 0), false);
set(v, 0);
assert_eq(get(v, 0), true);

◆ set_all()

template<BitStore Store>
auto & gf2::set_all ( Store & store,
bool value = true )
constexpr

Sets the bits in the store to the boolean value and returns the store for chaining.

By default, all bits are set to true.

Example

auto v = BitVec<u8>::zeros(10);
set_all(v);
assert_eq(to_string(v), "1111111111");

◆ set_bits() [1/2]

template<BitStore Store>
auto gf2::set_bits ( Store const & store)
constexpr

Returns an iterator over the indices of any set bits in the bit-store.

You can use this iterator to iterate over the set bits in the store and get the index of each bit.

Example

auto v = BitVec<u8>::alternating(10);
assert_eq(to_string(v), "1010101010");
auto indices = std::ranges::to<std::vector>(set_bits(v));
assert_eq(indices, (std::vector<usize>{0, 2, 4, 6, 8}));
gf2::set_bits
constexpr auto set_bits(Store const &store)
Returns an iterator over the indices of any set bits in the bit-store.
Definition BitStore.h:1097

◆ set_bits() [2/2]

template<Unsigned Word>
void gf2::set_bits ( Word & word,
u8 begin,
u8 end )
constexpr

Sets the bits in the half-open range [begin, end) of word to one, leaving the others unchanged.

Note
In debug mode, the range `[begin, end) is checked for validity and the program exits on failure.

Example

u8 word = 0b0000'0000;
set_bits(word, 1, 3);
assert_eq(word, 0b0000'0110);

◆ set_except_bits()

template<Unsigned Word>
void gf2::set_except_bits ( Word & word,
u8 begin,
u8 end )
constexpr

Sets the bits of word to 1 except for those in the half-open range [begin, end) which are unchanged.

Note
In debug mode, the range `[begin, end) is checked for validity and the program exits on failure.

Example

u8 word = 0b0000'0000;
set_except_bits(word, 1, 3);
assert_eq(word, 0b1111'1001);
gf2::set_except_bits
constexpr void set_except_bits(Word &word, u8 begin, u8 end)
Sets the bits of word to 1 except for those in the half-open range [begin, end) which are unchanged.
Definition Unsigned.h:194

◆ span() [1/2]

template<BitStore Store>
constexpr auto gf2::span ( Store & store,
usize begin,
usize end )
staticconstexpr

Constructs a bit-span over the bit-store store for its bits in the range [begin, end). This span allows modification of the underlying bits (unless its created from a span that is itself const).

It is the responsibility of the caller to ensure that the underlying bit-store continues to exist for as long as the BitSpan is in use.

Note
This method panics if the span range is invalid.

Example

const auto v = BitVec<>::alternating(10);
auto s = span(v, 1, 5);
assert_eq(to_string(s), "0101");
gf2::span
static constexpr auto span(Store const &store, usize begin, usize end)
Constructs a read-only bit-span over the const bit-store store for its bits in the range [begin,...
Definition BitStore.h:1176

◆ span() [2/2]

template<BitStore Store>
constexpr auto gf2::span ( Store const & store,
usize begin,
usize end )
staticconstexpr

Constructs a read-only bit-span over the const bit-store store for its bits in the range [begin, end).

It is the responsibility of the caller to ensure that the underlying bit-store continues to exist for as long as the BitSpan is in use.

Note
This method panics if the span range is invalid.

Example

const auto v = BitVec<>::alternating(10);
auto s = span(v, 1, 5);
assert_eq(to_string(s), "0101");

◆ split() [1/2]

template<BitStore Store>
auto gf2::split ( Store const & store,
usize at )
constexpr

Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively. Clones of the parts are returned as a pair of new bit-vectors [left, right].

On return, left is a clone of the bits from the start of the bit-vector up to but not including at and right contains the bits from at to the end of the bit-vector. This bit-vector itself is not modified.

Note
This method panics if the split point is beyond the end of the bit-vector.

Example

auto v = BitVec<>::alternating(10);
auto [left, right] = split(v, 5);
assert_eq(to_string(left), "10101");
assert_eq(to_string(right), "01010");
assert_eq(to_string(v), "1010101010");
gf2::split
constexpr void split(Store const &store, usize at, BitVec< typename Store::word_type > &left, BitVec< typename Store::word_type > &right)
Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively....
Definition BitStore.h:1283

◆ split() [2/2]

template<BitStore Store>
void gf2::split ( Store const & store,
usize at,
BitVec< typename Store::word_type > & left,
BitVec< typename Store::word_type > & right )
constexpr

Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively. Clones of the parts are stored in the passed bit-vectors left and right.

On return, left contains the bits from the start of the bit-vector up to but not including at and right contains the bits from at to the end of the bit-vector. This bit-vector itself is not modified.

This lets one reuse the left and right destinations without having to allocate new bit-vectors. This is useful when implementing iterative algorithms that need to split a bit-vector into two parts repeatedly.

Note
This method panics if the split point is beyond the end of the bit-vector.

Example

auto v = BitVec<>::alternating(10);
BitVec left, right;
split(v, 5, left, right);
assert_eq(to_string(left), "10101");
assert_eq(to_string(right), "01010");
assert_eq(to_string(v), "1010101010");

◆ store_words()

template<BitStore Store>
auto gf2::store_words ( Store const & store)
constexpr

Returns a const iterator over all the words underlying the bit-store.

You can use this iterator to iterate over the words in the store and read the Word value of each word. You cannot use this iterator to modify the words in the store.

Note
The words here may be a synthetic construct. The expectation is that the bit 0 in the store is located at the bit-location 0 of word(0). That is always the case for bit-vectors but bit-slices typically synthesise "words" on the fly from adjacent pairs of bit-vector words. Nevertheless, almost all the methods in BitStore are implemented efficiently by operating on those words.

Example

auto v = BitVec<u8>::ones(10);
assert_eq(to_string(v), "1111111111");
auto words = std::ranges::to<std::vector>(store_words(v));
assert_eq(words, (std::vector<u8>{0b1111'1111, 0b0000'0011}));
gf2::store_words
constexpr auto store_words(Store const &store)
Returns a const iterator over all the words underlying the bit-store.
Definition BitStore.h:1137

◆ sub()

template<BitStore Store>
auto gf2::sub ( Store const & store,
usize begin,
usize end )
constexpr

Returns a clone of the elements in the half-open range [begin, end) as a new bit-vector.

Note
This method panics if the range is not valid.

Example

auto v = BitVec<>::alternating(10);
auto s = sub(v,1,5);
assert_eq(to_string(s), "0101");
s.set_all();
assert_eq(to_string(s), "1111");
assert_eq(to_string(v), "1010101010");
gf2::sub
constexpr auto sub(Store const &store, usize begin, usize end)
Returns a clone of the elements in the half-open range [begin, end) as a new bit-vector.
Definition BitStore.h:1253

◆ swap()

template<BitStore Store>
auto & gf2::swap ( Store & store,
usize i0,
usize i1 )
constexpr

Swaps the bits in the bit-store at indices i0 and i1 and returns the store for chaining.

Note
In debug mode, panics if either of the indices is out of bounds.

Example

auto v = BitVec<>::zeros(10);
set(v, 0);
assert_eq(to_string(v), "1000000000");
swap(v, 0, 1);
assert_eq(to_string(v), "0100000000");
swap(v, 0, 1);
assert_eq(to_string(v), "1000000000");
swap(v, 0, 9);
assert_eq(to_string(v), "0000000001");
swap(v, 0, 9);
assert_eq(to_string(v), "1000000000");
gf2::swap
constexpr auto & swap(Store &store, usize i0, usize i1)
Swaps the bits in the bit-store at indices i0 and i1 and returns the store for chaining.
Definition BitStore.h:297

◆ to_binary_string() [1/2]

template<BitStore Store>
std::string gf2::to_binary_string ( Store const & store,
std::string_view sep = "",
std::string_view pre = "",
std::string_view post = "" )
static

Returns a binary string representation of a store.

The string is formatted as a sequence of 0s and 1s with the least significant bit on the right.

Parameters
storeThe bit-store to convert to a binary string.
sepThe separator between bit elements which defaults to no separator.
preThe prefix to add to the string which defaults to no prefix.
postThe postfix to add to the string which defaults to no postfix.

Example

BitVec v{10};
assert_eq(to_binary_string(v), "0000000000");
set(v, 0);
assert_eq(to_binary_string(v), "1000000000");
assert_eq(to_binary_string(v, ",", "[", "]"), "[1,0,0,0,0,0,0,0,0,0]");
gf2::to_binary_string
static std::string to_binary_string(Store const &store, std::string_view sep="", std::string_view pre="", std::string_view post="")
Returns a binary string representation of a store.
Definition BitStore.h:1431

◆ to_binary_string() [2/2]

template<Unsigned Word>
std::string gf2::to_binary_string ( Word word)
inlinestatic

Returns the binary string representation of an Unsigned showing all the bits.

Example

assert_eq(to_binary_string(u8{0b0000'0011}), "00000011");
assert_eq(to_binary_string(u8{0b1111'1111}), "11111111");

◆ to_hex_string() [1/2]

template<BitStore Store>
std::string gf2::to_hex_string ( Store const & store)
static

Returns the "hex" string representation of the bits in the bit-store.

The output is a string of hex characters without any spaces, commas, or other formatting.

The string may have a two character suffix of the form ".base" where base is one of 2, 4 or 8.
All hex characters encode 4 bits: "0X0" -> 0b0000, "0X1" -> 0b0001, ..., "0XF" -> 0b1111.
The three possible ".base" suffixes allow for bit-vectors whose length is not a multiple of 4.
Empty bit-vectors are represented as the empty string.

  • 0X1 is the hex representation of the bit-vector 0001 => length 4.
  • 0X1.8 is the hex representation of the bit-vector 001 => length 3.
  • 0X1.4 is the hex representation of the bit-vector 01 => length 2.
  • 0X1.2 is the hex representation of the bit-vector 1 => length 1.

The output is in vector-order. If "h0" is the first hex digit in the output string, you can print it as four binary digits v_0v_1v_2v_3. For example, if h0 = "A" which is 1010 in binary, then v = 1010.

Example

BitVec v0;
assert_eq(to_hex_string(v0), "");
auto v1 = BitVec<>::ones(4);
assert_eq(to_hex_string(v1), "F");
auto v2 = BitVec<>::ones(5);
assert_eq(to_hex_string(v2), "F1.2");
auto v3 = BitVec<>::alternating(8);
assert_eq(to_binary_string(v3), "10101010");
assert_eq(to_hex_string(v3), "AA");
gf2::to_hex_string
static std::string to_hex_string(Store const &store)
Returns the "hex" string representation of the bits in the bit-store.
Definition BitStore.h:1536

◆ to_hex_string() [2/2]

template<Unsigned Word>
std::string gf2::to_hex_string ( Word word)
inlinestatic

Returns the hex string representation of an Unsigned showing all the bits.

Example

assert_eq(to_hex_string(u8{0b0000'0011}), "03");
assert_eq(to_hex_string(u8{0b1111'1111}), "FF");

◆ to_pretty_string()

template<BitStore Store>
std::string gf2::to_pretty_string ( Store const & store)
static

Returns a "pretty" string representation of a store.

The output is a string of 0's and 1's with spaces between each bit, and the whole thing enclosed in square brackets.

Example

auto v = BitVec<>::alternating(10);
assert_eq(to_pretty_string(v), "[1,0,1,0,1,0,1,0,1,0]");
BitVec empty;
assert_eq(to_pretty_string(empty), "[]");
gf2::to_pretty_string
static std::string to_pretty_string(Store const &store)
Returns a "pretty" string representation of a store.
Definition BitStore.h:1500

◆ to_string()

template<BitStore Store>
std::string gf2::to_string ( Store const & store,
std::string_view sep = "",
std::string_view pre = "",
std::string_view post = "" )
static

Returns a binary string representation of a store.

The string is formatted as a sequence of 0s and 1s with the least significant bit on the right.

Parameters
storeThe bit-store to convert to a binary string.
sepThe separator between bit elements which defaults to no separator.
preThe prefix to add to the string which defaults to no prefix.
postThe postfix to add to the string which defaults to no postfix.

Example

BitVec v{10};
assert_eq(to_string(v), "0000000000");
set(v, 0);
assert_eq(to_string(v), "1000000000");
assert_eq(to_string(v, ",", "[", "]"), "[1,0,0,0,0,0,0,0,0,0]");

◆ to_words()

template<BitStore Store>
auto gf2::to_words ( Store const & store)
constexpr

Returns a copy of the words underlying this bit-store.

Note
The last word in the vector may not be fully occupied but unused slots will be all zeros.

Example

auto v = BitVec<u8>::ones(10);
auto words = to_words(v);
assert_eq(words, (std::vector<u8>{0b1111'1111, 0b0000'0011}));
gf2::to_words
constexpr auto to_words(Store const &store)
Returns a copy of the words underlying this bit-store.
Definition BitStore.h:1153

◆ trailing_ones()

template<Unsigned Word>
u8 gf2::trailing_ones ( Word word)
constexpr

Returns the number of trailing ones in an Unsigned.

Example

assert_eq(trailing_ones(u8{0b0000'0000}), 0);
assert_eq(trailing_ones(u8{0b0000'0001}), 1);
assert_eq(trailing_ones(u8{0b0000'0010}), 0);
assert_eq(trailing_ones(u8{0b1111'1111}), 8);
gf2::trailing_ones
constexpr u8 trailing_ones(Word word)
Returns the number of trailing ones in an Unsigned.
Definition Unsigned.h:388

◆ trailing_zeros() [1/2]

template<BitStore Store>
usize gf2::trailing_zeros ( Store const & store)
constexpr

Returns the number of trailing zeros in the store.

Example

auto v = BitVec<u8>::zeros(27);
assert_eq(trailing_zeros(v), 27);
set(v, 0);
assert_eq(trailing_zeros(v), 26);
gf2::trailing_zeros
constexpr usize trailing_zeros(Store const &store)
Returns the number of trailing zeros in the store.
Definition BitStore.h:729

◆ trailing_zeros() [2/2]

template<Unsigned Word>
u8 gf2::trailing_zeros ( Word word)
constexpr

Returns the number of trailing zeros in an Unsigned.

Example

assert_eq(trailing_zeros(u8{0b0000'0000}), 8);
assert_eq(trailing_zeros(u8{0b0000'0001}), 0);
assert_eq(trailing_zeros(u8{0b0000'0010}), 1);
assert_eq(trailing_zeros(u8{0b1111'1111}), 0);

◆ unset_bits()

template<BitStore Store>
auto gf2::unset_bits ( Store const & store)
constexpr

Returns an iterator over the indices of any unset bits in the bit-store.

You can use this iterator to iterate over the unset bits in the store and get the index of each bit.

Example

auto v = BitVec<u8>::alternating(10);
assert_eq(to_string(v), "1010101010");
auto indices = std::ranges::to<std::vector>(unset_bits(v));
assert_eq(indices, (std::vector<usize>{1, 3, 5, 7, 9}));
gf2::unset_bits
constexpr auto unset_bits(Store const &store)
Returns an iterator over the indices of any unset bits in the bit-store.
Definition BitStore.h:1114

◆ with_set_bits()

template<Unsigned Word>
Word gf2::with_set_bits ( u8 begin,
u8 end )
constexpr

Returns an Unsigned with the bits in the half-open range [begin, end) set to 1 and the others set to 0.

Note
In debug mode, the range `[begin, end) is checked for validity and the program exits on failure.

Example

assert_eq(with_set_bits<u8>(0, 0), 0b0000'0000);
assert_eq(with_set_bits<u8>(0, 1), 0b0000'0001);
assert_eq(with_set_bits<u8>(0, 2), 0b0000'0011);
assert_eq(with_set_bits<u8>(1, 3), 0b0000'0110);
assert_eq(with_set_bits<u8>(0, 8), 0b1111'1111);
gf2::with_set_bits
constexpr Word with_set_bits(u8 begin, u8 end)
Returns an Unsigned with the bits in the half-open range [begin, end) set to 1 and the others set to ...
Definition Unsigned.h:111

◆ with_unset_bits()

template<Unsigned Word>
Word gf2::with_unset_bits ( u8 begin,
u8 end )
constexpr

Returns an Unsigned with the bits in the half-open range [begin, end) set to 0 and the others set to 1.

Note
In debug mode, the range `[begin, end) is checked for validity and the program exits on failure.

Example

assert_eq(with_unset_bits<u8>(0, 0), 0b1111'1111);
assert_eq(with_unset_bits<u8>(0, 1), 0b1111'1110);
assert_eq(with_unset_bits<u8>(0, 2), 0b1111'1100);
assert_eq(with_unset_bits<u8>(1, 3), 0b1111'1001);
assert_eq(with_unset_bits<u8>(0, 8), 0b0000'0000);
gf2::with_unset_bits
constexpr Word with_unset_bits(u8 begin, u8 end)
Returns an Unsigned with the bits in the half-open range [begin, end) set to 0 and the others set to ...
Definition Unsigned.h:131

◆ word_index()

template<Unsigned Word>
usize gf2::word_index ( usize i)
constexpr

Returns the index of the Unsigned word holding bit element i.

Assumes we are holding bits in a sequence of Unsigned words.

Example

assert_eq(word_index<u8>(0), 0);
assert_eq(word_index<u8>(8), 1);
assert_eq(word_index<u8>(19), 2);
gf2::word_index
constexpr usize word_index(usize i)
Returns the index of the Unsigned word holding bit element i.
Definition Unsigned.h:540

◆ words_needed()

template<Unsigned Word>
usize gf2::words_needed ( usize n_bits)
constexpr

Returns the number of Unsigneds needed to store n_bits bits.

Example

assert_eq(words_needed<u8>(0), 0);
assert_eq(words_needed<u8>(8), 1);
assert_eq(words_needed<u8>(19), 3);
gf2::words_needed
constexpr usize words_needed(usize n_bits)
Returns the number of Unsigneds needed to store n_bits bits.
Definition Unsigned.h:523

Variable Documentation

◆ ALTERNATING

template<Unsigned Word>
Word gf2::ALTERNATING = MAX<Word> / 3
constexpr

The Unsigned instance with alternating bits set to 0 and 1.

Example

assert_eq(ALTERNATING<u8>, 0b0101'0101);
gf2::ALTERNATING
constexpr Word ALTERNATING
The Unsigned instance with alternating bits set to 0 and 1.
Definition Unsigned.h:91

◆ BITS

template<Unsigned Word>
u8 gf2::BITS = std::numeric_limits<Word>::digits
constexpr

The number of bits in an Unsigned returned as a u8.

Example

assert_eq(BITS<u16>, 16);
gf2::BITS
constexpr u8 BITS
The number of bits in an Unsigned returned as a u8.
Definition Unsigned.h:55

◆ MAX

template<Unsigned Word>
Word gf2::MAX = std::numeric_limits<Word>::max()
constexpr

The Unsigned instance with all its bits set to 1.

Example

assert_eq(MAX<u8>, 255);
gf2::MAX
constexpr Word MAX
The Unsigned instance with all its bits set to 1.
Definition Unsigned.h:82

◆ ONE

template<Unsigned Word>
Word gf2::ONE = Word{1}
constexpr

The one value for an Unsigned type.

Example

assert_eq(ONE<u8>, 1);
gf2::ONE
constexpr Word ONE
The one value for an Unsigned type.
Definition Unsigned.h:73

◆ ZERO

template<Unsigned Word>
Word gf2::ZERO = Word{0}
constexpr

The zero value for an Unsigned type.

Example

assert_eq(ZERO<u8>, 0);
gf2::ZERO
constexpr Word ZERO
The zero value for an Unsigned type.
Definition Unsigned.h:64