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

#include <BitVector.h>

Public Types
using	word_type = Word
	The underlying unsigned word type used to store the bits.

Public Member Functions
Required BitStore Concept Methods:
constexpr usize	size () const
	Returns the number of bit-elements in the bit-vector.
constexpr usize	words () const
	Returns the number of words in the bit-vector's underlying word store.
constexpr Word	word (usize i) const
	Returns word i from the bit-vector's underlying word store.
constexpr void	set_word (usize i, Word word)
	Sets word i in the bit-vector's underlying word store to value (masked if necessary).
constexpr const Word *	store () const
	Returns a const pointer to the underlying store of words .
constexpr Word *	store ()
	Returns a pointer to the underlying store of words.
constexpr u8	offset () const
	Returns the offset (in bits) of the first bit in the bit-vector within the first word.
Constructors:
constexpr	BitVector (usize size=0)
	Constructs a bit-vector of length n with all the bit elements set to 0.
constexpr	BitVector (usize size, Word word)
	Constructs a bit-vector with size elements by repeatedly copying all the bits from word.
Size and Capacity:
constexpr usize	capacity () const
	Returns the current capacity of the bit-vector.
constexpr usize	remaining_capacity () const
	Returns the number of additional elements we can store in the bit-vector without reallocating.
constexpr BitVector &	shrink_to_fit ()
	Shrinks the bit-vector's capacity as much as possible.
constexpr BitVector &	clear ()
	Removes all elements from the bit-vector so `size()==0`.
constexpr BitVector &	resize (usize n)
	Resize the bit-vector so that its size() is n.
constexpr void	clean ()
	Sets any unused bits in the last occupied word to 0.
Push/pop Single Elements:
constexpr BitVector &	push (bool b)
	Pushes a single bit b onto the bit-vector.
constexpr std::optional< bool >	pop ()
	Removes the last bit from the bit-vector and returns it or std::nullopt if the bit-vector is empty.
Appending from Various Sources:
template<Unsigned Src>
constexpr auto	append (Src src)
	Appends all the bits from any unsigned integral src value and returns a reference to this for chaining.
template<typename Iter> requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>
constexpr auto	append (Iter src_begin, Iter src_end)
	Appends all the bits from an iteration of any Unsigneds and returns a reference to this for chaining.
template<BitStore Src>
constexpr BitVector &	append (Src const &src)
	Appends all the bits from any BitStore src onto the end of the bit-vector and returns this for chaining.
template<usize N>
auto	append (std::bitset< N > const &src)
	Appends all the bits from a std::bitset onto the end of the bit-vector and returns this for chaining.
constexpr BitVector &	append_digit (char c, int base)
	Appends a single character c onto the end of bit-vector and returns this for chaining.
constexpr BitVector &	append_hex_digit (char c)
	Appends a single hex digit character c onto the end of bit-vector and returns this for chaining.
Removing Elements:
constexpr BitVector< Word >	split_off (usize at)
	Splits a bit-vector into two at the given index, returning a new BitVector.
constexpr void	split_off (usize at, BitVector< Word > &dst)
	Splits a bit-vector into two at the given index, returning the second part in dst.
template<Unsigned Dst = Word>
constexpr std::optional< Dst >	split_off_unsigned ()
	Split off a single arbitrary sized unsigned integer off the end of the bit-vector and returns it or std::nullopt if the bit-vector is empty.
Bit Accessors:
constexpr bool	get (usize i) const
	Returns true if the bit at the given index i is set, false otherwise.
constexpr bool	operator[] (usize i) const
	Returns the boolean value of the bit element i.
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.
Bit Mutators:
constexpr auto	set (usize i, bool value=true)
	Sets the bit-element i to the specified boolean value & returns this for chaining. The default value for value is true.
constexpr auto	operator[] (usize i)
	Returns a "reference" to the bit element i.
constexpr auto	flip (usize i)
	Flips the value of the bit-element i and returns this for chaining.
constexpr auto	swap (usize i0, usize i1)
	Swaps the bits in the bit-vector at indices i0 and i1 and returns this for chaining.
Store Queries:
constexpr bool	is_empty () const
	Returns true if the bit-vector is empty, false otherwise.
constexpr bool	any () const
	Returns true if at least one bit in the bit-vector is set, false otherwise.
constexpr bool	all () const
	Returns true if all bits in the bit-vector are set, false otherwise.
constexpr bool	none () const
	Returns true if no bits in the bit-vector are set, false otherwise.
Store Mutators:
constexpr auto	set_all (bool value=true)
	Sets the bits in the bit-vector to the boolean value and returns a reference to this for chaining.
constexpr auto	flip_all ()
	Flips the value of the bits in the bit-vector and returns a reference to this for chaining.
Copying into the BitVector:
template<Unsigned Src>
constexpr auto	copy (Src src)
	Copies all the bits from any unsigned integral src value to this equal-sized bit-vector. Returns a reference to this for chaining.
template<typename Iter> requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>
constexpr void	copy (Iter src_begin, Iter src_end)
	Copies all the bits from an iteration of any unsigned integral src values to this equal-sized bit-vector.
template<BitStore Src>
constexpr auto	copy (Src const &src)
	Copies all the bits from any src bit-store to this equal-sized bit-vector and returns a reference to this for chaining.
template<usize N>
constexpr auto	copy (std::bitset< N > const &src)
	Copies all the bits from a std::bitset to this equal-sized bit-vector and returns a reference to this for chaining.
BitVector Fills:
constexpr auto	copy (std::invocable< usize > auto f)
	Fills the bit-vector by repeatedly calling f(i) and returns a reference to this for chaining.
constexpr auto	fill_random (double p=0.5, u64 seed=0)
	Fill the bit-vector 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 bit-vector.
constexpr usize	count_zeros () const
	Returns the number of unset bits in the bit-vector.
constexpr usize	leading_zeros () const
	Returns the number of leading zeros in the bit-vector.
constexpr usize	trailing_zeros () const
	Returns the number of trailing zeros in the bit-vector.
Set-bit Indices:
constexpr std::optional< usize >	first_set () const
	Returns the index of the first set bit in the bit-vector or {} if no bits are set.
constexpr std::optional< usize >	last_set () const
	Returns the index of the last set bit in the bit-vector or {} if no bits are set.
constexpr std::optional< usize >	next_set (usize index) const
	Returns the index of the next set bit after index in the bit-vector or {} if no more set bits exist.
constexpr std::optional< usize >	previous_set (usize index) const
	Returns the index of the previous set bit before index in the bit-vector or {} if there are none.
