bit_vector

An implementation of arbitrarily large Bit Vectors in Ruby using C + inline assembler for speed

This builds heavily on a much earlier Gem 'bitset' authored by 'MoonWolf' on RAA.

Notes on Bit Vector Lengths

Many bit vector operations are only defined if the lengths of the vectors are the same. By considering a bit vector to possess any number of high-order zeros most operations can be made to work with differently sized operands. When creating this library a couple of different approaches to this were considered:

• Return a result the size of the first operand,
• Return the smallest result set (not necessarily normalized),
• Return a normalized result (the length being the position of the high order bit).

Like the original implementor I chose to use the middle strategy.

Bit Vectors in String Format

The string format of a bit vector represents the bit positions from least significant to most significant with the characters '0,-,f,F,N' representing an un-set bit and all other characters interpreted as a set bit.

from_bytes and to_bytes

These are methods to serialize and de-serialize a bit vector in a platform dependent way. They use US-ASCII encoded strings consisting of 8-bit bytes that represents the bit vector. It is not the binary representation as a string of 0's and 1's used by new and to_s methods.

Operators and Methods

Statements that use binary operators of the form r = a op b are computed by the Ruby call a.op(b)

Most operators are obvious, here's some that aren't

minus

This is defined elementwise as: r = a and not b

bytesize

This returns the length in bytes required to store this bitvec

New

Called with:

• a FixNum to create an empty vector of specified length
• a String to create a vector from the string in the format described above.