A classe java.util.BitSet

A classe java.util.BitSet é muito útil para alguns problemas que exigem você saber se um determinado elemento está presente ou não com rapidez e eficiência de memória.
Em vez de usar um byte ou 4 bytes para cada elemento booleano (como você poderia esperar em um boolean[] ou então em um ArrayList), BitSet usa apenas um bit.
Infelizmente, java.util.BitSet não implementa java.util.Set nem java.util.List. Mas ela tem métodos bem interessantes, como cardinality (que conta quantos elementos "true" existem no conjunto, mas de maneira muito eficiente), nextSetBit e nextClearBit (que procuram qual é o próximo elemento "true" ou "false" respectivamente. Em algumas versões da JVM, esses métodos também são implementados com instruções especiais do processador.
Vou dar um exemplo de uso dessa classe, implementando o Crivo de Eratóstenes (para achar os números primos). Para simplificar, não vou efetuar a otimização de indicar no crivo apenas os números ímpares.

import java.util.*;
class Sieve {
    private BitSet bs;
    public void findPrimes (int n) {
        bs = new BitSet (n+1);
        int sq = (int) Math.sqrt (n);
        // Ao final desta rotina, todos os bits marcados serão primos, e os
        // bits desmarcados serão números compostos.
        bs.set (0, n - 1, true); // marcando todos os bits como primos...
        // Agora vamos achar o primeiro bit primo, e desmarcar todos os bits
        // que são múltiplos dele. Vamos começar por 3
        int x = 2;
        while (x <= sq) {
            for (int i = x + x; i <= n; i += x) {
                bs.clear (i);
            }
            // Devemos achar o próximo bit setado que seja maior que x
            x = bs.nextSetBit (x + 1);
        }
    }
    public boolean isPrime (int n) {
        return bs.get (n);
    }
    public int nextPrime (int n) {
        return bs.nextSetBit (n + 1); // -1 se não houver um próximo
    }
    public long sumPrimes () {
        int n = 1;
        long sum = 0;
        while ((n = bs.nextSetBit (n + 1)) > 0) {
            sum += n;
        }
        return sum;
    }
    public static void main(String[] args) {
        Sieve s = new Sieve();
        s.findPrimes (10);
        System.out.println (s.sumPrimes());
        s.findPrimes (100);
        System.out.println (s.sumPrimes());
        s.findPrimes (2000000);
        System.out.println (s.sumPrimes());
        long n = 600851475147L; // =  3 * 7^2 * 11 * 163 * 2279657
        int sqrtN = (int) Math.sqrt (n);
       
        int factor = 2;
        int nFactors = 0;
        while (n > 1) {
            int exponent = 0;
            while (n % factor == 0) {
                exponent++;
                n /= factor;
            }
            if (exponent != 0) {
                System.out.printf ("%d^%d . ", factor, exponent);
                nFactors++;
            }
            factor = s.nextPrime (factor);
            if (factor == -1) {
                if (n != 1)
                    System.out.printf ("%d^%d . ", n, 1);
                break;
            }
        }

        System.out.println ();
        System.out.println (nFactors);
    }
}