Unset-bit Indices:
constexpr std::optional< usize >	first_unset () const
	Returns the index of the first unset bit in the bit-vector or {} if no bits are unset.
constexpr std::optional< usize >	last_unset () const
	Returns the index of the last unset bit in the bit-vector or {} if no bits are unset.
constexpr std::optional< usize >	next_unset (usize index) const
	Returns the index of the next unset bit after index in the bit-vector or {} if no more unset bits exist.
constexpr std::optional< usize >	previous_unset (usize index) const
	Returns the index of the previous unset bit before index in the bit-vector 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-vector.
constexpr auto	bits ()
	Returns a non-const iterator over the values of the bits in the mutable bit-vector.
constexpr auto	set_bits () const
	Returns an iterator over the indices of any set bits in the bit-vector.
constexpr auto	unset_bits () const
	Returns an iterator over the indices of any unset bits in the bit-vector.
constexpr auto	store_words () const
	Returns a const iterator over all the words underlying the bit-vector.
Exports:
constexpr void	to_words (std::output_iterator< word_type > auto out)
	Returns a copy of the words underlying this bit-vector and puts them into the passed output iterator.
constexpr auto	to_words () const
	Returns a copy of the words underlying this bit-vector as a new std::vector<word_type>.
Spans:
constexpr auto	span (usize begin, usize end) const
	Returns an immutable bit-span encompassing the bit-vector's bits in the half-open range [begin, end).
constexpr auto	span (usize begin, usize end)
	Returns a mutable bit-span encompassing the bit-vector's 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.
Splits:
constexpr void	split_at (usize at, BitVector< word_type > &left, BitVector< word_type > &right) const
	Views the bit-vector as two parts containing the elements [0, at) and [at, size()) respectively.
constexpr auto	split_at (usize at) const
	Views the bit-vector as two parts containing the elements [0, at) and [at, size()) respectively.
Riffling:
constexpr void	riffled (BitVector< word_type > &dst) const
	Interleaves the bits of this bit-vector 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-vector with zeros.
String Representations:
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 bit-vector.
std::string	to_string (std::string_view sep="", std::string_view pre="", std::string_view post="") const
	Returns a binary string representation of the bit-vector.
std::string	to_pretty_string () const
	Returns a "pretty" string representation of the bit-vector.
std::string	to_hex_string () const
	Returns the "hex" string representation of the bits in the bit-vector.
std::string	describe () const
	Returns a multi-line string describing the bit-vector in some detail.

Static Public Member Functions
Factory Constructors:
static constexpr BitVector	with_capacity (usize capacity)
	Factory method to construct an empty bit-vector with at least the specified capacity.
static constexpr BitVector	zeros (usize n)
	Factory method to generate a bit-vector of length n where the elements are all 0.
static constexpr BitVector	ones (usize n)
	Factory method to generate a bit-vector of length n where the elements are all 1.
static constexpr BitVector	constant (usize n, bool value)
	Factory method to generate a bit-vector of length n where the elements are set to value.
static constexpr BitVector	unit (usize n, usize i)
	Factory method to generate a "unit" bit-vector of length n where only element i is set.
static constexpr BitVector	alternating (usize n)
	Factory method to generate a bit-vector of length n looking like 101010....
template<Unsigned Src>
static constexpr BitVector	from (Src src)
	Factory method to construct a bit-vector by copying all the bits from any Unsigned instance. The resulting bit-vector will have the same size as the number of bits in the src unsigned integer.
template<typename Iter> requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>
static constexpr BitVector	from (Iter src_begin, Iter src_end)
	Factory method to construct a bit-vector by copying all the bits from an iteration of any Unsigneds.
template<BitStore Src>
static constexpr BitVector	from (Src const &src)
	Factory method to construct a bit-vector by copying all the bits from any other bit-store instance.
template<usize N>
static constexpr BitVector	from (std::bitset< N > const &src)
	Factory method to construct a bit-vector from the bits of a std::bitset.
static constexpr BitVector	from (usize size, std::invocable< usize > auto f)
	Factory method to construct a bit-vector by repeatedly calling f(i) for i in [0, size).
Constructor BitVectors with Random Fills:
static BitVector	random (usize size, double p=0.5, u64 seed=0)
	Factory method to generate a bit-vector of size size where the elements are picked at random.
static BitVector	seeded_random (usize size, u64 seed)
	Factory method to generate a bit-vector of size size where the elements are from independent fair coin flips generated from an RNG seeded with the given seed.
static BitVector	biased_random (usize size, double p)
	Factory method to generate a bit-vector of size size where the elements are from independent fair coin flips and where each bit is 1 with probability p.
Constructors from Strings:
static std::optional< BitVector >	from_string (std::string_view sv)
	Factory method to construct a bit-vector from a string s, returning std::nullopt on failure.
static std::optional< BitVector >	from_binary_string (std::string_view sv, bool no_punctuation=false)
	Factory method to construct a bit-vector from a binary string, returning std::nullopt on failure.
static std::optional< BitVector >	from_hex_string (std::string_view sv, bool no_punctuation=false)
	Factory method to construct a bit-vector from a hex string, returning std::nullopt on failure.

Static Public Attributes
static constexpr u8	bits_per_word = BITS<Word>
	The number of bits per Word.

Detailed Description

template<Unsigned Word = usize>
class gf2::BitVector< Word >

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.

The BitVector class satisfies the BitStore concept.

Constructor & Destructor Documentation

◆ BitVector() [1/2]

template<Unsigned Word = usize>

gf2::BitVector< Word >::BitVector ( usize size = 0 )

inlineexplicitconstexpr

Constructs a bit-vector of length n with all the bit elements set to 0.

Note: The default constructor returns the empty bit-vector with no elements.

Example

BitVector u;
assert_eq(u.to_string(), "");
BitVector<u8> v{10};
assert_eq(v.to_string(), "0000000000");

◆ BitVector() [2/2]

template<Unsigned Word = usize>

gf2::BitVector< Word >::BitVector	(	usize	size,
		Word	word )

inlineexplicitconstexpr

Constructs a bit-vector with size elements by repeatedly copying all the bits from word.

You specify the size of the bit-vector which means the final copy of word may be truncated and padded with zeros (unused bit slots are always set to zero in this library).

Example

