This library (work in progress) defines functions for working with arbitrary sized bit-vectors. The library has two sets of algorithms:

• the "small" representation for sizes [1 .. 64] uses uint64_t
• the "large" representation for sizes [65 .. ) uses an array of uint32_t

All functions in the library have an explicit parameter specifying the widths of the bit-vectors involved.

In addition, we plan to provide a 3rd representation, which is a union of "small" and "large", and the width argument will be used to choose between the alternatives of the union. Thus, the width is used as the "tag" of the corresponding algebraic datatype, but it is not stored directly with the value.

Bit-vectors that do not fit in a representation type exactly, are placed in the most significant bits of the representation, with the least significant unused bits set to 0. Essentially, if x is an N-bit vector (1 <= N <= 64), it will be represented as x * 2^(64-N) (aka x << (64-N)). The same holds for large bit-vectors, where the least significant element of the representation array may contain up to 31 bits of padding. This is useful, because it allows many operations to be performed directly on the normalized representation, without having to change representations.

For the large representation, the least significant bits of the value are in the first array element, and the most significant bits are in the last array element.