A sparse bitset is a large collection of boolean
values where many of the values are off (or false
). For maintaining these sparsely populated sets, the BitSet
class can be very inefficient. Because the majority of the bits will be off, space will be occupied to store nothing. For working with these sparse bitsets, you can create an alternate representation, backed instead by a hashtable, or HashMap
. Only those positions where a value is set are then stored in the mapping.
To create a sparse bitset, subclass BitSet
and override the necessary methods (everything).
The skeleton code should help you get started, so you can focus on the set-oriented routines.
The following UML diagram shows you the BitSet
operations:

For more information on the BitSet
class, see BitSet class.
Skeleton Code
Task 1:
Either start with the skeleton code or create a SparseBitSet
class. The skeleton provides a no-argument constructor only. Because the bitmap will be sparse, you shouldn't provide a constructor that will preallocate any space, as BitMap
does. Besides a constructor, the skeleton defines the clear()
, clone()
, equals()
, get()
, hashCode()
, set()
, size()
, and toSting()
method.
In the skeleton, the getBitSet()
method returns the internal Set
used to store the bits. You should use this method as you complete the other methods in the subclass. The actual HashSet
used to store the bit values is created for you in the constructor.
Help for task 1:
Shift click to save the file to your working directory.
Task 2:
Working alphabetically, the first method to complete is the and(BitSet set)
method. This method performs a logical AND of the two bit sets. Only those bits in both sets are in the resulting set. Complete the and()
method to combine the internal Set
with that of the argument.
Help for task 2:
The retainAll()
method of Set()
retains only
the elements in this set that are contained in the other set.
Task 3:
The next method to complete is the andNot(BitSet set)
method. Instead of keeping bits present in both, the andNot()
operation will remove bits from the current set that are also in the set passed as an argument. This is sometimes called a logical NAND operation.
Help for task 3:
The removeAll()
method of Set()
removes the elements in this set that are contained in the other set.
Task 4:
Because the clear()
, clone()
, equals()
, get()
, and hashCode()
methods are defined in the skeleton code, the next method to complete is the length()
method. The length()
method returns the logical size of the BitSet
, which is defined to be the position of the highest set bit, plus one. Thus, if bit 127 was set, the length would be 128 as the bit counting starts at zero.
Help for task 4:
The max()
method of Collections()
reports the highest value in a collection. Make sure you check for an empty set, as an empty set reports zero, not one.
Task 5:
The last easy method to complete is the or(BitSet set)
method. This method performs a logical OR operation of the two bit sets. Every bit set of either set is in the resulting set.
Help for task 5:
The addAll()
method of Set()
combines
the elements of two sets.
Task 6:
With the set()
, size()
, and toString()
methods already defined for you, you're left to complete the xor(BitSet set)
method. This method performs a logical exclusive or (XOR) operation. Only those bits on in one of the sets will be on in the resulting set.
Unlike the other operations, the solution is not just a single method call of Set
.
Help for task 6:
You need to find out what elements are in each set that are not in the other set without altering the original sets. Once you have these two sets, combine them to create the resulting set.
Task 7:
Compile your program and run the Tester
program to see what happens. The Tester
program creates a couple of sets and performs all the operations.
Help for task 7:
Check your output to make sure the various set operations are correct.