BitVector<u8> v{10, u8{0b0101'0101}};
assert_eq(v.size(), 10);
assert_eq(v.to_string(), "1010101010");

Member Function Documentation

◆ all()

template<Unsigned Word = usize>

bool gf2::BitVector< Word >::all ( ) const

inlineconstexpr

Returns true if all bits in the bit-vector are set, false otherwise.

Note: Empty bit-vectors have no set bits (logical connective for all is AND with identity true).

Example

BitVector v{3};
assert_eq(v.all(), false);
v.set(0);
v.set(1);
v.set(2);
assert_eq(v.all(), true);

◆ alternating()

template<Unsigned Word = usize>

constexpr BitVector gf2::BitVector< Word >::alternating ( usize n )

inlinestaticconstexpr

Factory method to generate a bit-vector of length n looking like 101010....

Example

assert_eq(BitVector<u8>::alternating(10).to_string(), "1010101010");

gf2::BitVector::alternating

static constexpr BitVector alternating(usize n)

Factory method to generate a bit-vector of length n looking like 101010....

Definition BitVector.h:239

◆ any()

template<Unsigned Word = usize>

bool gf2::BitVector< Word >::any ( ) const

inlineconstexpr

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

Note: Empty bit-vectors have no set bits (logical connective for any is OR with identity false).

Example

BitVector v{10};
assert_eq(v.any(), false);
v.set(0);
assert_eq(v.any(), true);

◆ append() [1/4]

template<Unsigned Word = usize>

template<typename Iter>
requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>

auto gf2::BitVector< Word >::append	(	Iter	src_begin,
		Iter	src_end )

inlineconstexpr

Appends all the bits from an iteration of any Unsigneds and returns a reference to this for chaining.

Note

We allow any unsigned integral source, e.g. appending u64 words into a BitVector<u8>.

Example

auto v = BitVector<u8>::ones(4);
std::vector<u16> src = { 0b1010101010101010, 0b1010101010101010, 0b1111111111111111 };
v.append(src.begin(), src.end());
assert_eq(v.to_string(), "1111010101010101010101010101010101011111111111111111");
auto w = BitVector<u32>::ones(4);
w.append(src.begin(), src.end());
assert_eq(w.to_string(), "1111010101010101010101010101010101011111111111111111");

◆ append() [2/4]

template<Unsigned Word = usize>

template<BitStore Src>

BitVector & gf2::BitVector< Word >::append ( Src const & src )

inlineconstexpr

Appends all the bits from any BitStore src onto the end of the bit-vector and returns this for chaining.

Note

Generally, we do not support interactions between bit-stores that use different underlying unsigned word types. This method is an exception, and the src bit-store may use a different unsigned type from the one used here.

Example

auto v = BitVector<u8>::zeros(10);
auto w = BitVector<u16>::ones(10);
v.append(w);
assert_eq(v.size(), 20);
assert_eq(v.to_string(), "00000000001111111111");

◆ append() [3/4]

template<Unsigned Word = usize>

template<Unsigned Src>

auto gf2::BitVector< Word >::append ( Src src )

inlineconstexpr

Appends all the bits from any unsigned integral src value and returns a reference to this for chaining.

Note: We allow any unsigned integral source, e.g. appending a single u16 into a BitVector<u8>.

Example

auto v = BitVector<u8>::ones(4);
u16 src = 0b1010101010101010;
v.append(src);
assert_eq(v.to_string(), "11110101010101010101");
auto w = BitVector<u32>::ones(4);
w.append(src);
assert_eq(w.to_string(), "11110101010101010101");

◆ append() [4/4]

template<Unsigned Word = usize>

template<usize N>

auto gf2::BitVector< Word >::append ( std::bitset< N > const & src )

inline

Appends all the bits from a std::bitset onto the end of the bit-vector and returns this for chaining.

Example

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

◆ append_digit()

template<Unsigned Word = usize>

BitVector & gf2::BitVector< Word >::append_digit	(	char	c,
		int	base )

inlineconstexpr

Appends a single character c onto the end of bit-vector and returns this for chaining.

The character is interpreted as a base base number wherebase must be one of 2, 4, 8, 16.

Note: This method does nothing if the base or character is not recognized.

Example

BitVector v;
v.append_digit('A', 16);
assert_eq(v.to_string(), "1010");
v.append_digit('X', 16);
assert_eq(v.to_string(), "1010");
v.append_digit('1', 8);
assert_eq(v.to_string(), "1010001");
v.append_digit('1', 4);
assert_eq(v.to_string(), "101000101");
v.append_digit('1', 2);
assert_eq(v.to_string(), "1010001011");

◆ append_hex_digit()

template<Unsigned Word = usize>

BitVector & gf2::BitVector< Word >::append_hex_digit ( char c )

inlineconstexpr

Appends a single hex digit character c onto the end of bit-vector and returns this for chaining.

Note: This method does nothing if the character is not a hex digit.

This is the same as append_digit(c, 16) but we push hex digits more often than other bases and want to skip some checks for efficiency.

Example

BitVector v;
v.append_hex_digit('F');
assert_eq(v.to_string(), "1111");
v.append_hex_digit('X');
assert_eq(v.to_string(), "1111");
v.append_hex_digit('1');
assert_eq(v.to_string(), "11110001");

◆ back()

template<Unsigned Word = usize>

bool gf2::BitVector< Word >::back ( ) const

inlineconstexpr

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

Panics

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

Example

auto v = BitVector<>::ones(10);
assert_eq(v.back(), true);
v.set_all(false);
assert_eq(v.back(), false);

◆ biased_random()

template<Unsigned Word = usize>

BitVector gf2::BitVector< Word >::biased_random	(	usize	size,
		double	p )

inlinestatic

Factory method to generate a bit-vector of size size where the elements are from independent fair coin flips and where each bit is 1 with probability p.

Parameters

size	The length of the bit-vector to generate.
p	The probability of the elements being 1.

Example

auto u = BitVector<>::biased_random(10, 0.3);
auto v = BitVector<>::biased_random(10, 0.3);
assert_eq(u.size(), v.size());

◆ bits() [1/2]

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::bits ( )

inlineconstexpr

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

You can use this iterator to iterate over the bits in the bit-vector 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 = BitVector<u8>::zeros(10);
for (auto&& bit : v.bits()) bit = true;
assert_eq(v.to_string(), "1111111111");

◆ bits() [2/2]

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::bits ( ) const

inlineconstexpr

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

You can use this iterator to iterate over the bits in the bit-vector 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 = BitVector<u8>::ones(10);

for (auto&& bit : u.bits()) assert_eq(bit, true);

◆ capacity()

template<Unsigned Word = usize>

usize gf2::BitVector< Word >::capacity ( ) const

inlineconstexpr

Returns the current capacity of the bit-vector.

This is the total number of bits that the bit-vector can hold without allocating more memory. The number includes the number of bits already in use.

Example

BitVector v0;
assert_eq(v0.capacity(), 0);
BitVector<u64> v1(10);
assert_eq(v1.capacity(), 64);

◆ clean()

template<Unsigned Word = usize>

void gf2::BitVector< Word >::clean ( )

inlineconstexpr

Sets any unused bits in the last occupied word to 0.

This method can be used to enforce the guarantee that unused bits in the store are always set to 0.

◆ clear()

template<Unsigned Word = usize>

BitVector & gf2::BitVector< Word >::clear ( )

inlineconstexpr

Removes all elements from the bit-vector so size()==0.

The capacity is not changed by this operation.

◆ constant()

template<Unsigned Word = usize>

constexpr BitVector gf2::BitVector< Word >::constant	(	usize	n,
		bool	value )

inlinestaticconstexpr

Factory method to generate a bit-vector of length n where the elements are set to value.

Example

auto v = BitVector<>::constant(10, true);
assert_eq(v.to_string(), "1111111111");
auto w = BitVector<>::constant(10, false);
assert_eq(w.to_string(), "0000000000");

◆ copy() [1/5]

template<Unsigned Word = usize>

template<typename Iter>
requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>

void gf2::BitVector< Word >::copy	(	Iter	src_begin,
		Iter	src_end )

inlineconstexpr

Copies all the bits from an iteration of any unsigned integral src values to this equal-sized bit-vector.

Note

We allow any unsigned integral source, e.g. copying u64 words into a BitVector<u8> of the correct size.

Panics

Panics if the size of this bit-vector does not match the number of bits in the source iteration.

Example

BitVector<u8> v{48};
std::vector<u16> src = { 0b1010101010101010, 0b1010101010101010, 0b1111111111111111 };
v.copy(src.begin(), src.end());
assert_eq(v.to_string(), "010101010101010101010101010101011111111111111111");
BitVector<u32> w{48};
w.copy(src.begin(), src.end());
assert_eq(w.to_string(), "010101010101010101010101010101011111111111111111");

◆ copy() [2/5]

template<Unsigned Word = usize>

template<BitStore Src>

auto gf2::BitVector< Word >::copy ( Src const & src )

inlineconstexpr

Copies all the bits from any src bit-store to this equal-sized bit-vector 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 BitVector<u32> to BitVector<u8>) as long as the sizes match.

Panics

Panics if the sizes of this bit-vector and the src bit-store do not match.

Example

auto v = BitVector<u64>::ones(10);
assert_eq(v.to_string(), "1111111111");
v.copy(BitVector<u8>::alternating(10));
assert_eq(v.to_string(), "1010101010");

◆ copy() [3/5]

template<Unsigned Word = usize>

template<Unsigned Src>

auto gf2::BitVector< Word >::copy ( Src src )

inlineconstexpr

Copies all the bits from any unsigned integral src value to this equal-sized bit-vector. Returns a reference to this for chaining.

Notes:

We allow any unsigned integral source, e.g. copying a single u64 into a BitVector<u8> of size 64.
The least-significant bit of the source becomes the bit at index 0 in the bit-vector.

Panics

Panics if the size of the bit-vector does not match the number of bits in the source integer type.

Example

BitVector<u8> v{16};
u16 src = 0b1010101010101010;
v.copy(src);
assert_eq(v.to_string(), "0101010101010101");
BitVector<u32> w{16};
w.copy(src);
assert_eq(w.to_string(), "0101010101010101");

◆ copy() [4/5]

template<Unsigned Word = usize>

template<usize N>

auto gf2::BitVector< Word >::copy ( std::bitset< N > const & src )

inlineconstexpr

Copies all the bits from a std::bitset to this equal-sized bit-vector and returns a reference to this for chaining.

Note

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

Panics

Panics if the size of the bit-vectors does not match the number of bits in the source std::bitset.

Example

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

◆ copy() [5/5]

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::copy ( std::invocable< usize > auto f )

inlineconstexpr

Fills the bit-vector by repeatedly calling f(i) and returns a reference to this for chaining.

Example

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

◆ count_ones()

template<Unsigned Word = usize>

usize gf2::BitVector< Word >::count_ones ( ) const

inlineconstexpr

Returns the number of set bits in the bit-vector.

Example

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

◆ count_zeros()

template<Unsigned Word = usize>

usize gf2::BitVector< Word >::count_zeros ( ) const

inlineconstexpr

Returns the number of unset bits in the bit-vector.

Example

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

◆ describe()

template<Unsigned Word = usize>

std::string gf2::BitVector< Word >::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_random()

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::fill_random	(	double	p = 0.5,
		u64	seed = 0 )

inlineconstexpr

Fill the bit-vector with random bits and returns a reference to this for chaining.

The default call fill_random() 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).

