2002.07.04 ~09 Q3VM bit vectors
A few days ago I implemented a form of generic (compressed) bit vector.
It uses an array of int, and packs 31 bits per int (for reasons of
overflow and sign). Bits are accessed by bitshift, in sizes from 1
to 31 bits (values passed around via int).
The initial purpose for the bit vector was for my mod implementation of
multiple-pierce hitscan (viz. railgun). The original (unmodded) railgun
uses a three-element array of ints, to hold the entity number for each
object pierced (up to three). My rationale was that such limit is
arbitrary, and decided to expand it as much as possible. The most obvious
extension is to expand this array to 1024 elements of int (maximum number
of entities possible). That leads to 4*1024 = 4KB memory use, and most of
it unused since there aren't many weapons that will be infinitely piercing.
Just to keep track of a yes/no state.
This led to wishing for an array of bits. Thus the implementation. At 31
bits to the word, and 1024 bits, this resulted in 34 bytes to record
entities pierced. Major win.
A general bit vector of arbitrary length can also lay the foundation for
bignums, integers of arbitrary size.