Introduction

A gf2::BitSet is a fixed size vector of bit elements stored compactly in an array of unsigned integer words.
The size is set at compile time by a template parameter referred to here as N.

The class satisfies the gf2::BitStore concept, which provides a rich API for manipulating the bits in the bit-set. The free functions defined for that concept are also pulled into the class as member functions. For example, if v is a gf2::BitSet, you can call v.count_ones() to count the number of set bits in the bit-set instead of calling the free function gf2::count_ones(v), though both forms are valid.

In mathematical terms, a bitset is a vector over GF2, the simplest Galois-Field with just two elements usually denoted 0 & 1, as the booleans true & false, or as the bits set & unset. Arithmetic over GF(2) is mod 2, so addition/subtraction becomes the XOR operation while multiplication/division becomes AND.

Note: Operations on and between bitsets and other objects in the gf2 library are implemented using bitwise operations on whole underlying words at a time. These operations are highly optimised in modern CPUs, allowing for fast computation even on large bitsets. It also means we never have to worry about overflows or carries as we would with normal integer arithmetic.

The gf2::BitSet class is a hybrid between a [std::array] and a std::bitset, along with extra mathematical features to facilitate numerical work, and in particular, linear algebra.

It is worth noting that a BitSet prints in vector-order.

For example, a bitset of size four will print as \(v_0 v_1 v_2 v_3\) with the elements in increasing index order, so the least significant vector element, \(v_0\), comes first on the left. Contrast that to a std::bitset, which always prints in bit-order. The equivalent std::bitset with four elements prints as \(b_3 b_2 b_1 b_0\) with the least significant bit \(b_0\) printed last on the right.

Of course, for many applications, printing in bit-order makes perfect sense. A bitset of four elements initialised to 0x1 will print 1000. A std::bitset prints the same value as 0001, which will be more natural in some settings.

However, our main aim is numerical work, where vector order is more natural. In particular, bit-order is unnatural for matrices over GF(2). It is too confusing to print a matrix in any order other than the one where the (0,0) element is at the top left, and proceed from there.

Declaration

The declaration of the bit-set class looks like:

template <usize N, Unsigned Word = usize>
class BitSet {
public:
    using word_type = Word;
    // ...
};

The first template parameter N specifies the number of bit elements in the bitset, which are all initialised to zero.

The Word template parameter specifies the underlying gf2::Unsigned integer type used to hold the bit-set's bits, and the default is usually the most efficient type for the target platform. On most modern platforms, that usize will be a 64-bit unsigned integer. The choice of underlying word type is exposed via the public word_type type alias as required by the gf2::BitStore concept.

If your application calls for a vast number of bit-sets with only a few bits each, you might consider using std::uint8_t as the Word type to save memory.

Note: You might notice that many of the doctests in the library use 8-bit underlying words. The reason is we want to exercise the various functions across word boundaries for modest, easily readable bit-stores.

Methods Overview

The gf2::BitSet class provides a rich set of methods for querying and manipulating, bit-sets. Here is an overview of the main methods available in the class:

Category	Description
Concept Methods	Methods needed to satisfy the gf2::BitStore concept.
Constructors	Methods to create bit-sets with various initial values..
Factory Constructors	Class methods to create bit-sets with specific fills.
Bit Access	Methods to access individual bit elements in a bit-set.
Queries	Methods to query the overall state of a bit-set.
Mutators	Methods to mutate the overall state of a bit-set.
Fills	Methods to fill a bit-set from various sources.
Spans	Methods to create non-owning views over a part of a bit-set — bit-spans.
Sub-vectors	Methods to pull out a clone of piece of a bit-set as new bit-vector.
Riffling	Methods to create bit-vectors that copy a bit-set with interleaved zeros.
Set/Unset Indices	Methods to find the indices of set & unset bits in a bit-set.
Iterators	Methods to create various iterators over a bit-set.
Stringification	Methods to create string representations of a bit-set.
Equality Operator	Operator to compare bit-stores, including bit-sets for content equality.
Bit Shifts	Operators to shift the bits in bit-sets left or right.
Bit-wise Operators	Operators to combine bit-stores using logical operations.
Arithmetic Operators	Operators to add or subtract bit-stores.
Other Functions	Dot products, convolutions, concatenation etc. for bit-sets.

Concept Methods

Bit-sets satisfy the gf2::BitStore concept and forwards many method calls to free functions defined for that concept. The concept requires us to provide the following methods:

Method Name	Description
gf2::BitSet::size	Returns N, the number of bit elements in the bitset.
gf2::BitSet::words	Returns the number of Words needed to store those elements.
gf2::BitSet::word	Returns the word for the passed index.
gf2::BitSet::set_word	Sets the word at the passed index to the passed value.
gf2::BitSet::store const	Returns a const pointer to the beginning of the Word store.
gf2::BitSet::store	Returns a non-const pointer to the beginning of the Word store.
gf2::BitSet::offset	For bitsets, this always returns 0.

These methods are trivial to implement for bit-sets.

