gf2

The namespace for the gf2 library. More...

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

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

Functions
template<unsigned_word Word, typename Rhs> requires store_word_is<Rhs, Word>
constexpr auto	dot (const BitMat< Word > &lhs, const BitStore< Rhs > &rhs)
	Bit-matrix, bit-store multiplication, M * v, returning a new bit-vector.
template<unsigned_word Word, typename Rhs> requires store_word_is<Rhs, Word>
constexpr auto	operator* (const BitMat< Word > &lhs, const BitStore< Rhs > &rhs)
	Operator form for bit-matrix, bit-vector multiplication, M * v, returning a new bit-vector.
template<unsigned_word Word, typename Lhs> requires store_word_is<Lhs, Word>
constexpr auto	dot (const BitStore< Word > &lhs, const BitMat< Word > &rhs)
	Bit-vector, bit-matrix multiplication, v * M`, returning a new bit-vector.
template<unsigned_word Word, typename Lhs> requires store_word_is<Lhs, Word>
constexpr auto	operator* (const BitStore< Lhs > &lhs, const BitMat< Word > &rhs)
	Operator form for bit-vector, bit-matrix multiplication, v * M, returning a new bit-vector.
template<unsigned_word Word>
constexpr auto	dot (const BitMat< Word > &lhs, const BitMat< Word > &rhs)
	Bit-matrix, bit-matrix multiplication, M * N, returning a new bit-matrix.
template<unsigned_word Word>
constexpr auto	operator* (const BitMat< Word > &lhs, const BitMat< Word > &rhs)
	Operator form for bit-matrix, bit-matrix multiplication, M * N, returning a new bit-matrix.
template<unsigned_word Word, typename Rhs> requires store_word_is<Rhs, Word>
std::string	string_for (const BitMat< Word > &A, const BitStore< Rhs > &b)
	Returns a string that shows a bit-matrix and a bit-vector side-by-side.
template<unsigned_word Word, typename Rhs> requires store_word_is<Rhs, Word>
std::string	string_for (const BitMat< Word > &A, const BitStore< Rhs > &b, const BitStore< Rhs > &c)
	Returns a string that shows a bit-matrix and two bit-vectors side-by-side.
template<unsigned_word Word, typename Rhs> requires store_word_is<Rhs, Word>
std::string	string_for (const BitMat< Word > &A, const BitStore< Rhs > &b, const BitStore< Rhs > &c, const BitStore< Rhs > &d)
	Returns a string that shows a bit-matrix and three bit-vectors side-by-side.
template<unsigned_word Word>
std::string	string_for (const BitMat< Word > &A, const BitMat< Word > &B)
	Returns a string that shows two bit-matrices side-by-side.
template<unsigned_word Word>
std::string	string_for (const BitMat< Word > &A, const BitMat< Word > &B, const BitMat< Word > &C)
	Returns a string that shows three bit-matrices side-by-side.
template<typename Lhs, typename Rhs>
constexpr bool	operator== (const BitStore< Lhs > &lhs, const BitStore< Rhs > &rhs)
	Checks that any pair of bit-stores are equal in content.
template<typename Lhs, typename Rhs>
auto	join (const BitStore< Lhs > &lhs, const BitStore< Rhs > &rhs)
	Returns a new bit-vector formed by joining two bit-stores lhs and rhs.
template<typename Lhs, typename Rhs> requires store_words_match<Lhs, Rhs>
constexpr bool	dot (const BitStore< Lhs > &lhs, const BitStore< Rhs > &rhs)
	Returns the dot product of lhs and rhs as a boolean value.
template<typename Lhs, typename Rhs> requires store_words_match<Lhs, Rhs>
constexpr bool	operator* (const BitStore< Lhs > &lhs, const BitStore< Rhs > &rhs)
	Operator * is used for the dot product of lhs and rhs as a boolean value.
template<typename Lhs, typename Rhs> requires store_words_match<Lhs, Rhs>
auto	convolve (const BitStore< Lhs > &lhs, const BitStore< Rhs > &rhs)
	Returns the convolution of this store with the given rhs store as a new bit-vector.
Constructors:
template<unsigned_word Word>
constexpr Word	with_set_bits (u8 begin, u8 end)
	Returns an unsigned_word with the bits in the half-open range [begin, end) set to 1 and the others set to 0.
template<unsigned_word Word>
constexpr Word	with_unset_bits (u8 begin, u8 end)
	Returns an unsigned_word with the bits in the half-open range [begin, end) set to 0 and the others set to 1.
Bit mutators:
template<unsigned_word Word>
constexpr void	set_bits (Word &word, u8 begin, u8 end)
	Sets the bits in the half-open range [begin, end) of word to one, leaving the others unchanged.
template<unsigned_word Word>
constexpr void	reset_bits (Word &word, u8 begin, u8 end)
	Resets the bits in the half-open range [begin, end) of word to zero, leaving the others unchanged.
template<unsigned_word Word>
constexpr void	set_except_bits (Word &word, u8 begin, u8 end)
	Sets the bits of word to 1 except for those in the half-open range [begin, end) which are unchanged.
template<unsigned_word Word>
constexpr void	reset_except_bits (Word &word, u8 begin, u8 end)
	Sets the bits of word to 0 except for those in the half-open range [begin, end) which are unchanged.
template<unsigned_word Word>
constexpr Word	reverse_bits (Word word)
	Returns a copy of word with all its bits reversed.
template<unsigned_word Word, typename Other> requires std::convertible_to<Other, Word>
constexpr void	replace_bits (Word &word, u8 begin, u8 end, Other other)
	Replace the bits of word in the range [begin, end) with the bits from other leaving the rest unchanged.
Bit Riffling:
template<unsigned_word Word>
constexpr std::pair< Word, Word >	riffle (Word word)
	Riffles an unsigned_word into a pair of others containing the bits in the original word interleaved with zeros.
Bit Counts:
template<unsigned_word Word>
constexpr u8	count_ones (Word word)
	Returns the number of set bits in an unsigned_word.
template<unsigned_word Word>
constexpr u8	count_zeros (Word word)
	Returns the number of unset bits in an unsigned_word.
template<unsigned_word Word>
constexpr u8	trailing_zeros (Word word)
	Returns the number of trailing zeros in an unsigned_word.
template<unsigned_word Word>
constexpr u8	leading_zeros (Word word)
	Returns the number of leading zeros in an unsigned_word.
template<unsigned_word Word>
constexpr u8	trailing_ones (Word word)
	Returns the number of trailing ones in an unsigned_word.
template<unsigned_word Word>
constexpr u8	leading_ones (Word word)
	Returns the number of leading ones in an unsigned_word.
template<unsigned_word Word>
constexpr std::optional< u8 >	lowest_set_bit (Word word)
	Returns the index of the lowest set bit in an unsigned_word or std::nullopt if no bits are set.
Searches:
template<unsigned_word Word>
constexpr std::optional< u8 >	highest_set_bit (Word word)
	Returns the index of the highest set bit in an unsigned_word or std::nullopt if no bits are set.
template<unsigned_word Word>
constexpr std::optional< u8 >	lowest_unset_bit (Word word)
	Returns the index of the lowest unset bit in an unsigned_word or std::nullopt if there are no unset bits.
template<unsigned_word Word>
constexpr std::optional< u8 >	highest_unset_bit (Word word)
	Returns the index of the highest unset bit in an unsigned_word or std::nullopt if there are none.
Stringification:
template<unsigned_word Word>
static std::string	to_binary_string (Word word)
	Returns the binary string representation of an unsigned_word showing all the bits.
template<unsigned_word Word>
static std::string	to_hex_string (Word word)
	Returns the hex string representation of an unsigned_word showing all the bits.
Bit Locations:
template<unsigned_word Word>
constexpr usize	words_needed (usize n_bits)
	Returns the number of unsigned_words needed to store n_bits bits.
template<unsigned_word Word>
constexpr usize	word_index (usize i)
	Returns the index of the unsigned_word word holding bit element i.
template<unsigned_word Word>
constexpr u8	bit_offset (usize i)
	Returns the bit position within the containing word for bit element i.
template<unsigned_word Word>
constexpr std::pair< usize, u8 >	index_and_offset (usize i)
	Returns a pair of the index of the word and the bit position within the word for bit element i.
template<unsigned_word Word>
constexpr std::pair< usize, Word >	index_and_mask (usize i)
	Returns a pair of the index of the word and a mask isolating bit element i.

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

Detailed Description

The namespace for the gf2 library.

Function Documentation

bit_offset()

template<unsigned_word Word>

u8 gf2::bit_offset ( usize i )

constexpr

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

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

Example

assert_eq(bit_offset<u8>(0), 0);
assert_eq(bit_offset<u8>(8), 0);
assert_eq(bit_offset<u8>(19), 3);

convolve()

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

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

Returns the convolution of this store with the given rhs store as a new bit-vector.

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

Example

auto lhs = BitVec<>::ones(3);
auto rhs = BitVec<>::ones(2);
auto result = convolve(lhs, rhs);
assert_eq(result.to_string(), "1001");

count_ones()

template<unsigned_word Word>

u8 gf2::count_ones ( Word word )

constexpr

Returns the number of set bits in an unsigned_word.

Example

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

count_zeros()

template<unsigned_word Word>

u8 gf2::count_zeros ( Word word )

constexpr

Returns the number of unset bits in an unsigned_word.

Example

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

dot() [1/2]

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

bool gf2::dot ( const BitStore< Lhs > & lhs, const BitStore< Rhs > & rhs )

constexpr

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

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

Note

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

Example

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

dot() [2/2]

template<unsigned_word Word, typename Lhs>
requires store_word_is<Lhs, Word>

auto gf2::dot ( const BitStore< Word > & lhs, const BitMat< Word > & rhs )

constexpr

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

Note

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

highest_set_bit()

template<unsigned_word Word>

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

constexpr

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

Example

assert(highest_set_bit(u8{0b0000'0000}) == std::optional<u8>{});
assert(highest_set_bit(u8{0b0000'0001}) == std::optional<u8>{0});
assert(highest_set_bit(u8{0b0000'0010}) == std::optional<u8>{1});
assert(highest_set_bit(u8{0b1000'0000}) == std::optional<u8>{7});

highest_unset_bit()

template<unsigned_word Word>

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

constexpr

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

Example

assert(highest_unset_bit(u8{0b1111'1111}) == std::optional<u8>{});
assert(highest_unset_bit(u8{0b1100'0000}) == std::optional<u8>{5});
assert(highest_unset_bit(u8{0b0001'0011}) == std::optional<u8>{7});
assert(highest_unset_bit(u8{0b1000'0000}) == std::optional<u8>{6});

index_and_mask()

template<unsigned_word Word>

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

constexpr

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

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

Example

assert_eq(index_and_mask<u8>(0), (std::pair{0, 1}));
assert_eq(index_and_mask<u8>(8), (std::pair{1, 1}));
assert_eq(index_and_mask<u8>(19), (std::pair{2, 1 << 3}));

index_and_offset()

template<unsigned_word Word>

std::pair< usize, u8 > gf2::index_and_offset ( usize i )

constexpr

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

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

Example

assert_eq(index_and_offset<u8>(0), (std::pair{0, 0}));
assert_eq(index_and_offset<u8>(8), (std::pair{1, 0}));
assert_eq(index_and_offset<u8>(19), (std::pair{2, 3}));

join()

template<typename Lhs, typename Rhs>

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

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

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

Example

auto lhs = BitVec<u16>::zeros(12);
auto rhs = BitVec<u8>::ones(12);
auto v = join(lhs, rhs);
assert_eq(v.to_string(), "000000000000111111111111");

leading_ones()

template<unsigned_word Word>

u8 gf2::leading_ones ( Word word )

constexpr

Returns the number of leading ones in an unsigned_word.

Example

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

leading_zeros()

template<unsigned_word Word>

u8 gf2::leading_zeros ( Word word )

constexpr

Returns the number of leading zeros in an unsigned_word.

Example

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

lowest_set_bit()

template<unsigned_word Word>

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

constexpr

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

Example

assert(lowest_set_bit(u8{0b0000'0000}) == std::optional<u8>{});
assert(lowest_set_bit(u8{0b0000'0001}) == std::optional<u8>{0});
assert(lowest_set_bit(u8{0b0000'0010}) == std::optional<u8>{1});
assert(lowest_set_bit(u8{0b1000'0000}) == std::optional<u8>{7});

lowest_unset_bit()

template<unsigned_word Word>

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

constexpr

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

Example

assert(lowest_unset_bit(u8{0b1111'1111}) == std::optional<u8>{});
assert(lowest_unset_bit(u8{0b0001'1000}) == std::optional<u8>{0});
assert(lowest_unset_bit(u8{0b0000'1001}) == std::optional<u8>{1});
assert(lowest_unset_bit(u8{0b1000'1111}) == std::optional<u8>{4});

operator*() [1/2]

template<unsigned_word Word, typename Lhs>
requires store_word_is<Lhs, Word>

auto gf2::operator* ( const BitStore< Lhs > & lhs, const BitMat< Word > & rhs )

constexpr

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

Note

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

operator*() [2/2]

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

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

constexpr

Operator * is used for the dot product of lhs and rhs as a boolean value.

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

Note

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

Example

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

operator==()

template<typename Lhs, typename Rhs>

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

constexpr

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

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

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

replace_bits()

template<unsigned_word Word, typename Other>
requires std::convertible_to<Other, Word>

void gf2::replace_bits ( Word & word, u8 begin, u8 end, Other other )

constexpr

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

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

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

Note

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

Example

u8 word = 0b1111'1111;
replace_bits(word, 1, 3, 0b0000'0000);
assert_eq(word, 0b1111'1001);

reset_bits()

template<unsigned_word Word>

void gf2::reset_bits ( Word & word, u8 begin, u8 end )

constexpr

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

Note

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

Example

u8 word = 0b1111'1111;
reset_bits(word, 1, 3);
assert_eq(word, 0b1111'1001);

reset_except_bits()

template<unsigned_word Word>

void gf2::reset_except_bits ( Word & word, u8 begin, u8 end )

constexpr

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

Note

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

Example

u8 word = 0b1111'1111;
reset_except_bits(word, 1, 3);
assert_eq(word, 0b000'0110);

reverse_bits()

template<unsigned_word Word>

Word gf2::reverse_bits ( Word word )

constexpr

Returns a copy of word with all its bits reversed.

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

Example

u32  n32 = 0x12345678;
auto m32 = reverse_bits(n32);
assert_eq(m32, 0x1e6a2c48);
u64  n64 = 0x1234567890123456;
auto m64 = reverse_bits(n64);
assert_eq(m64, 0x6a2c48091e6a2c48);
u16 zero = 0;
assert_eq(reverse_bits(zero), 0);

riffle()

template<unsigned_word Word>

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

constexpr

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

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

Example

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

set_bits()

template<unsigned_word Word>

void gf2::set_bits ( Word & word, u8 begin, u8 end )

constexpr

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

Note

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

Example

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

set_except_bits()

template<unsigned_word Word>

void gf2::set_except_bits ( Word & word, u8 begin, u8 end )

constexpr

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

Note

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

Example

u8 word = 0b0000'0000;
set_except_bits(word, 1, 3);
assert_eq(word, 0b1111'1001);

to_binary_string()

template<unsigned_word Word>

std::string gf2::to_binary_string ( Word word )

inlinestatic

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

Example

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

to_hex_string()

template<unsigned_word Word>

std::string gf2::to_hex_string ( Word word )

inlinestatic

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

Example

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

trailing_ones()

template<unsigned_word Word>

u8 gf2::trailing_ones ( Word word )

constexpr

Returns the number of trailing ones in an unsigned_word.

Example

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

trailing_zeros()

template<unsigned_word Word>

u8 gf2::trailing_zeros ( Word word )

constexpr

Returns the number of trailing zeros in an unsigned_word.

Example

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

with_set_bits()

template<unsigned_word Word>

Word gf2::with_set_bits ( u8 begin, u8 end )

constexpr

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

Note

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

Example

assert_eq(with_set_bits<u8>(0, 0), 0b0000'0000);
assert_eq(with_set_bits<u8>(0, 1), 0b0000'0001);
assert_eq(with_set_bits<u8>(0, 2), 0b0000'0011);
assert_eq(with_set_bits<u8>(1, 3), 0b0000'0110);
assert_eq(with_set_bits<u8>(0, 8), 0b1111'1111);

with_unset_bits()

template<unsigned_word Word>

Word gf2::with_unset_bits ( u8 begin, u8 end )

constexpr

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

Note

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

Example

assert_eq(with_unset_bits<u8>(0, 0), 0b1111'1111);
assert_eq(with_unset_bits<u8>(0, 1), 0b1111'1110);
assert_eq(with_unset_bits<u8>(0, 2), 0b1111'1100);
assert_eq(with_unset_bits<u8>(1, 3), 0b1111'1001);
assert_eq(with_unset_bits<u8>(0, 8), 0b0000'0000);

word_index()

template<unsigned_word Word>

usize gf2::word_index ( usize i )

constexpr

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

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

Example

assert_eq(word_index<u8>(0), 0);
assert_eq(word_index<u8>(8), 1);
assert_eq(word_index<u8>(19), 2);

words_needed()

template<unsigned_word Word>

usize gf2::words_needed ( usize n_bits )

constexpr

Returns the number of unsigned_words needed to store n_bits bits.

Example

assert_eq(words_needed<u8>(0), 0);
assert_eq(words_needed<u8>(8), 1);
assert_eq(words_needed<u8>(19), 3);

Variable Documentation

ALTERNATING

template<unsigned_word Word>

Word gf2::ALTERNATING = MAX<Word> / 3

constexpr

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

Example

assert_eq(ALTERNATING<u8>, 0b0101'0101);

BITS

template<unsigned_word Word>

u8 gf2::BITS = std::numeric_limits<Word>::digits

constexpr

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

Example

assert_eq(BITS<u16>, 16);

MAX

template<unsigned_word Word>

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

constexpr

The unsigned_word instance with all its bits set to 1.

Example

assert_eq(MAX<u8>, 255);

ONE

template<unsigned_word Word>

Word gf2::ONE = Word{1}

constexpr

The one value for an unsigned_word type.

Example

assert_eq(ONE<u8>, 1);

ZERO

template<unsigned_word Word>

Word gf2::ZERO = Word{0}

constexpr

The zero value for an unsigned_word type.

Example

assert_eq(ZERO<u8>, 0);