GF2::Vector

Overview

A GF2::Vector represents a vector over GF(2) (a.k.a. \(\mathbb{F}_2\)) the simplest Galois field that has just two elements usually denoted 0 & 1, or as booleans—true & false, or as bits—set & unset. Arithmetic over GF(2) is defined mod 2 which has the effect that addition/subtraction becomes the XOR operation while multiplication/division becomes AND.

The class is something of a hybrid between a std::vector and a std::bitset along with some extra mathematical features to facilitate linear algebra.

We often refer to an object of the type GF2::Vector as a bit-vector.

A bit-vector is dynamically sized at runtime and can be resized as needs dictate. A std::bitset on the other hand, has a fixed size determined at compile time that can never be changed. Boost does have a boost::dynamic_bitset`class that, as its name suggests, allows for a bitset to be sized at runtime. However, it isn’t aimed at algebraic operations.

By default, a bit-vector prints in vector-order. For example, a bit-vector of size 4 will print as v₀v₁v₂v₃ with the elements in increasing order where the least significant element, v₀, is printed first on the left. A std::bitset on the other hand, prints in bit-order. The equivalent std::bitset prints as b₃b₂b₁b₀ with the least significant bit b₀ printed last on the right.

To be fair, for many applications printing in bit-order makes perfect sense. If a size 4 bit-vector or bitset is initialized with the hex number 0x1, the bit-vector prints as 1000. The bitset prints the same value as 0001 which may be more natural in many settings. For this reason, GF2::Vector also supports conversions to a string in bit-order though it is not the default. It isn’t the default because our main aim here is linear algebra. Bit-order is not at all natural for matrices over GF(2). It is too confusing to print a matrix in anything but the natural order with the (0,0) element at the top left and proceeding from there.

The elements of a GF2::Vector are packed in an array of some unsigned integer type as defined by the class template parameter Block. The default Block is an unsigned 64-bit word. Most of the methods defined in the GF2::Vector class operate on whole blocks at a time so are very efficient.

Declaration

The GF2::Vector class is defined in the header <GF2/Vector.h> as follows:

namespace GF2 {
    template<
        std::unsigned_integral Block = uint64_t,
        Allocator = std::allocator<Block>
    > class Vector;
}

The two template parameters add some visual clutter but they both have reasonable defaults so the clutter completely disappears in most uses.

For example your code might have a simple line like:

    ...
    GF2::Vector v(32);
    ...

This creates a vector with 32 elements which by default are all set to 0. The 32 elements are packed into a singly 64-bit word so in this example there is some spare capacity.

Template Parameters

std::unsigned_integral
Block = uint64_t

The individual vector elements/bits are packed into blocks of type Block which defaults to an unsigned 64-bit word.

Allocator =
std::allocator<Block>

The default Allocator should be just fine for most purposes, but you can use your own custom type to handle all memory allocations/de-allocations for blocks.

The default std::unsigned_integral used for a Block is 64-bits as that is the native size for many modern CPU’s. Of course if you are using lots of smaller bit-vectors and have concerns about space being conserved you might use a different Block. Perhaps if the bit-vectors all fit in 8 bits you might have code along the lines

    using Vector = GF2::Vector<uint8_t>;
    Vector v = ...

You should use just one Block type throughout your code. In theory, there is no reason that one couldn’t intermingle operations between say a GF2::Vector<uint32_t> and a GF2::Vector<uint64_t> but doing so efficiently greatly increases code complexity and the library doesn’t support this.

Class Types

Type	Definition
`reference`	Proxy class representing a reference to an individual vector element (a single bit).

Type

Definition

reference

Proxy class representing a reference to an individual vector element (a single bit).

Class Constants

npos

A public static constant of type size_type used to indicate search failures etc.

Methods

Construction
`constructors`	Create a bit-vector in various ways.
`ones` `zeros` `checker_board`	Factory methods to construct bit-vectors with all the bits set to 1 or 0 or in a checker board pattern 1010101… or 0101010…
`random`	Factory method to construct a bit-vector with a random fill.
`from`	Factory method to construct a bit-vector whose elements match the bits of some unsigned integer type.
Element Access
`element` `operator[]` `operator()` `test`	Access a specific bit.
`all` `any` `none`	Checks if all, any, or none of the bit-vector elements are set.
`count` `count1` `count0` `parity`	The number of set or unset elements (`parity` is just `count % 2`)
`sub`	Extracts a vector as a distinct copy of some of the elements of this one. Note that views into a bit-vector are not supported.
`blocks`	Access the underlying block store: `std::vector<Block>`
`allocator`	Read-only access to the underlying `Allocator` for the block store.
Iteration
`first` `last` `next` `prev`	Returns the index of the first, last, next, or previous set element.
`if_set_call` `reverse_if_set_call`	Iterates over the elements and calls a function for each set index.
`set_indices` `unset_indices`	Returns the index location of the set or unset bits in the bit-vector.
Capacity
`size` `empty`	The number of elements in the bit-vector.
`capacity` `unused`	Information about the capacity of the bit-vector—how many bits can it contain before needing a memory allocation.
`reserve`	Reserves storage. Does not change the `size`.
`shrink_to_fit`	Tries to reduce memory usage by freeing unused memory
Modifiers
`clear`	Clears all the elements from the bit-vector so `size()` becomes 0.
`push` `pop`	Removes the last element from the bit-vector or pushes a new on the end.
`append`	Adds elements/bits from various sources to the end of the bit-vector.
`resize`	Resizes the bit-vector, padding out any added values with zeros.
`swap_elements`	Swaps the values of two elements in the bit-vector.
`swap`	Swaps the contents of the bit-vector with another.
`replace`	Methods to replace some of the contents of the bit-vector with other values.
`set` `reset` `flip`	Sets, resets, or flips various ranges of elements in the bit-vector.
`set_if` `flip_if`	Sets or flips the values in a bit-vector based on the return value from a function of the element index.
`operator&=` `operator^=` `operator\|=` `operator+=` `operator-=` `operator*=` `operator~`	Element-by-element logical operations in-place between this bit-vector and another of equal size. Note that in GF(2) addition and subtraction are the same as XOR, while multiplication is the same as AND.
`operator<<=` `operator>>=` `operator<<` . `operator>>`	Left and right shifts of the bit-vector elements.
Conversions
`to_string` . `to_bit_order` `to_hex`	Returns various string representations of the bit-vector.
Debugging
`description`	A method to write some descriptive data about the bit-vector to a stream.
`GF2_DEBUG` `GF2_NDEBUG` `gf2_debug_assert` `gf2_assert` `gf2_always_assert`	The first two are optional compile time flags that control the degree of safety checking that is performed in the library. In particular, builds that set the `GF2_DEBUG` flag at compile time will get all indices bounds checked at runtime as well as other checks on sizes etc.

Construction

constructors

Create a bit-vector in various ways.

ones
zeros
checker_board

Factory methods to construct bit-vectors with all the bits set to 1 or 0 or in a checker board pattern 1010101… or 0101010…

random

Factory method to construct a bit-vector with a random fill.

from

Factory method to construct a bit-vector whose elements match the bits of some unsigned integer type.

Element Access

element
operator[]
operator()
test

Access a specific bit.

all
any
none

Checks if all, any, or none of the bit-vector elements are set.

count
count1
count0
parity

The number of set or unset elements (parity is just count % 2)

sub

Extracts a vector as a distinct copy of some of the elements of this one.
Note that views into a bit-vector are not supported.

blocks

Access the underlying block store: std::vector<Block>

allocator

Read-only access to the underlying Allocator for the block store.

Iteration

first
last
next
prev

Returns the index of the first, last, next, or previous set element.

if_set_call
reverse_if_set_call

Iterates over the elements and calls a function for each set index.

set_indices
unset_indices

Returns the index location of the set or unset bits in the bit-vector.

Capacity

size
empty

The number of elements in the bit-vector.

capacity
unused

Information about the capacity of the bit-vector—how many bits can it contain before needing a memory allocation.

reserve

Reserves storage. Does not change the size.

shrink_to_fit

Tries to reduce memory usage by freeing unused memory

Modifiers

clear

Clears all the elements from the bit-vector so size() becomes 0.

push
pop

Removes the last element from the bit-vector or pushes a new on the end.

append

Adds elements/bits from various sources to the end of the bit-vector.

resize

Resizes the bit-vector, padding out any added values with zeros.

swap_elements

Swaps the values of two elements in the bit-vector.

swap

Swaps the contents of the bit-vector with another.

replace

Methods to replace some of the contents of the bit-vector with other values.

set
reset
flip

Sets, resets, or flips various ranges of elements in the bit-vector.

set_if
flip_if

Sets or flips the values in a bit-vector based on the return value from a function of the element index.

operator&=
operator^=
operator|=
operator+=
operator-=
operator*=
operator~

Element-by-element logical operations in-place between this bit-vector and another of equal size. Note that in GF(2) addition and subtraction are the same as XOR, while multiplication is the same as AND.

operator<<=
operator>>=
operator<< .
operator>>

Left and right shifts of the bit-vector elements.

Conversions

to_string .
to_bit_order
to_hex

Returns various string representations of the bit-vector.

Debugging

description

A method to write some descriptive data about the bit-vector to a stream.

GF2_DEBUG
GF2_NDEBUG
gf2_debug_assert gf2_assert gf2_always_assert

The first two are optional compile time flags that control the degree of safety checking that is performed in the library.

In particular, builds that set the GF2_DEBUG flag at compile time will get all indices bounds checked at runtime as well as other checks on sizes etc.

Non-member Functions

copy

These functions have the general form GF2::copy(src, dst) where the src argument(s) is a source of bits and the dst argument(s) is a destination for those bits.

One sub-family of these copy functions takes a bit-vector as the source and uses its bits to overwrite an unsigned word, a collection of unsigned words or a std::bitset.

There is another sub-family that takes an unsigned word, a collection of unsigned words, or a std::bitset as the source of bits and uses those to overwrite a destination bit-vector.

operator&
operator|
operator^
operator+
operator-
operator*

Element-by-element logical operations between two equal sized bit-vectors. Note that in GF(2) addition and subtraction are the same as XOR, while multiplication is the same as AND.

diff

Logical DIFF for two equal sized bit-vectors.

join

Joins two bit-vectors to create new one.

dot

Returns the dot product of two equal sized bit-vectors.

convolution

Returns the convolution of two bit-vectors.

polynomial_sum

Evaluates a polynomial over GF(2).

operator<<
operator>>

Performs stream input and output for bit-vectors.