The one place where care is needed is in the set_word method, which must ensure that any bits beyond the bitset's size remain set to zero.

Warning: While the gf2::BitSet::store method provides write access to the underlying words, you must be careful when modifying them directly. You must ensure that any bits beyond the bitset's size remain zero. The gf2::BitSet::set_word method takes care of this for you, so prefer using that method when possible.

Constructors

The default constructor for a gf2::BitSet<N> creates an a bit-set with N bits, all initialised to zero. You can also create a bit-vector with an initial fill using the following constructor:

Method Name	Description
gf2::BitSet()	Constructs a bit-vector with N zero elements.
gf2::BitSet(Word)	Constructs a bit-set of size N by repeatedly copying the bits from the Word

Factory Constructors

There are also many static factory construction functions.

Method Name	Description
gf2::BitSet::zeros	Returns a bit-set where all the elements are 0.
gf2::BitSet::ones	Returns a bit-set where all the elements are 1.
gf2::BitSet::constant	Returns a bit-set where all the elements are whatever is passed as a value.
gf2::BitSet::unit	Returns a bit-set where all the elements are zero except for a single 1.
gf2::BitSet::alternating	Returns a bit-set where all the elements follow the pattern 101010...
gf2::BitSet::from	Returns a BitVSet filled with bits from various sources.
gf2::BitSet::random	Returns a BitVSet with a random fill seeded from entropy.
gf2::BitSet::seeded_random	Returns a BitVSet with a reproducible random fill.
gf2::BitSet::biased_random	Returns a random BitSet where you set the probability of bits being 1.

The gf2::BitVec::from factory method is overloaded to allow construction from:

A std::bitset where we copy the bits over.
A callable object (a function of some sort) that generates bits on demand when passed an index.

Bit Access

The following methods provide access to individual bit elements in the bit-set.

Function	Description
gf2::BitSet::get	Returns the value of a single bit element as a read-only boolean.
gf2::BitSet::operator[]()	Returns a bool in the const case and a BitRef with read-write access to a bit element in the non-const version.
gf2::BitSet::front	Returns the value of the first element in the bit-set.
gf2::BitSet::back	Returns the value of the last element in the bit-set.
gf2::BitSet::set	Sets a bit to the given boolean value which defaults to true.
gf2::BitSet::flip	Flips the value of the bit element at a given index.
gf2::BitSet::swap	Swaps the values of bit elements at locations i and j.

Note: You can set the DEBUG flag at compile time to enable bounds checks on the index arguments.

The non-const version of gf2::BitSet::operator[]() returns a gf2::BitRef, which is "reference" to an individual bit in the vector. It is automatically converted to a boolean on reads, but it also allows writes, which means you can write natural-looking single-bit assignments:

v[12] = true;

Queries

The following methods let you query the overall state of a bit-set.

Function	Description
gf2::BitSet::is_empty	Returns true if the bit-set is empty
gf2::BitSet::any	Returns true if any bit in the bit-set is set.
gf2::BitSet::all	Returns true if every bit in the bit-set is set.
gf2::BitSet::none	Returns true if no bit in the bit-set is set.
gf2::BitSet::count_ones	Returns the number of set bits in the bit-set.
gf2::BitSet::count_zeros	Returns the number of unset bits in the bit-set.
gf2::BitSet::leading_zeros	Returns the number of leading unset bits in the bit-set.
gf2::BitSet::trailing_zeros	Returns the number of trailing unset bits in the bit-set.

These methods efficiently operate on words at a time, so they are inherently parallel.

Mutators

The following methods let you mutate the entire bit-set in a single call.

Function	Description
gf2::BitVec::set_all	Sets all the bits in the bit-set to the passed value, which defaults to true.
gf2::BitSet::flip_all	Flips the values of all the bits in the bit-set.

The methods operate on words at a time, so are inherently parallel.

Copies & Fills

The following methods let you populate the entire bit-set in a single call.

Function	Description
gf2::BitSet::copy	Makes the bits in this bit-set identical to those from various sources.
gf2::BitSet::random_fill	Fills the bit-set with random 0's and 1's.

Copies

The gf2::BitSet::copy methods support copying bits from:

Another bit-store of the same size but possibly a different underlying word type.
A std::bitset of the same size as the bit-set.
An unsigned integer that has the same number of bits as the bit-set. The integer type need not be the same as the underlying Word used by the bit-set.
A function or callable object that takes a single usize index argument and returns a boolean value for that index.

Note: In each case, the size of the source and destinations must match exactly and that condition is always checked unless the NDEBUG flag is set at compile time. You can always use a gf2::BitSpan to copy a subset of bits if needed.

Random Fills

By default, the random fill method uses a random number generator seeded with system entropy, so the results change from run to run. You can set a specific seed to get reproducible fills.

The default probability that a bit is set is 50%, but you can pass a different probability in the range [0.0, 1.0] if desired.

Spans

The following methods let you create a gf2::BitSpan, which is a non-owning view of some contiguous subset of bits in the bit-set.

Function	Description
gf2::BitSet::span	Returns a gf2::BitSpan encompassing the bits in a half-open range [begin, end).

