BitSet extension to store multiple bits per position in Java
In this post, I want to talk about how to store information that needs more than one bit per position. BitSet in Java allows us to store information using 1 bit per position and the bit can be either zero or one. But sometimes, we want to use more than 1 bit per position. For ex: when we want to store 3 states like unvisited
, true
or false
for each position, a single BitSet cannot help. You need at least 2 bits per position to represent 3 states. After BitSet, the next compact data structure is byte array. But with a byte array, we would be using 8 bits for each piece of information instead of 2 or more bits that we actually need. With MultiBitSet, you can use 2 bits to represent unvisited
as 00
, true
as 01
and false
as 10
. It allows you to use as less memory as possible.
BitSet:
true - 1
false - 0MultiBitSet:
unvisited - 00
true - 01
false - 10
A MultiBitSet, depending on no. of bits used for each piece of information, uses more than 1 bit.
MultiBitSet can support different no. of states per position, you can use 2 bits to store up to 4 states, 3 bits to store up to 8 states, 4 to store up to 16 states, etc. Below is the code that shows how to put or get data from MultiBitSet.
There it is, a way to store information using more than 1 bit per position.