If p < 0 then the fill is all zeros, if p > 1 then the fill is all ones.

Example

BitVector u{10}, v{10};
u64 seed = 1234567890;
u.fill_random(0.5, seed);
v.fill_random(0.5, seed);
assert(u == v);

◆ first_set()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitVector< Word >::first_set ( ) const

inlineconstexpr

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

Example

auto v = BitVector<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});
BitVector empty;
assert(empty.first_set() == std::optional<usize>{});

◆ first_unset()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitVector< Word >::first_unset ( ) const

inlineconstexpr

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

Example

auto v = BitVector<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});
BitVector empty;
assert(empty.first_unset() == std::optional<usize>{});

◆ flip()

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::flip ( usize i )

inlineconstexpr

Flips the value of the bit-element i and returns this for chaining.

Panics

In debug mode the index i is bounds-checked.

Example

auto v = BitVector<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<Unsigned Word = usize>

auto gf2::BitVector< Word >::flip_all ( )

inlineconstexpr

Flips the value of the bits in the bit-vector and returns a reference to this for chaining.

Example

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

◆ from() [1/5]

template<Unsigned Word = usize>

template<typename Iter>
requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>

constexpr BitVector gf2::BitVector< Word >::from	(	Iter	src_begin,
		Iter	src_end )

inlinestaticconstexpr

Factory method to construct a bit-vector by copying all the bits from an iteration of any Unsigneds.

Note

We allow any unsigned integral source, e.g. copying u64 words into a BitVector<u8>.

Example

std::vector<u16> src = { 0b1010101010101010, 0b1010101010101010, 0b1111111111111111 };
auto v = BitVector<u8>::from(src.begin(), src.end());
assert_eq(v.to_string(), "010101010101010101010101010101011111111111111111");
auto w = BitVector<u32>::from(src.begin(), src.end());
assert_eq(w.to_string(), "010101010101010101010101010101011111111111111111");

◆ from() [2/5]

template<Unsigned Word = usize>

template<BitStore Src>

constexpr BitVector gf2::BitVector< Word >::from ( Src const & src )

