Java Reference ยท Collections
The BitSet class
Reference for java.util.BitSet: compact boolean vectors, set operations with and/or/xor, nextSetBit() iteration and a prime sieve example.
BitSet is a growable vector of bits. Each index from 0 upward is either set (true) or clear (false), and all the bits live packed in a long[], so a million flags take about 125 KB instead of the megabyte a boolean[] needs (and far more than a List<Boolean> or Set<Integer>).
It also supports bulk logical operations between two bit sets (and, or, xor, andNot), which run a machine word at a time. That makes it a good fit for flags, membership of small non-negative integers, sieves, and sets of IDs.
BitSet seen = new BitSet(); seen.set(3); seen.set(10, 15); // bits 10..14 boolean has = seen.get(12); // true
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Syntax
public class BitSet implements Cloneable, java.io.Serializable
| Constructor | Description |
|---|---|
BitSet() |
Empty set with room for 64 bits; grows as needed. |
BitSet(int nbits) |
Initial capacity of at least nbits bits. Throws NegativeArraySizeException if negative. |
| Method | Description |
|---|---|
set(i), set(i, bool), set(from, to) |
Set one bit, assign one bit, or set a range (end exclusive). |
clear(i), clear(from, to), clear() |
Clear a bit, a range, or all bits. |
get(i) |
Value of a bit; false beyond the end. |
flip(i), flip(from, to) |
Toggle bits. |
and, or, xor, andNot |
In-place logical operations with another BitSet. |
intersects(other) |
true if any bit is set in both. |
cardinality() |
Number of set bits. |
length() / size() |
Index of highest set bit plus one / bits of allocated storage. |
nextSetBit(i), nextClearBit(i) |
Next index at or after i, or -1 (nextSetBit). |
previousSetBit(i), previousClearBit(i) |
Search backward. |
stream() |
IntStream of set indexes (Java 8). |
toByteArray(), toLongArray(), valueOf(...) |
Convert to and from arrays. |
Usage notes
- Indexes must be
>= 0. A negative index throwsIndexOutOfBoundsException. The upper bound is effectivelyInteger.MAX_VALUE. get()never throws for large indexes; bits past the end read asfalse.set()grows the storage automatically.size()is not the count.size()is allocated capacity (a multiple of 64),length()is highest set bit plus one, andcardinality()is the number of ones.- Operations mutate.
a.or(b)changesa. Clone first to keep the original, as the example does. - Not thread-safe. Synchronize externally or use
AtomicIntegerArray/ConcurrentHashMap.newKeySet()for concurrent flags. - Iterating: the
nextSetBitloop skips empty words, so it is fast for sparse sets. Avoid afor (i = 0; i < size(); i++)loop that callsget(i). - Dense, small-range ints:
BitSetbeatsHashSet<Integer>in memory and speed. For sparse or huge ranges, aSetis better. equals()andhashCode()compare the set bits, ignoring allocated size.- Printing shows the indexes of set bits in braces.