Skip to content
Tutorials Center
My learning

Topics

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.

Java
BitSet seen = new BitSet();
seen.set(3);
seen.set(10, 15);          // bits 10..14
boolean has = seen.get(12);   // true

Try it

Java Basic operations

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.

Java Set operations and a sieve

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

Java
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 throws IndexOutOfBoundsException. The upper bound is effectively Integer.MAX_VALUE.
  • get() never throws for large indexes; bits past the end read as false. 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, and cardinality() is the number of ones.
  • Operations mutate. a.or(b) changes a. 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 nextSetBit loop skips empty words, so it is fast for sparse sets. Avoid a for (i = 0; i < size(); i++) loop that calls get(i).
  • Dense, small-range ints: BitSet beats HashSet<Integer> in memory and speed. For sparse or huge ranges, a Set is better.
  • equals() and hashCode() compare the set bits, ignoring allocated size.
  • Printing shows the indexes of set bits in braces.