BitSet extension to store multiple bits per position in Java

Uday Sagar Shiramshetty
2 min readMay 26, 2020

--

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 unvisitedas 00, trueas 01 and falseas 10. It allows you to use as less memory as possible.

BitSet:
true - 1
false - 0
MultiBitSet:
unvisited - 00
true - 01
false - 10

A MultiBitSet, depending on no. of bits used for each piece of information, uses more than 1 bit.

BitSet vs MultiBitSet

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.

MultiBitSet.java

There it is, a way to store information using more than 1 bit per position.

--

--