gf2::BitStore< Store >

The base class for the vector-like types in the gf2 library: BitSet, BitVec, and BitSpan
The template parameter Store is a derived class — we use the CRTP idiom for compile time polymorphism. The Store subclass provides an implementation for a small number of required methods and in return, inherit the many methods provided by this base class. More...

#include <BitStore.h>

Public Types
using	word_type = typename store_word<Store>::word_type
	Unsigned word type used to store the bits (u8, 16, u32, u64, or usize).

Public Member Functions
Required methods:
The BitStore subclasses implement the following methods ...
constexpr usize	size () const
	Returns the number of bit elements in the store.
constexpr usize	words () const
	Returns the fewest number of words needed to store the bits in the store.
constexpr word_type	word (usize i) const
	Returns "word" i underpinning this bit store.
constexpr void	set_word (usize i, word_type value)
	This method sets "word" at index i to the specified value.
constexpr const word_type *	data () const
	Returns a const pointer to the real first word in the underlying store.
constexpr word_type *	data ()
	Returns a pointer to the real first word in the underlying store.
constexpr u8	offset () const
	Returns the offset (in bits) from the bit 0 of data()[0] to the first bit in the store.
Individual bit reads:
constexpr bool	get (usize i) const
	Returns true if the bit at the given index i is set, false otherwise.
constexpr bool	operator[] (usize index) const
	Returns the boolean value of the bit element at index.
constexpr bool	front () const
	Returns true if the first bit element is set, false otherwise.
constexpr bool	back () const
	Returns true if the last bit element is set, false otherwise.
Individual bit mutators:
auto	set (usize index, bool value=true)
	Sets the bit-element at the given index to the specified boolean value & returns this for chaining. The default value for value is true.
constexpr auto	operator[] (usize index)
	Returns a "reference" to the bit element at index.
auto	flip (usize index)
	Flips the value of the bit-element at the given index and returns this for chaining/.
constexpr auto	swap (usize i0, usize i1)
	Swaps the bits in the bit-store at indices i0 and i1 and returns this for chaining.
Store queries:
constexpr bool	is_empty () const
	Returns true if the store is empty, false otherwise.
constexpr bool	any () const
	Returns true if at least one bit in the store is set, false otherwise.
constexpr bool	all () const
	Returns true if all bits in the store are set, false otherwise.
constexpr bool	none () const
	Returns true if no bits in the store are set, false otherwise.
Store mutators:
auto	set_all (bool value=true)
	Sets the bits in the store to the boolean value and returns a reference to this for chaining.
auto	flip_all ()
	Flips the value of the bits in the store and returns a reference to this for chaining.
Store fills:
template<unsigned_word Src>
auto	copy (Src src)
	Copies the bits from an unsigned integral src value and returns a reference to this for chaining.
template<typename SrcStore>
auto	copy (const BitStore< SrcStore > &src)
	Copies the bits from an equal-sized src store and returns a reference to this for chaining.
template<usize N>
auto	copy (const std::bitset< N > &src)
	Copies the bits of an equal-sized std::bitset and returns a reference to this for chaining.
auto	fill (std::invocable< usize > auto f)
	Fill the store by repeatedly calling f(i) and returns a reference to this for chaining.
auto	random_fill (double p=0.5, u64 seed=0)
	Fill the store with random bits and returns a reference to this for chaining.
Bit counts:
constexpr usize	count_ones () const
	Returns the number of set bits in the store.
constexpr usize	count_zeros () const
	Returns the number of unset bits in the store.
constexpr usize	leading_zeros () const
	Returns the number of leading zeros in the store.
constexpr usize	trailing_zeros () const
	Returns the number of trailing zeros in the store.
Set bit indices:
std::optional< usize >	first_set () const
	Returns the index of the first set bit in the bit-store or {} if no bits are set.
std::optional< usize >	last_set () const
	Returns the index of the last set bit in the bit-store or {} if no bits are set.