inlinestaticconstexpr

Factory method to construct a bit-vector by copying all the bits from any other bit-store instance.

Note

Generally, we do not support interactions between bit-stores that use different underlying unsigned word types. This method is an exception – the src bit-store may use a different unsigned type from the one used here. It makes it possible to convert between bit-vector types which is occasionally useful.

Example

auto v = BitVector<u8>::from(BitVector<u8>::ones(10));
assert_eq(v.size(), 10);
assert_eq(v.to_string(), "1111111111");
auto w = BitVector<u8>::from(BitVector<u16>::ones(20));
assert_eq(w.size(), 20);
assert_eq(w.to_string(), "11111111111111111111");
auto x = BitVector<u8>::from(BitVector<u32>::zeros(10));
assert_eq(x.size(), 10);
assert_eq(x.to_string(), "0000000000");

◆ from() [3/5]

template<Unsigned Word = usize>

template<Unsigned Src>

constexpr BitVector gf2::BitVector< Word >::from ( Src src )

inlinestaticconstexpr

Factory method to construct a bit-vector by copying all the bits from any Unsigned instance. The resulting bit-vector will have the same size as the number of bits in the src unsigned integer.

Example

u8 s8 = 0b01010101;
auto u = BitVector<u8>::from(s8);
assert_eq(u.size(), 8);
assert_eq(u.to_string(), "10101010");
u16 s16 = 0b0101010101010101;
auto v = BitVector<u8>::from(s16);
assert_eq(v.size(), 16);
assert_eq(v.to_string(), "1010101010101010");
auto w = BitVector<u32>::from(s8);
assert_eq(w.size(), 8);
assert_eq(w.to_string(), "10101010");

◆ from() [4/5]

template<Unsigned Word = usize>

template<usize N>

constexpr BitVector gf2::BitVector< Word >::from ( std::bitset< N > const & src )

inlinestaticconstexpr

Factory method to construct a bit-vector from the bits of a std::bitset.

Note

A std::bitset prints its bit elements in bit-order ...b2b1b0., we print in vector-order b0b1b2...

Example

std::bitset<10> src{0b1010101010};
auto v = BitVector<>::from(src);
assert_eq(v.to_string(), "0101010101");

◆ from() [5/5]

template<Unsigned Word = usize>

constexpr BitVector gf2::BitVector< Word >::from	(	usize	size,
		std::invocable< usize > auto	f )

inlinestaticconstexpr

Factory method to construct a bit-vector by repeatedly calling f(i) for i in [0, size).

Parameters

size	The length of the bit-vector to generate.
f	The function to call for each index i in [0, size).

Example

auto v = BitVector<u8>::from(10, [](usize i) { return i % 2 == 0; });
assert_eq(v.size(), 10);
assert_eq(v.to_string(), "1010101010");

◆ from_binary_string()

template<Unsigned Word = usize>

std::optional< BitVector > gf2::BitVector< Word >::from_binary_string	(	std::string_view	sv,
		bool	no_punctuation = false )

inlinestatic

Factory method to construct a bit-vector from a binary string, returning std::nullopt on failure.

The string can contain whitespace, commas, single quotes, and underscores. If the second argument is true, then the string is assumed to have none of the above characters. There can always be a "0b" prefix.

Example

auto v = BitVector<u8>::from_binary_string("0b1010'1010'10").value();
assert_eq(v.to_string(), "1010101010");
auto u = BitVector<u8>::from_binary_string("").value();
assert_eq(u.to_string(), "");

◆ from_hex_string()

template<Unsigned Word = usize>

std::optional< BitVector > gf2::BitVector< Word >::from_hex_string	(	std::string_view	sv,
		bool	no_punctuation = false )

inlinestatic

Factory method to construct a bit-vector from a hex string, returning std::nullopt on failure.

The hex string should consist of the characters 0-9, A-F, a-f, with an optional prefix "0x" or "0X". The string may also have a suffix of the form ".base" where base is one of 2, 4 or 8 which indicates that the last digit should be interpreted as a base base number. This allows for bit-vectors whose length is not a multiple of 4.

Example

auto v1 = gf2::BitVector<>::from_hex_string("0xAA").value();
assert_eq(v1.to_string(), "10101010");
auto v2 = gf2::BitVector<>::from_hex_string("0x1").value();
assert_eq(v2.to_string(), "0001");
auto v3 = gf2::BitVector<>::from_hex_string("0x1.8").value();
assert_eq(v3.to_string(), "001");
auto v4 = gf2::BitVector<>::from_hex_string("0x1.4").value();
assert_eq(v4.to_string(), "01");
auto v5 = gf2::BitVector<>::from_hex_string("0x1.2").value();
assert_eq(v5.to_string(), "1");

◆ from_string()

template<Unsigned Word = usize>

std::optional< BitVector > gf2::BitVector< Word >::from_string ( std::string_view sv )

inlinestatic

Factory method to construct a bit-vector from a string s, returning std::nullopt on failure.

The string can contain whitespace, commas, single quotes, and underscores and optionally a "0b", "0x", or "0X" prefix. If there is no prefix, and the string only contains '0' and '1' characters, we assume the string is binary. To force getting it interpreted as a hex string, add a prefix of "0x" or "0X".

A hex string can have a suffix of ".2", ".4", or ".8" to indicate the base of the last digit/character. This allows for bit-vectors of any length as opposed to just a multiple of 4.

Example

auto v1 = BitVector<>::from_string("0b1010_1010_10").value();
assert_eq(v1.to_string(), "1010101010");
auto v2 = BitVector<>::from_string("AA").value();
assert_eq(v2.to_string(), "10101010");
auto v3 = BitVector<>::from_string("1010'1010").value();
assert_eq(v3.to_string(), "10101010");
auto v4 = BitVector<>::from_string("0x1.8").value();
assert_eq(v4.to_string(), "001");

◆ front()

template<Unsigned Word = usize>

bool gf2::BitVector< Word >::front ( ) const

inlineconstexpr

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

Panics

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

Example

auto v = BitVector<>::ones(10);
assert_eq(v.front(), true);
v.set_all(false);
assert_eq(v.front(), false);

◆ get()

template<Unsigned Word = usize>

bool gf2::BitVector< Word >::get ( usize i ) const

inlineconstexpr

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

Panics

In debug mode the index i is bounds-checked.

Example

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

◆ is_empty()

template<Unsigned Word = usize>

bool gf2::BitVector< Word >::is_empty ( ) const

inlineconstexpr

Returns true if the bit-vector is empty, false otherwise.

Example

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

◆ last_set()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitVector< Word >::last_set ( ) const

inlineconstexpr

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

Example

