BitVector

BitVector

This is an implementation of a bit vector (also know as a bit set or bit array). It is an array that lets you access every individual bit separately. A BitVector provides a more extensive API than the standard java.util.BitSet implementation and better performance in some use cases. Some methods have a different behaviour than the ones from the BitSet class provided by the JDK. Consult the Javadocs for further information.

Creating a BitVector

You can construct a new BitVector either by using one of the provided constructors directly or by using a static utility method. The following code shows how to create a BitVector through a constructor:

//create an empty vector
BitVector vec1 = new BitVector();

//create a vector with an initial capacity of 16 bits
BitVector vec2 = new BitVector(16);

The static methods provide ways to create BitVectors with specific content. The following example creates equal BitVectors:

byte[] bytes = new byte[]{0x0a, 0x0b, 0x0c, 0x0d};
BitVector vec1 = BitVector.valueOf(bytes);
BitVector vec2 = BitVector.fromHexString("0a0b0c0d");
BitVector vec3 = BitVector.valueOf("00001010000010110000110000001101");
int myInt = 168496141;
BitVector vec4 = BitVector.valueOf(myInt);

Wrapping a Byte Array

A BitVector uses a byte array to store the bits internally. For that reason a BitVector can be easily used with arbitrary binary data (which often comes as a byte array) without having to do any copy operations. The following example illustrates this:

byte[] bytes = new byte[]{0x0a, 0x0b, 0x0c, 0x0d};
BitVector vec = BitVector.wrap(bytes);

As shown above, you can simply wrap any byte array into a BitVector. This will not copy the content of the given array and is therefore very efficient. You can then easily access and set every single bit of that array individually:

System.out.println(vec); //00001010000010110000110000001101
System.out.println(vec.get(4)); //print the value of the bit at index 4
vec.set(31, false); //set the bit at index 31 (the rightmost bit)
System.out.println(vec); //00001010000010110000110000001100

As the BitVector uses a reference to the byte array, any externally imposed change to that array will be reflected by the BitVector and vice versa.

Counting Bits

You can count the number of 1s and 0s in a BitVector. The BitVector will cache the computed number internally so that subsequent calls to bitsSet() and bitsUnset() can serve the cached value immediately:

BitVector vec = BitVector.valueOf("00001010011");
System.out.println(vec.bitsSet()); //prints 4
System.out.println(vec.bitsUnset()); //prints 7

NOTE: Some operations will cause the internal cache to be invalidated. See Javadocs for details

More Examples

The following example shows basic operations on a BitVector:

BitVector vec = BitVector.valueOf("10100011");
vec.add(true);
vec.add(false);
vec.set(0, 5, true);
System.out.println(vec); //1111101110

BitVector vec2 = vec.get(5, 10);
System.out.println(vec2); //01110

The following example shows logical operations on a BitVector:

BitVector vec1 = BitVector.valueOf("10100011");
BitVector vec2 = BitVector.valueOf("00011110");
System.out.println(vec1.clone().and(vec2)); //00000010
System.out.println(vec1.clone().or(vec2));  //10111111
System.out.println(vec1.clone().xor(vec2)); //10111101

NOTE: The first BitVector in the above example is cloned so that the original values are not overwritten by the boolean operations.

The following example shows operations that shift and rotate the bits of a BitVector:

BitVector vec = BitVector.valueOf("10100011");
vec.rotateRight(3);
System.out.println(vec); //01110100
vec.shiftLeft(4);
System.out.println(vec); //01000000