std::optional< usize >	next_set (usize index) const
	Returns the index of the next set bit after index in the store or {} if no more set bits exist.
std::optional< usize >	previous_set (usize index) const
	Returns the index of the previous set bit before index in the store or {} if there are none.
Unset bit indices:
std::optional< usize >	first_unset () const
	Returns the index of the first unset bit in the bit-store or {} if no bits are unset.
std::optional< usize >	last_unset () const
	Returns the index of the last unset bit in the bit-store or {} if no bits are unset.
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.
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 exist.
Iterators:
constexpr auto	bits () const
	Returns a const iterator over the bool values of the bits in the const bit-store.
constexpr auto	bits ()
	Returns a non-const iterator over the values of the bits in the mutable bit-store.
constexpr auto	set_bit_indices () const
	Returns an iterator over the indices of any set bits in the bit-store.
constexpr auto	unset_bit_indices () const
	Returns an iterator over the indices of any unset bits in the bit-store.
constexpr auto	store_words () const
	Returns a const iterator over all the words underlying the bit-store.
constexpr auto	to_words () const
	Returns a copy of the words underlying this bit-store.
Spans:
constexpr auto	span (usize begin, usize end) const
	Returns an immutable bit-span encompassing the bits in the half-open range [begin, end).
constexpr auto	span (usize begin, usize end)
	Returns a mutable bit-span encompassing the bits in the half-open range [begin, end).
Sub-vectors:
constexpr auto	sub (usize begin, usize end) const
	Returns a clone of the elements in the half-open range [begin, end) as a new bit-vector.
constexpr void	split_at (usize at, BitVec< word_type > &left, BitVec< word_type > &right) const
	Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively.
constexpr auto	split_at (usize at) const
	Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively.
Riffling:
constexpr void	riffle_into (BitVec< word_type > &dst) const
	Interleaves the bits of this bit-store with zeros storing the result into the bit-vector dst.
constexpr auto	riffled () const
	Returns a new bit-vector that is the result of riffling the bits in this bit-store with zeros.
Bit shifts:
constexpr void	operator<<= (usize shift)
	In-place left shift of the bit-store by shift bits.
constexpr void	operator>>= (usize shift)
	In-place right shift of the bit-store by shift bits.
constexpr auto	operator<< (usize shift) const
	Returns a new bit-vector that is lhs shifted left by shift bits.
constexpr auto	operator>> (usize shift) const
	Returns a new bit-vector that is lhs shifted right by shift bits.
Bit-wise operations:
template<typename Rhs> requires store_words_match<Store, Rhs>
void	operator^= (const BitStore< Rhs > &rhs)
	In-place XOR with another equal-sized bit-store.
template<typename Rhs> requires store_words_match<Store, Rhs>
void	operator&= (const BitStore< Rhs > &rhs)
	In-place AND with another equal-sized bit-store.
template<typename Rhs> requires store_words_match<Store, Rhs>
void	operator|= (const BitStore< Rhs > &rhs)
	In-place OR with another equal-sized bit-store.
auto	operator~ () const
	Returns a new bit-vector that has the same bits as the current bit-store but with all the bits flipped.
template<typename Rhs> requires store_words_match<Store, Rhs>
auto	operator^ (const BitStore< Rhs > &rhs) const
	Returns a new bit-vector that is the XOR of the current bit-store and another equal-sized bit-store.
template<typename Rhs> requires store_words_match<Store, Rhs>
auto	operator& (const BitStore< Rhs > &rhs) const
	Returns a new bit-vector that is the AND of the current bit-store and another equal-sized bit-store.
template<typename Rhs> requires store_words_match<Store, Rhs>
auto	operator| (const BitStore< Rhs > &rhs) const
	Returns a new bit-vector that is the OR of the current bit-store and another equal-sized bit-store.