auto v = BitVector<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});
BitVector empty;
assert(empty.last_set() == std::optional<usize>{});

◆ last_unset()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitVector< Word >::last_unset ( ) const

inlineconstexpr

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

Example

auto v = BitVector<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});
BitVector empty;
assert(empty.last_unset() == std::optional<usize>{});

◆ leading_zeros()

template<Unsigned Word = usize>

usize gf2::BitVector< Word >::leading_zeros ( ) const

inlineconstexpr

Returns the number of leading zeros in the bit-vector.

Example

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

◆ next_set()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitVector< Word >::next_set ( usize index ) const

inlineconstexpr

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

Example

auto v = BitVector<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<Unsigned Word = usize>

std::optional< usize > gf2::BitVector< Word >::next_unset ( usize index ) const

inlineconstexpr

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

Example

auto v = BitVector<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>{});
BitVector empty;
assert(empty.next_unset(0) == std::optional<usize>{});

◆ none()

template<Unsigned Word = usize>

bool gf2::BitVector< Word >::none ( ) const

inlineconstexpr

Returns true if no bits in the bit-vector are set, false otherwise.

Note: Empty bit-vectors have no set bits (logical connective for none is AND with identity true).

Example

BitVector v{10};
assert_eq(v.none(), true);
v.set(0);
assert_eq(v.none(), false);

◆ offset()

template<Unsigned Word = usize>

u8 gf2::BitVector< Word >::offset ( ) const

inlineconstexpr

Returns the offset (in bits) of the first bit in the bit-vector within the first word.

This is always zero for BitVector.

◆ ones()

template<Unsigned Word = usize>

constexpr BitVector gf2::BitVector< Word >::ones ( usize n )

inlinestaticconstexpr

Factory method to generate a bit-vector of length n where the elements are all 1.

Example

assert_eq(BitVector<>::ones(10).to_string(), "1111111111");

◆ operator[]() [1/2]

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::operator[] ( usize i )

inlineconstexpr

Returns a "reference" to the bit element i.

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.

Panics

In debug mode the index i is bounds-checked.

Example

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

◆ operator[]() [2/2]

template<Unsigned Word = usize>

bool gf2::BitVector< Word >::operator[] ( usize i ) const

inlineconstexpr

Returns the boolean value of the bit element i.

Panics

In debug mode the index i is bounds-checked.

Example

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

◆ pop()

template<Unsigned Word = usize>

std::optional< bool > gf2::BitVector< Word >::pop ( )

inlineconstexpr

Removes the last bit from the bit-vector and returns it or std::nullopt if the bit-vector is empty.

Example

BitVector v;
v.push(1);
v.push(0);
assert(v.to_string() == "10");
auto b1 = v.pop();
assert_eq(*b1, false);
assert(v.to_string() == "1");
auto b2 = v.pop();
assert_eq(*b2, true);
assert(v.to_string() == "");
auto b3 = v.pop();
assert(b3 == std::nullopt);

◆ previous_set()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitVector< Word >::previous_set ( usize index ) const

inlineconstexpr

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

Example

auto v = BitVector<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<Unsigned Word = usize>

std::optional< usize > gf2::BitVector< Word >::previous_unset ( usize index ) const

inlineconstexpr

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

Example

auto v = BitVector<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>{});
BitVector empty;
assert(empty.previous_unset(0) == std::optional<usize>{});

◆ push()

template<Unsigned Word = usize>

BitVector & gf2::BitVector< Word >::push ( bool b )

inlineconstexpr

Pushes a single bit b onto the bit-vector.

Returns a reference to the current object for chaining.

Example

BitVector v;
v.push(1);
assert(v.to_string() == "1");
v.push(0);
assert(v.to_string() == "10");

◆ random()

template<Unsigned Word = usize>

BitVector gf2::BitVector< Word >::random	(	usize	size,
		double	p = 0.5,
		u64	seed = 0 )

inlinestatic

Factory method to generate a bit-vector of size size where the elements are picked at random.

The default call BitVector<>::random(size) produces a random bit-vector with each bit being 1 with probability 0.5 and where the RNG is seeded from entropy.

Parameters

size	The length of the bit-vector to generate.
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).

If p < 0 then the bit-vector is all zeros, if p > 1 then the bit-vector is all ones.

Example

u64 seed = 1234567890;
auto u = BitVector<>::random(10, 0.5, seed);
auto v = BitVector<>::random(10, 0.5, seed);
assert(u == v);

◆ remaining_capacity()

template<Unsigned Word = usize>

usize gf2::BitVector< Word >::remaining_capacity ( ) const

inlineconstexpr

Returns the number of additional elements we can store in the bit-vector without reallocating.

Example

BitVector<u64> v1(10);

assert_eq(v1.remaining_capacity(), 54);

◆ resize()

template<Unsigned Word = usize>

BitVector & gf2::BitVector< Word >::resize ( usize n )

inlineconstexpr

Resize the bit-vector so that its size() is n.

If n is greater than the bit-vector's current size, then the new elements are set to 0.
If n is less than the bit-vector's current size, then the bit-vector is truncated.

Example

auto v = BitVector<u8>::ones(1000);
v.resize(10);
assert_eq(v.to_string(), "1111111111");
v.resize(15);
assert_eq(v.to_string(), "111111111100000");

◆ riffled() [1/2]

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::riffled ( ) const

inlineconstexpr

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

If this bit-vector 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 = BitVector<u8>::ones(10);
auto dst = v.riffled();
assert_eq(dst.to_string(), "1010101010101010101");

◆ riffled() [2/2]

template<Unsigned Word = usize>

void gf2::BitVector< Word >::riffled ( BitVector< word_type > & dst ) const

inlineconstexpr

Interleaves the bits of this bit-vector with zeros storing the result into the bit-vector dst.

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

Note: There is no last zero bit in dst.

Example

auto v = BitVector<u8>::ones(10);
BitVector<u8> dst;
v.riffled(dst);
assert_eq(dst.to_string(), "1010101010101010101");

◆ seeded_random()

template<Unsigned Word = usize>

BitVector gf2::BitVector< Word >::seeded_random	(	usize	size,
		u64	seed )

inlinestatic

Factory method to generate a bit-vector of size size where the elements are from independent fair coin flips generated from an RNG seeded with the given seed.

This allows one to have reproducible random bit-vectors, which is useful for testing and debugging.

Parameters

size	The length of the bit-vector to generate.
seed	The seed to use for the random number generator (if you set this to 0 then entropy is used).

If p < 0 then the bit-vector is all zeros, if p > 1 then the bit-vector is all ones.

Example

