00:00

Help Us Improve

We're sorry this tutorial wasn't helpful. Please tell us what we can do better.

BitSet Class in Java – Compact Sets of Bits

java.util.BitSet is a growable vector of bits, where each bit is indexed by a non-negative integer and is either true (set) or false (clear). It stores 64 flags per long, making it far more compact than a boolean[] (one byte per flag) or a Set<Integer>, and it supports fast bulk logical operations such as AND, OR and XOR.

This tutorial covers the core methods, the difference between cardinality, length and size, set operations, iterating over set bits, and a classic use case: the Sieve of Eratosthenes.

1. Setting, Reading and Iterating Bits

BitSetBasics.java 
import java.util.BitSet;

public class BitSetBasics {
    public static void main(String[] args) {
        BitSet bits = new BitSet();          // all bits start as false; grows as needed
        bits.set(1);
        bits.set(4);
        bits.set(6, 9);                      // sets 6, 7, 8 (end exclusive)
        System.out.println("bits          : " + bits);
        System.out.println("get(4), get(5): " + bits.get(4) + ", " + bits.get(5));
        System.out.println("cardinality() : " + bits.cardinality() + " (number of set bits)");
        System.out.println("length()      : " + bits.length() + " (highest set bit + 1)");
        System.out.println("size()        : " + bits.size() + " (bits of storage)");

        bits.clear(7);
        bits.flip(0);
        System.out.println("after clear(7), flip(0): " + bits);
        System.out.println("nextSetBit(2) : " + bits.nextSetBit(2));
        System.out.println("nextClearBit(0): " + bits.nextClearBit(0));
        System.out.print("iterate set bits:");
        for (int i = bits.nextSetBit(0); i >= 0; i = bits.nextSetBit(i + 1)) System.out.print(" " + i);
        System.out.println();
        System.out.println("stream sum    : " + bits.stream().sum());
    }
}
Output
bits          : {1, 4, 6, 7, 8}
get(4), get(5): true, false
cardinality() : 5 (number of set bits)
length()      : 9 (highest set bit + 1)
size()        : 64 (bits of storage)
after clear(7), flip(0): {0, 1, 4, 6, 8}
nextSetBit(2) : 4
nextClearBit(0): 2
iterate set bits: 0 1 4 6 8
stream sum    : 19
MethodPurpose
set(i), set(from, to), set(i, boolean)Set bits to true (or a given value)
get(i), get(from, to)Read a bit, or a range as a new BitSet
clear(i), clear()Set bits to false
flip(i)Toggle a bit
cardinality()Number of set bits
length()Index of the highest set bit + 1 (the "logical" size)
size()Bits of storage currently allocated (multiple of 64)
nextSetBit(i), nextClearBit(i), previousSetBit(i)Navigate efficiently
isEmpty(), stream()Any bit set; stream of set indexes

Ranges use an inclusive start and exclusive end, like substring. Negative indexes throw IndexOutOfBoundsException.

2. Logical Operations

Bitwise operations work on all bits at once, making set algebra very fast. They modify the BitSet they are called on, so clone it first if you need to keep the original:

BitSetOperations.java 
import java.util.BitSet;

public class BitSetOperations {
    static BitSet of(int... indexes) {
        BitSet b = new BitSet();
        for (int i : indexes) b.set(i);
        return b;
    }

    public static void main(String[] args) {
        // Days of the month on which two employees are available
        BitSet asha = of(1, 2, 5, 8, 9, 15);
        BitSet ravi = of(2, 3, 8, 15, 20);

        BitSet both = (BitSet) asha.clone();  both.and(ravi);       // intersection
        BitSet either = (BitSet) asha.clone(); either.or(ravi);     // union
        BitSet onlyOne = (BitSet) asha.clone(); onlyOne.xor(ravi);  // symmetric difference
        BitSet ashaOnly = (BitSet) asha.clone(); ashaOnly.andNot(ravi);

        System.out.println("Asha        : " + asha);
        System.out.println("Ravi        : " + ravi);
        System.out.println("and (both)  : " + both);
        System.out.println("or (either) : " + either);
        System.out.println("xor         : " + onlyOne);
        System.out.println("andNot      : " + ashaOnly);
        System.out.println("intersects  : " + asha.intersects(ravi));
    }
}
Output
Asha        : {1, 2, 5, 8, 9, 15}
Ravi        : {2, 3, 8, 15, 20}
and (both)  : {2, 8, 15}
or (either) : {1, 2, 3, 5, 8, 9, 15, 20}
xor         : {1, 3, 5, 9, 20}
andNot      : {1, 5, 9}
intersects  : true
MethodSet operation
and(other)Intersection
or(other)Union
xor(other)Symmetric difference
andNot(other)Difference
intersects(other)Do they share any set bit?

3. Use Case: Sieve of Eratosthenes

SieveOfEratosthenes.java 
import java.util.BitSet;

public class SieveOfEratosthenes {
    public static void main(String[] args) {
        int n = 50;
        BitSet composite = new BitSet(n + 1);          // 1 bit per number instead of 1 byte (boolean[])
        for (int p = 2; (long) p * p <= n; p++) {
            if (!composite.get(p)) {
                for (int m = p * p; m <= n; m += p) composite.set(m);
            }
        }
        StringBuilder primes = new StringBuilder();
        for (int i = composite.nextClearBit(2); i <= n; i = composite.nextClearBit(i + 1)) primes.append(i).append(' ');
        System.out.println("Primes up to " + n + ": " + primes.toString().trim());

        BitSet flags = BitSet.valueOf(new long[] {0b1011L});   // from a long bit mask
        System.out.println("valueOf(0b1011) = " + flags + ", toLongArray()[0] = " + flags.toLongArray()[0]);
    }
}
Output
Primes up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
valueOf(0b1011) = {0, 1, 3}, toLongArray()[0] = 11

BitSet.valueOf and toLongArray/toByteArray convert between a BitSet and raw bit masks, which is useful for storage and network protocols.

4. When to Use BitSet

  • Large sets of flags indexed by integers: visited nodes, available seats, feature flags, permissions.
  • Fast set operations on dense integer sets.
  • Memory-sensitive algorithms such as sieves and Bloom filters.

For sets of enum constants, use EnumSet, which is backed by a bit vector and type-safe. For sparse sets with huge indexes (such as a few IDs around one billion), a HashSet<Integer> may use less memory. BitSet is not thread-safe; synchronize externally if it is shared.

5. Summary

  • BitSet is a growable, compact vector of bits indexed by non-negative integers.
  • Use set, get, clear and flip; iterate with nextSetBit or stream().
  • cardinality counts set bits, length is highest set bit + 1, size is allocated storage.
  • and, or, xor and andNot perform fast in-place set operations.

Related Tutorials