Arithmetic operations:
template<typename Rhs> requires store_words_match<Store, Rhs>
void	operator+= (const BitStore< Rhs > &rhs)
	In-place addition of this bit-store with the an equal-sized rhs bit-store.
template<typename Rhs> requires store_words_match<Store, Rhs>
void	operator-= (const BitStore< Rhs > &rhs)
	In-place subtraction of this bit-store with the an equal-sized rhs bit-store.
template<typename Rhs> requires store_words_match<Store, Rhs>
auto	operator+ (const BitStore< Rhs > &rhs) const
	Returns a new bit-vector that is the + of this store with the passed (equal-sized) rhs bit-store.
template<typename Rhs> requires store_words_match<Store, Rhs>
auto	operator- (const BitStore< Rhs > &rhs) const
	Returns a new bit-vector that is the - of this store with the passed (equal-sized) rhs bit-store.
String representations:
std::string	to_string (std::string_view sep="", std::string_view pre="", std::string_view post="") const
	Returns a binary string representation of the store.
std::string	to_pretty_string () const
	Returns a "pretty" string representation of the store.
std::string	to_binary_string (std::string_view sep="", std::string_view pre="", std::string_view post="") const
	Returns a binary string representation of the store.
std::string	to_hex_string () const
	Returns the "hex" string representation of the bits in the bit-store.
std::string	describe () const
	Returns a multi-line string describing the bit-vector in some detail.

Static Public Attributes
static constexpr u8	bits_per_word = BITS<word_type>
	The number of bits in each store word.

Detailed Description

template<typename Store>
class gf2::BitStore< Store >

The base class for the vector-like types in the gf2 library: BitSet, BitVec, and BitSpan
The template parameter Store is a derived class — we use the CRTP idiom for compile time polymorphism. The Store subclass provides an implementation for a small number of required methods and in return, inherit the many methods provided by this base class.

Note

The BitStore class has no data members of its own. Users typically will not use this class directly – it's just an implementation detail to avoid code duplication. Instead, they will create Instead, they will create gf2::BitSet and gf2::BitVec instances, along with gf2::BitSpan's from those objects.

Member Function Documentation

all()

template<typename Store>

bool gf2::BitStore< Store >::all ( ) const

inlineconstexpr

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(v.all(), false);
v.set(0);
v.set(1);
v.set(2);
assert_eq(v.all(), true);

any()

template<typename Store>

bool gf2::BitStore< Store >::any ( ) const

inlineconstexpr

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(v.any(), false);
v.set(0);
assert_eq(v.any(), true);

back()

template<typename Store>

bool gf2::BitStore< Store >::back ( ) const

inlineconstexpr

Returns true if the last 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(v.back(), true);
v.set_all(false);
assert_eq(v.back(), false);

bits() [1/2]

template<typename Store>

auto gf2::BitStore< Store >::bits ( )

inlineconstexpr

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 : v.bits()) bit = true;
assert_eq(v.to_string(), "1111111111");

bits() [2/2]

template<typename Store>

auto gf2::BitStore< Store >::bits ( ) const

inlineconstexpr

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 : u.bits()) assert_eq(bit, true);

copy() [1/3]

template<typename Store>

template<typename SrcStore>

auto gf2::BitStore< Store >::copy ( const BitStore< SrcStore > & src )

inline

Copies the bits from an equal-sized src store and returns a reference to this 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(v.to_string(), "1111111111");
v.copy(BitVec<u8>::alternating(10));
assert_eq(v.to_string(), "1010101010");

copy() [2/3]

template<typename Store>

template<usize N>

auto gf2::BitStore< Store >::copy ( const std::bitset< N > & src )

inline

Copies the bits of an equal-sized std::bitset and returns a reference to this 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};
v.copy(src);
assert_eq(v.to_string(), "0101010101");

copy() [3/3]

template<typename Store>

template<unsigned_word Src>

auto gf2::BitStore< Store >::copy ( Src src )

inline

Copies the bits from an unsigned integral src value and returns a reference to this for chaining.