u64 seed = 1234567890;
auto u = BitVector<>::seeded_random(10, seed);
auto v = BitVector<>::seeded_random(10, seed);
assert(u == v);

◆ set()

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::set	(	usize	i,
		bool	value = true )

inlineconstexpr

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

Panics

In debug mode the index i is bounds-checked.

Example

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

◆ set_all()

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::set_all ( bool value = true )

inlineconstexpr

Sets the bits in the bit-vector to the boolean value and returns a reference to this for chaining.

By default, all bits are set to true.

Example

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

◆ set_bits()

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::set_bits ( ) const

inlineconstexpr

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

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

Example

auto v = BitVector<u8>::alternating(10);
assert_eq(v.to_string(), "1010101010");
auto indices = std::ranges::to<std::vector>(v.set_bits());
assert_eq(indices, (std::vector<usize>{0, 2, 4, 6, 8}));

◆ set_word()

template<Unsigned Word = usize>

void gf2::BitVector< Word >::set_word	(	usize	i,
		Word	word )

inlineconstexpr

Sets word i in the bit-vector's underlying word store to value (masked if necessary).

The final word in the store may not be fully occupied but we ensure that unused bits remain set to 0.

Panics

In debug mode the index is bounds checked.

Example

auto v = BitVector<u8>::zeros(10);
assert_eq(v.to_string(), "0000000000");
v.set_word(1, 0b1111'1111);
assert_eq(v.to_string(), "0000000011");
assert_eq(v.count_ones(), 2);

◆ shrink_to_fit()

template<Unsigned Word = usize>

BitVector & gf2::BitVector< Word >::shrink_to_fit ( )

inlineconstexpr

Shrinks the bit-vector's capacity as much as possible.

This method may do nothing.

Example

auto v = BitVector<u8>::ones(1000);
v.resize(15);
v.shrink_to_fit();
assert_eq(v.capacity(), 16);

◆ size()

template<Unsigned Word = usize>

usize gf2::BitVector< Word >::size ( ) const

inlineconstexpr

Returns the number of bit-elements in the bit-vector.

Example

BitVector v0;
assert_eq(v0.size(), 0);
BitVector<u8> v1(10);
assert_eq(v1.size(), 10);

◆ span() [1/2]

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::span	(	usize	begin,
		usize	end )

inlineconstexpr

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

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

Panics

This method panics if the range is not valid.

Example

auto v = BitVector<>::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<Unsigned Word = usize>

auto gf2::BitVector< Word >::span	(	usize	begin,
		usize	end ) const

inlineconstexpr

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

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

Panics

This method panics if the range is not valid.

Example

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

◆ split_at() [1/2]

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::split_at ( usize at ) const

inlineconstexpr

Views the bit-vector 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.

Panics

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

Example

auto v = BitVector<>::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<Unsigned Word = usize>

void gf2::BitVector< Word >::split_at	(	usize	at,
		BitVector< word_type > &	left,
		BitVector< word_type > &	right ) const

inlineconstexpr

Views the bit-vector 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.

Panics

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

Example

auto v = BitVector<>::alternating(10);
BitVector 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");

◆ split_off() [1/2]

template<Unsigned Word = usize>

BitVector< Word > gf2::BitVector< Word >::split_off ( usize at )

inlineconstexpr

Splits a bit-vector into two at the given index, returning a new BitVector.

The returned bit-vector contains the bits from at to the end of the bit-vector. The bit-vector is resized to only contain the bits in the half-open range [0, at).

Panics

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

Example

auto v = BitVector<>::alternating(10);
auto w = v.split_off(5);
assert_eq(v.to_string(), "10101");
assert_eq(w.to_string(), "01010");

◆ split_off() [2/2]

template<Unsigned Word = usize>

void gf2::BitVector< Word >::split_off	(	usize	at,
		BitVector< Word > &	dst )

inlineconstexpr

Splits a bit-vector into two at the given index, returning the second part in dst.

On return, dst contains the bits from at to the end of the bit-vector. The bit-vector is resized to only contain the bits in the half-open range [0, at).

Panics

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

Example

auto v = BitVector<>::alternating(10);
BitVector dst;
v.split_off(5, dst);
assert_eq(v.to_string(), "10101");
assert_eq(dst.to_string(), "01010");

◆ split_off_unsigned()

template<Unsigned Word = usize>

template<Unsigned Dst = Word>

std::optional< Dst > gf2::BitVector< Word >::split_off_unsigned ( )

inlineconstexpr

Split off a single arbitrary sized unsigned integer off the end of the bit-vector and returns it or std::nullopt if the bit-vector is empty.

Note

You can split off a primitive unsigned integer type of any size from the end of a non-empty bit-vector. For example, if v is a BitVector<u8>with 22 elements, then you can split off a u16 value from the end of v by calling v.split_off_unsigned<u16>(). This leaves the bit-vector with 6 elements.

Examples

auto v = BitVector<u8>::ones(22);
auto x16 = v.split_off_unsigned<u16>();
assert_eq(*x16, 0b1111'1111'1111'1111);
assert_eq(v.size(), 6);
assert_eq(v.to_string(), "111111");
auto w = BitVector<u8>::alternating(24);
auto x8 = w.split_off_unsigned<u8>();
assert_eq(*x8, 0b0101'0101);
assert_eq(w.size(), 16);
assert_eq(w.to_string(), "1010101010101010");
w.append(*x8);
assert_eq(w.to_string(), "101010101010101010101010");

◆ store() [1/2]

template<Unsigned Word = usize>

Word * gf2::BitVector< Word >::store ( )

inlineconstexpr

Returns a pointer to the underlying store of words.

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

Example

auto v = BitVector<u8>::ones(10);
auto ptr = v.store();
assert_eq(*ptr, 0b1111'1111);

◆ store() [2/2]

template<Unsigned Word = usize>

const Word * gf2::BitVector< Word >::store ( ) const

inlineconstexpr

Returns a const pointer to the underlying store of words .

Example

auto v = BitVector<u8>::ones(10);
auto ptr = v.store();
assert_eq(*ptr, 0b1111'1111);

◆ store_words()

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::store_words ( ) const

inlineconstexpr

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

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

Example

auto v = BitVector<u8>::ones(10);
assert_eq(v.to_string(), "1111111111");
auto words = std::ranges::to<std::vector>(v.store_words());
assert_eq(words, (std::vector<u8>{0b1111'1111, 0b0000'0011}));

◆ sub()

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::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.

Panics

This method panics if the range is not valid.

Example

auto v = BitVector<>::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<Unsigned Word = usize>

auto gf2::BitVector< Word >::swap	(	usize	i0,
		usize	i1 )

inlineconstexpr

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

Panics

In debug mode the indices are bounds-checked.

Example

auto v = BitVector<>::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<Unsigned Word = usize>

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

inline

Returns a binary string representation of the bit-vector.

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

BitVector 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<Unsigned Word = usize>

std::string gf2::BitVector< Word >::to_hex_string ( ) const

inline

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

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

BitVector v0;
assert_eq(v0.to_hex_string(), "");
auto v1 = BitVector<>::ones(4);
assert_eq(v1.to_hex_string(), "F");
auto v2 = BitVector<>::ones(5);
assert_eq(v2.to_hex_string(), "F1.2");
auto v3 = BitVector<>::alternating(8);
assert_eq(v3.to_binary_string(), "10101010");
assert_eq(v3.to_hex_string(), "AA");

◆ to_pretty_string()

template<Unsigned Word = usize>

std::string gf2::BitVector< Word >::to_pretty_string ( ) const

inline

Returns a "pretty" string representation of the bit-vector.

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 = BitVector<>::alternating(10);
assert_eq(v.to_pretty_string(), "[1,0,1,0,1,0,1,0,1,0]");
BitVector empty;
assert_eq(empty.to_pretty_string(), "[]");

◆ to_string()

template<Unsigned Word = usize>

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

inline

Returns a binary string representation of the bit-vector.

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

BitVector 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() [1/2]

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::to_words ( ) const

inlineconstexpr

Returns a copy of the words underlying this bit-vector as a new std::vector<word_type>.

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

Example

auto v = BitVector<u8>::ones(10);
auto words = v.to_words();
assert_eq(words, (std::vector<u8>{0b1111'1111, 0b0000'0011}));

◆ to_words() [2/2]

template<Unsigned Word = usize>

void gf2::BitVector< Word >::to_words ( std::output_iterator< word_type > auto out )

inlineconstexpr

Returns a copy of the words underlying this bit-vector and puts them into the passed output iterator.

Note

The last word in the bit-vector may not be fully occupied but unused slots will be all zeros.
The output iterator must be able to accept values of the bit-vector's word_type.
The output iterator must have enough space to accept all the words in the bit-vector.
If there is extra space in the output iterator, those extra slots are left unchanged.

Example

auto v = BitVector<u8>::ones(10);
std::vector<u8> out8(v.words());
v.to_words(out8.begin());
assert_eq(out8, (std::vector<u8>{0b1111'1111, 0b0000'0011}));
std::vector<u16> out16(v.words());
v.to_words(out16.begin());
assert_eq(out16, (std::vector<u16>{0b1111'1111, 0b0000'0011}));

◆ trailing_zeros()

template<Unsigned Word = usize>

usize gf2::BitVector< Word >::trailing_zeros ( ) const

inlineconstexpr

Returns the number of trailing zeros in the bit-vector.

Example

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

◆ unit()

template<Unsigned Word = usize>

constexpr BitVector gf2::BitVector< Word >::unit	(	usize	n,
		usize	i )

inlinestaticconstexpr

Factory method to generate a "unit" bit-vector of length n where only element i is set.

This method panics if the condition i < n is not met.

Example

assert_eq(BitVector<>::unit(10, 0).to_string(), "1000000000");

assert_eq(BitVector<>::unit(10, 9).to_string(), "0000000001");

gf2::BitVector::unit

static constexpr BitVector unit(usize n, usize i)

Factory method to generate a "unit" bit-vector of length n where only element i is set.

Definition BitVector.h:226

◆ unset_bits()

template<Unsigned Word = usize>

auto gf2::BitVector< Word >::unset_bits ( ) const

inlineconstexpr

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

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

Example

auto v = BitVector<u8>::alternating(10);
assert_eq(v.to_string(), "1010101010");
auto indices = std::ranges::to<std::vector>(v.unset_bits());
assert_eq(indices, (std::vector<usize>{1, 3, 5, 7, 9}));

◆ with_capacity()

template<Unsigned Word = usize>

constexpr BitVector gf2::BitVector< Word >::with_capacity ( usize capacity )

inlinestaticconstexpr

Factory method to construct an empty bit-vector with at least the specified capacity.

Example

auto v = BitVector<>::with_capacity(10);
assert_eq(v.size(), 0);
assert(v.capacity() >=10);

◆ word()

template<Unsigned Word = usize>

Word gf2::BitVector< Word >::word ( usize i ) const

inlineconstexpr

Returns word i from the bit-vector's underlying word store.

The final word in the store may not be fully occupied but we guarantee that unused bits are set to 0.

Panics

In debug mode the index is bounds checked.

Example

auto v = BitVector<u8>::ones(10);
assert_eq(v.to_string(), "1111111111");
assert_eq(v.words(), 2);
assert_eq(v.word(0), 0b1111'1111);
assert_eq(v.word(1), 0b0000'0011);

◆ words()

template<Unsigned Word = usize>

usize gf2::BitVector< Word >::words ( ) const

inlineconstexpr

Returns the number of words in the bit-vector's underlying word store.

The bit-elements are packed into a standard vector with this number of words.

Example

BitVector v0;
assert_eq(v0.words(), 0);
BitVector<u8> v1(10);
assert_eq(v1.words(), 2);

◆ zeros()

template<Unsigned Word = usize>

constexpr BitVector gf2::BitVector< Word >::zeros ( usize n )

inlinestaticconstexpr

Factory method to generate a bit-vector of length n where the elements are all 0.

Example

auto v = BitVector<>::zeros(10);

assert_eq(v.to_string(), "0000000000");

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BitVector() [1/2]

Example

◆ BitVector() [2/2]

Example

Member Function Documentation

◆ all()

Example

◆ alternating()

Example

◆ any()

Example

◆ append() [1/4]

Note

Example

◆ append() [2/4]

Note

Example

◆ append() [3/4]

Example

◆ append() [4/4]

Example

◆ append_digit()

Example

◆ append_hex_digit()

Example

◆ back()

Panics

Example

◆ biased_random()

Example

◆ bits() [1/2]

Note

Example

◆ bits() [2/2]

Note

Example

◆ capacity()

Example

◆ clean()

◆ clear()

◆ constant()

Example

◆ copy() [1/5]

Note

Panics

Example

◆ copy() [2/5]

Note

Panics

Example

◆ copy() [3/5]

Notes:

Panics

Example

◆ copy() [4/5]

Note

Panics

Example

◆ copy() [5/5]

Example

◆ count_ones()

Example

◆ count_zeros()

Example

◆ describe()

◆ fill_random()

Example

◆ first_set()

Example

◆ first_unset()

Example

◆ flip()

Panics

Example