What’s a BitVector ?
BitVector is composed of two words, bit and vector:
A bit refers to a digit in the binary numeral system (base 2). It’s like a switch, it can be either on (1 or true) or off (0 or false), which is a boolean value.
When referring to a vector, you might think of a vector used in linear algebra which has both magnitude and direction, but in this case it defines a structure which is basically a resizable array. With this little background information we can say that a BitVector is meant to pack bit values (or booleans) as close as possible into an array so that no space is wasted.
Most compilers and flash use a larger data type (e.g. an integer) in place of a boolean. This is done because it is more efficient to send a fixed amount of data at a time through the memory and to the processor (e.g. x86 machines can only send data in packs of 32bits). Thus storing a boolean always waists some memory.
We can overcome this limitation by using bitwise operators in flash to modify the bits in a number. Since flash internally represents a number by an 32bit signed integer (double word) we can store up to 31 boolean values (0..31) in it.
How this works
The class uses a native array to store integers in it, whereas each integer will hold the bit values. The important details are found inside the setBit() and getBit() function.
Both functions need the array index for the integer and the position of the bit inside the number. The array index is computed by dividing the bit index by the data size:
arrayIndex = int(bitIndex / dataSize)
For example, if we want to set a bit at index 42 in the BitVector, we get arrayIndex = int(42 / 31) = 1. To determine the bit position we modulo the bit index by the data size, which simply wraps the bit index into the range of the data size.
bitPos = bitIndex % dataSize
Referring to the example above: bitPos = 42 % 31 = 11.
Now the bitwise part:
To set a bit shift a 1 into the bit position giving a 1 at the same position as the bit to write. Assuming the bit position is 4, the result would be:
1 << bit = 1 << 4 = 1*2*2*2*2 = 1* 2^3 = 10000 (binary).
Then logically or (|) it with the integer, which only returns 0 when both operands have a zero at the same position:
1 << bitPos 10000 integer 00110 result | 10110
To get a bit shift up a 1 bit position, which gives a 1 at the same position as the bit to retrieve. Then binary and (&) it with the integer and shift the number back down bit positions to get a one or a zero. The binary & operator returns 1 only if both the operands have a 1 in the same position.
1 << bitPos 10000 integer 10110 result & 10000 result >> bitPos = 1
Finally to clear a bit without affecting all the other bits, the bit to get cleared must be 0, and every other bits need to be 1. So again shift a 1 into the bit position to clear, but this time apply the binary not operator (~) to reverse every bit. Then the binary& operator clears the bit.
1 << bitPos 10000 (1 << bitPos)~ 01111 integer 10110 result & 00110
Why should this be useful ?
If storing thousands of values, the BitVector is more size efficient and thus reduces memory consumption. I admit it’s hard to reach the limit now, but with AS3 we will see much more complex applications. You also get less traffic and therefore a faster response when sending bit packed values over the network.
Setting and getting a bit involves one division (to get the correct array index), one modulo (to get the correct bit position), and finally two bit operations, to modify the bits. So it’s not as fast as an native flash array.
The BitVector class
public function BitVector(size:Number)
The constructor in my implementation takes only one parameter: the total number of bits.
For efficiency’s sake you have to manually resize the BitVector with the resize() function, which automatically expands or truncates the BitVector.
The syntax to get/set a boolean value:
myBitVector.setBit(4, true); // set bit at index 4 trace(myBitVector.getBit(4)); // outputs 1 myBitVector.setBit(4, false); // clear bit at index 4 trace(myBitVector.getBit(4)); // outputs 0
You can also clear or set all bits in one step by using the clearAll() or setAll() function.
Here you can download (right click & save as) my BitVector class.
That’s it !
Have fun, Michael