Notes:

1. The size of the store must match the number of bits in the source 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;
v.copy(src);
assert_eq(v.to_string(), "0101010101010101");
BitVec<u32> w{16};
w.copy(src);
assert_eq(w.to_string(), "0101010101010101");

count_ones()

template<typename Store>

usize gf2::BitStore< Store >::count_ones ( ) const

inlineconstexpr

Returns the number of set bits in the store.

Example

BitVec v{10};
assert_eq(v.count_ones(), 0);
v.set(0);
assert_eq(v.count_ones(), 1);

count_zeros()

template<typename Store>

usize gf2::BitStore< Store >::count_zeros ( ) const

inlineconstexpr

Returns the number of unset bits in the store.

Example

BitVec v{10};
assert_eq(v.count_zeros(), 10);
v.set(0);
assert_eq(v.count_zeros(), 9);

data()

template<typename Store>

word_type * gf2::BitStore< Store >::data ( )

inlineconstexpr

Returns a pointer to the real first word in the underlying store.

Note

The pointer is non-const but you should be careful about using it to modify the words in the store.

describe()

template<typename Store>

std::string gf2::BitStore< Store >::describe ( ) const

inline

Returns a multi-line string describing the bit-vector in some detail.

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

fill()

template<typename Store>

auto gf2::BitStore< Store >::fill ( std::invocable< usize > auto f )

inline

Fill the store by repeatedly calling f(i) and returns a reference to this for chaining.

Example

BitVec v{10};
v.fill([](usize i) { return i % 2 == 0; });
assert_eq(v.size(), 10);
assert_eq(v.to_string(), "1010101010");

first_set()

template<typename Store>

std::optional< usize > gf2::BitStore< Store >::first_set ( ) const

inline

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(v.first_set() == std::optional<usize>{});
v.set(2);
assert(v.first_set() == std::optional<usize>{2});
v.set(2, false);
assert(v.first_set() == std::optional<usize>{});
v.set(27);
assert(v.first_set() == std::optional<usize>{27});
BitVec empty;
assert(empty.first_set() == std::optional<usize>{});

first_unset()

template<typename Store>

std::optional< usize > gf2::BitStore< Store >::first_unset ( ) const

inline

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(v.first_unset() == std::optional<usize>{});
v.set(2, false);
assert(v.first_unset() == std::optional<usize>{2});
v.set(2);
assert(v.first_unset() == std::optional<usize>{});
v.set(27, false);
assert(v.first_unset() == std::optional<usize>{27});
BitVec empty;
assert(empty.first_unset() == std::optional<usize>{});

flip()

template<typename Store>

auto gf2::BitStore< Store >::flip ( usize index )

inline

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

Note

In debug mode the index is bounds-checked.

Example

auto v = BitVec<u8>::ones(10);
v.flip(0);
assert_eq(v.to_string(), "0111111111");
v.flip(1);
assert_eq(v.to_string(), "0011111111");
v.flip(9);
assert_eq(v.to_string(), "0011111110");

flip_all()

template<typename Store>

auto gf2::BitStore< Store >::flip_all ( )

inline

Flips the value of the bits in the store and returns a reference to this for chaining.

Example

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

front()

template<typename Store>

bool gf2::BitStore< Store >::front ( ) const

inlineconstexpr

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(v.front(), true);
v.set_all(false);
assert_eq(v.front(), false);

get()

template<typename Store>

bool gf2::BitStore< Store >::get ( usize i ) const

inlineconstexpr

Returns true if the bit at the given index i is set, false otherwise.

Note

In debug mode the index i is bounds-checked.

Example

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

is_empty()

template<typename Store>

bool gf2::BitStore< Store >::is_empty ( ) const

inlineconstexpr

Returns true if the store is empty, false otherwise.

Example

BitVec v;
assert_eq(v.is_empty(), true);
BitVec u{10};
assert_eq(u.is_empty(), false);