There are two overloads of the gf2::BitSet::span method — one for const bit-sets and one for non-const bit-sets:

auto span(usize begin, usize end); // <1>

auto span(usize begin, usize end) const; // <2>

Returns a mutable gf2::BitSpan that allows modification of the bits in the specified range.
Returns an immutable gf2::BitSpan that does not allow modification of the bits in the specified range.

In both cases, the begin and end arguments define a half-open range of bits in the vector.

Mutability/immutability of the returned BitSpan is deep. The span's mutability reflects that of the underlying vector, so if the vector is mutable, so is the span, and vice versa.

This is similar to the C++20 std::span class for regular data collection types.

Note: A gf2::BitSpan also satisfies the gf2::BitStore concept, so you can take a span of a span.

Sub-vectors

The following methods create or fill independent bit-vectors with copies of some contiguous subset of the bits in the vector.

Function	Description
gf2::BitSet::sub	Returns a new gf2::BitVec encompassing the bits in a half-open range [begin, end).
gf2::BitSet::split_at	Fills two bit-vectors with the bits in the ranges [0, at) and [at, size()).

The gf2::BitSet::split_at method can optionally take two pre-existing bit-vectors to fill, thereby avoiding unnecessary allocations in some iterative algorithms that repeatedly use this method.

Note: These methods do not alter the underlying vector.

Riffling

We have methods that can interleave (riffle) the bits in a bit-set with zeros.

Function	Description
gf2::BitSet::riffled	Fills a pre-existing bit-vector with the result of riffling this bit-set.
gf2::BitSet::riffled	Returns a new bit-vector that is this bit-set with its bits interleaved with zeros.

If the bit-set looks like \(v_0 v_1 v_2 \ldots v_n\), then the riffling operation produces the vector \(v_0 0 v_1 0 v_2 0 \ldots v_n\) where a zero is interleaved between every bit in the original bit-set (there is no trailing zero at the end).

If you think of a bit-set as representing the coefficients of a polynomial over GF(2), then riffling corresponds to squaring that polynomial. See the documentation for gf2::BitPoly::squared for more information.

Set/Unset Bit Indices

The following methods find the indices of set or unset bits in the vector.

Function	Description
gf2::BitSet::first_set	Returns the index of the first set bit in the bit-set.
gf2::BitSet::last_set	Returns the index of the last set bit in the bit-set.
gf2::BitSet::next_set	Returns the index of the next set bit in the bit-set after the passed index.
gf2::BitSet::previous_set	Returns the index of the previous set bit in the bit-set before the passed index.
gf2::BitSet::first_unset	Returns the index of the first unset bit in the bit-set.
gf2::BitSet::last_unset	Returns the index of the last unset bit in the bit-set.
gf2::BitSet::next_unset	Returns the index of the next unset bit in the bit-set after the passed index.
gf2::BitSet::previous_unset	Returns the index of the previous unset bit in the bit-set before the passed index.

Iterators

The following methods create iterators for traversing the bits or underlying words in the bit-set:

Read-only iteration through the individual bits.
Read-write iteration through the individual bits.
Read-only iteration through the indices of the set bits.
Read-only iteration through the indices of the unset bits.
Read-write iteration through the underlying vector words.

Function	Description
gf2::BitSet::bits	Returns a gf2::BitsIter iterator over the bits in the bit-set.
gf2::BitSet::set_bits	Returns a gf2::SetBitsIter iterator to view the indices of all the set bits.
gf2::BitSet::unset_bits	Returns a gf2::UnsetBitsIter iterator to view the indices of all the unset bits.
gf2::BitSet::store_words	Returns a gf2::WordsIter iterator to view the "words" underlying the bit-set.
gf2::BitSet::to_words	Returns a copy of the "words" underlying the bit-set.

There are two overloads of the gf2::BitSet::bits method — one for const bit-stores and one for non-const bit-stores:

auto bits(); // <1>

auto bits() const; // <2>

Returns a mutable gf2::BitsIter that allows modification of the bits in the bit-set.
Returns an immutable gf2::BitsIter that only allows one to view the bits in the bit-set.

Stringification

The following methods return a string representation for a bit-set. The string can be in the obvious binary format or a more compact hex format.

Function	Description
gf2::BitSet::to_string	Returns a default string representation for a bit-set.
gf2::BitSet::to_pretty_string	Returns a "pretty" string representation for a bit-set.
gf2::BitSet::to_binary_string	Returns a binary string representation for a bit-set.
gf2::BitSet::to_hex_string	Returns a compact hex string representation for a bit-set.

Other Operators and Functions

There are many operators and free functions defined for any gf2::BitStore compatible class, including:

Category	Description
Equality Operator	Operator to compare bit-stores, including bit-sets for content equality.
Bit Shifts	Operators to shift the bits in bit-sets left or right.
Bit-wise Operators	Operators to combine bit-stores using logical operations.
Arithmetic Operators	Operators to add or subtract bit-stores.
Other Functions	Dot products, convolutions, concatenation etc. for bit-sets.