last_set()

template<typename Store>

std::optional< usize > gf2::BitStore< Store >::last_set ( ) const

inline

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(v.last_set() == std::optional<usize>{});
v.set(2);
assert(v.last_set() == std::optional<usize>{2});
v.set(27);
assert(v.last_set() == std::optional<usize>{27});
BitVec empty;
assert(empty.last_set() == std::optional<usize>{});

last_unset()

template<typename Store>

std::optional< usize > gf2::BitStore< Store >::last_unset ( ) const

inline

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(v.last_unset() == std::optional<usize>{});
v.set(2, false);
assert(v.last_unset() == std::optional<usize>{2});
v.set(2);
assert(v.last_unset() == std::optional<usize>{});
v.set(27, false);
assert(v.last_unset() == std::optional<usize>{27});
BitVec empty;
assert(empty.last_unset() == std::optional<usize>{});

leading_zeros()

template<typename Store>

usize gf2::BitStore< Store >::leading_zeros ( ) const

inlineconstexpr

Returns the number of leading zeros in the store.

Example

BitVec v{37};
assert_eq(v.leading_zeros(), 37);
v.set(27);
assert_eq(v.leading_zeros(), 27);
auto w = BitVec<u8>::ones(10);
assert_eq(w.leading_zeros(), 0);

next_set()

template<typename Store>

std::optional< usize > gf2::BitStore< Store >::next_set ( usize index ) const

inline

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(v.next_set(0) == std::optional<usize>{});
v.set(2);
v.set(27);
assert(v.next_set(0) == std::optional<usize>{2});
assert(v.next_set(2) == std::optional<usize>{27});
assert(v.next_set(27) == std::optional<usize>{});

next_unset()

template<typename Store>

std::optional< usize > gf2::BitStore< Store >::next_unset ( usize index ) const

inline

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>{});
v.set(2, false);
v.set(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>{});

none()

template<typename Store>

bool gf2::BitStore< Store >::none ( ) const

inlineconstexpr

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(v.none(), true);
v.set(0);
assert_eq(v.none(), false);

offset()

template<typename Store>

u8 gf2::BitStore< Store >::offset ( ) const

inlineconstexpr

Returns the offset (in bits) from the bit 0 of data()[0] to the first bit in the store.

Note

This is always zero for BitSet and BitVec but may be non-zero for BitSpan.

operator&()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

auto gf2::BitStore< Store >::operator& ( const BitStore< Rhs > & rhs ) const

inline

Returns a new bit-vector that is the AND of the current bit-store and another 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);
auto v2 = ~v1;
auto v3 = v1 & v2;
assert_eq(v3.to_string(), "0000000000");

operator&=()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

void gf2::BitStore< Store >::operator&= ( const BitStore< Rhs > & rhs )

inline

In-place AND with another 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(v1.to_string(), "0000000000");

operator+()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

auto gf2::BitStore< Store >::operator+ ( const BitStore< Rhs > & rhs ) const

inline

Returns a new bit-vector that is the + of this store with the passed (equal-sized) rhs bit-store.

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

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;
auto v3 = v1 + v2;
assert_eq(v3.to_string(), "1111111111");

operator+=()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

void gf2::BitStore< Store >::operator+= ( const BitStore< Rhs > & rhs )

inline

In-place addition of this bit-store with the an equal-sized rhs bit-store.

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

Note

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

Example

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

operator-()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

auto gf2::BitStore< Store >::operator- ( const BitStore< Rhs > & rhs ) const

inline

Returns a new bit-vector that is the - of this store with the passed (equal-sized) rhs bit-store.

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

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;
auto v3 = v1 - v2;
assert_eq(v3.to_string(), "1111111111");

operator-=()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

void gf2::BitStore< Store >::operator-= ( const BitStore< Rhs > & rhs )

inline

In-place subtraction of this bit-store with the an equal-sized rhs bit-store.

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

Note

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

Example

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

operator<<()

template<typename Store>

auto gf2::BitStore< Store >::operator<< ( usize shift ) const

inlineconstexpr

Returns a new bit-vector that is lhs 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(w.to_string(), "11111111111100000000");

operator<<=()

template<typename Store>

void gf2::BitStore< Store >::operator<<= ( usize shift )

inlineconstexpr

In-place left shift of the 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(v.to_string(), "11111111111100000000");

operator>>()

template<typename Store>

auto gf2::BitStore< Store >::operator>> ( usize shift ) const

inlineconstexpr

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(w.to_string(), "00000000111111111111");

operator>>=()

template<typename Store>

void gf2::BitStore< Store >::operator>>= ( usize shift )

inlineconstexpr

In-place right shift of the bit-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(v.to_string(), "00000000111111111111");

operator[]() [1/2]

template<typename Store>

auto gf2::BitStore< Store >::operator[] ( usize index )

inlineconstexpr

Returns a "reference" to the bit element at index.

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

Note

In debug mode the index i is bounds-checked.

Example

BitVec v{10};
v[2] = true;
assert(v.to_string() == "0010000000");
auto w = BitVec<>::ones(10);
v[3] = w[3];
assert(v.to_string() == "0011000000");
v[4] |= w[4];
assert(v.to_string() == "0011100000");

operator[]() [2/2]

template<typename Store>

bool gf2::BitStore< Store >::operator[] ( usize index ) const

inlineconstexpr

Returns the boolean value of the bit element at index.

Note

In debug mode the index is bounds-checked.

Example

BitVec v{10};
assert(v[2] == false);
v[2] = true;
assert(v[2] == true);
assert(v.to_string() == "0010000000");

operator^()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

auto gf2::BitStore< Store >::operator^ ( const BitStore< Rhs > & rhs ) const

inline

Returns a new bit-vector that is the XOR of the current bit-store and another 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);
auto v2 = ~v1;
auto v3 = v1 ^ v2;
assert_eq(v3.to_string(), "1111111111");

operator^=()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

void gf2::BitStore< Store >::operator^= ( const BitStore< Rhs > & rhs )

inline

In-place XOR with another 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(v1.to_string(), "1111111111");

operator|()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

auto gf2::BitStore< Store >::operator| ( const BitStore< Rhs > & rhs ) const

inline

Returns a new bit-vector that is the OR of the current bit-store and another equal-sized bit-store.

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;
auto v3 = v1 | v2;
assert_eq(v3.to_string(), "1111111111");

operator|=()

template<typename Store>

template<typename Rhs>
requires store_words_match<Store, Rhs>

void gf2::BitStore< Store >::operator|= ( const BitStore< Rhs > & rhs )

inline

In-place OR with another 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(v1.to_string(), "1111111111");

operator~()

template<typename Store>

auto gf2::BitStore< Store >::operator~ ( ) const

inline

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

Example

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

previous_set()

template<typename Store>

std::optional< usize > gf2::BitStore< Store >::previous_set ( usize index ) const

inline

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(v.previous_set(36) == std::optional<usize>{});
v.set(2);
v.set(27);
assert(v.previous_set(36) == std::optional<usize>{27});
assert(v.previous_set(27) == std::optional<usize>{2});
assert(v.previous_set(2)  == std::optional<usize>{});

previous_unset()

template<typename Store>

std::optional< usize > gf2::BitStore< Store >::previous_unset ( usize index ) const

inline

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>{});
v.set(2, false);
v.set(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>{});

random_fill()

template<typename Store>

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

inline

Fill the store with random bits and returns a reference to this for chaining.

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

Parameters

p	The probability of the elements being 1 (defaults to a fair coin, i.e. 50-50).
seed	The 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;
u.random_fill(0.5, seed);
v.random_fill(0.5, seed);
assert(u == v);

riffle_into()

template<typename Store>

void gf2::BitStore< Store >::riffle_into ( BitVec< word_type > & dst ) const

inlineconstexpr

Interleaves the bits of this bit-store with zeros storing the result into the 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;
v.riffle_into(dst);
assert_eq(dst.to_string(), "1010101010101010101");

riffled()

template<typename Store>

auto gf2::BitStore< Store >::riffled ( ) const

inlineconstexpr

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 = v.riffled();
assert_eq(dst.to_string(), "1010101010101010101");

set()

template<typename Store>

auto gf2::BitStore< Store >::set ( usize index, bool value = true )

inline

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

Note

In debug mode the index is bounds-checked.

Example

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

set_all()

template<typename Store>

auto gf2::BitStore< Store >::set_all ( bool value = true )

inline

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

By default, all bits are set to true.

Example

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

set_bit_indices()

template<typename Store>

auto gf2::BitStore< Store >::set_bit_indices ( ) const

inlineconstexpr

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(v.to_string(), "1010101010");
auto indices = std::ranges::to<std::vector>(v.set_bit_indices());
assert_eq(indices, (std::vector<usize>{0, 2, 4, 6, 8}));

set_word()

template<typename Store>

void gf2::BitStore< Store >::set_word ( usize i, word_type value )

inlineconstexpr

This method sets "word" at index i to the specified value.

For example, if the store has 18 bit elements, then setting the first word changes bit elements 0 through 7, the second word changes bit elements 8 through 15, and the third word changes bit elements 16 and 17.

This method is trivially implemented by the BitVec class. However, the bits in a BitSpan may not be aligned to word boundaries but that class synthesises words as if they were by combining adjacent words as needed.

Note

The method must ensure that inaccessible bits in the underlying store are not changed by this call.

span() [1/2]

template<typename Store>

auto gf2::BitStore< Store >::span ( usize begin, usize end )

inlineconstexpr

Returns a mutable bit-span encompassing the bits in the half-open range [begin, end).

Mutability here is deep – the interior pointer in the returned span is to non-const words.

Note

This method panics if the bit-vector is empty or if the range is not valid.

Example

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

span() [2/2]

template<typename Store>

auto gf2::BitStore< Store >::span ( usize begin, usize end ) const

inlineconstexpr

Returns an immutable bit-span encompassing the bits in the half-open range [begin, end).

Immutability here is deep – the interior pointer in the returned span is to const words.

Note

This method panics if the bit-store is empty or if the range is not valid.

Example

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

split_at() [1/2]

template<typename Store>

auto gf2::BitStore< Store >::split_at ( usize at ) const

inlineconstexpr

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 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] = v.split_at(5);
assert_eq(left.to_string(), "10101");
assert_eq(right.to_string(), "01010");
assert_eq(v.to_string(), "1010101010");

split_at() [2/2]

template<typename Store>

void gf2::BitStore< Store >::split_at ( usize at, BitVec< word_type > & left, BitVec< word_type > & right ) const

inlineconstexpr

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;
v.split_at(5, left, right);
assert_eq(left.to_string(), "10101");
assert_eq(right.to_string(), "01010");
assert_eq(v.to_string(), "1010101010");

store_words()

template<typename Store>

auto gf2::BitStore< Store >::store_words ( ) const

inlineconstexpr

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. Note that 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(v.to_string(), "1111111111");
auto indices = std::ranges::to<std::vector>(v.store_words());
assert_eq(indices, (std::vector<u8>{0b1111'1111, 0b0000'0011}));

sub()

template<typename Store>

auto gf2::BitStore< Store >::sub ( usize begin, usize end ) const

inlineconstexpr

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

Note

This method panics if the bit-vector is empty or if the range is not valid.

Example

auto v = BitVec<>::alternating(10);
auto s = v.sub(1,5);
assert_eq(s.to_string(), "0101");
s.set_all();
assert_eq(s.to_string(), "1111");
assert_eq(v.to_string(), "1010101010");

swap()

template<typename Store>

auto gf2::BitStore< Store >::swap ( usize i0, usize i1 )

inlineconstexpr

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

Note

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

Example

auto v = BitVec<>::zeros(10);
v.set(0);
assert_eq(v.to_string(), "1000000000");
v.swap(0, 1);
assert_eq(v.to_string(), "0100000000");
v.swap(0, 1);
assert_eq(v.to_string(), "1000000000");
v.swap(0, 9);
assert_eq(v.to_string(), "0000000001");
v.swap(0, 9);
assert_eq(v.to_string(), "1000000000");

to_binary_string()

template<typename Store>

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

inline

Returns a binary string representation of the store.

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

Parameters

sep	The separator between bit elements which defaults to no separator.
pre	The prefix to add to the string which defaults to no prefix.
post	The postfix to add to the string which defaults to no postfix.

Example

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

to_hex_string()

template<typename Store>

std::string gf2::BitStore< Store >::to_hex_string ( ) const

inline

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(v0.to_hex_string(), "");
auto v1 = BitVec<>::ones(4);
assert_eq(v1.to_hex_string(), "F");
auto v2 = BitVec<>::ones(5);
assert_eq(v2.to_hex_string(), "F1.2");
auto v3 = BitVec<>::alternating(8);
assert_eq(v3.to_binary_string(), "10101010");
assert_eq(v3.to_hex_string(), "AA");

to_pretty_string()

template<typename Store>

std::string gf2::BitStore< Store >::to_pretty_string ( ) const

inline

Returns a "pretty" string representation of the 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(v.to_pretty_string(), "[1,0,1,0,1,0,1,0,1,0]");
BitVec empty;
assert_eq(empty.to_pretty_string(), "[]");

to_string()

template<typename Store>

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

inline

Returns a binary string representation of the store.

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

Parameters

sep	The separator between bit elements which defaults to no separator.
pre	The prefix to add to the string which defaults to no prefix.
post	The postfix to add to the string which defaults to no postfix.

Example

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

to_words()

template<typename Store>

auto gf2::BitStore< Store >::to_words ( ) const

inlineconstexpr

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 = v.to_words();
assert_eq(words, (std::vector<u8>{0b1111'1111, 0b0000'0011}));

trailing_zeros()

template<typename Store>

usize gf2::BitStore< Store >::trailing_zeros ( ) const

inlineconstexpr

Returns the number of trailing zeros in the store.

Example

auto v = BitVec<u8>::zeros(27);
assert_eq(v.trailing_zeros(), 27);
v.set(0);
assert_eq(v.trailing_zeros(), 26);

unset_bit_indices()

template<typename Store>

auto gf2::BitStore< Store >::unset_bit_indices ( ) const

inlineconstexpr

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(v.to_string(), "1010101010");
auto indices = std::ranges::to<std::vector>(v.unset_bit_indices());
assert_eq(indices, (std::vector<usize>{1, 3, 5, 7, 9}));

word()

template<typename Store>

word_type gf2::BitStore< Store >::word ( usize i ) const

inlineconstexpr

Returns "word" i underpinning this bit store.

For example, if the store has 18 elements, then the first word will be returned for bit elements 0 through 7, the second word will be returned for bit elements 8 through 15, and the third word will be returned for bit elements 16 and 17.

This method is trivially implemented by the BitVec class. However, the bits in a BitSpan may not be aligned to word boundaries but that class synthesises words as if they were by combining adjacent words as needed.

Note

The final word may not be fully occupied but the method must guarantee that unused bits are set to 0.

words()

template<typename Store>

usize gf2::BitStore< Store >::words ( ) const

inlineconstexpr

Returns the fewest number of words needed to store the bits in the store.

This method is trivially implemented by the BitVec class. However, the bits in a BitSpan may not be aligned to word boundaries but that class synthesises words as if they were by combining adjacent words as needed.