can java.util.BitSet hold more than MAX_INT no. of bits?

Question

As the BitSet.get() function uses an int as an argument, I was thinking whether I could store more than 2^32 bits in a BitSet, and if so how would I retrieve them?

I am doing a Project Euler problem where I need to generate primes till 10^10. The algorithm I'm currently using to generate primes is the Erathonesus' Sieve, storing the boolean values as bits in a BitSet. Any workaround for this?

Answer 1

You could use a list of bitsets as List<BitSet> and when the end of one bitset has been reached you could move to the next one.

However, I think your approach is probably incorrect. Even if you use a single bit for each number you need 10^10 bits which is about 1 GB memory (8 bits in a byte and 1024^3 bytes in a GB). Most Project Euler problems should be solvable without needing that much memory.

Answer 2

No, it's limited by the int indexing in its interface. So they didn't bother exploiting all its potential, (about 64x downsized) probably because it wasn't feasible to use that much RAM. I worked on a LongBitSet implementation, published it here.

It can take:

//2,147,483,647 For reference, this is Integer.MAX_VALUE
137,438,953,216 LongBitSet max size (bits)
0b1111111_11111111_11111111_11111100_000000L in binary

Had to address corner cases, in the commit history you can see the 1st commit being a copy paste from java.util.BitSet.

See factory method:

    public static LongBitSet getMaxSizeInstance() {
        // Integer.MAX_VALUE - 3 << ADDRESS_BITS_PER_WORD
        return new LongBitSet( 0b1111111_11111111_11111111_11111100_000000L);
    }

Note: -Xmx24G -Xms24G -ea Min GB needed to start JVM with to call getMaxSizeInstance() without java.lang.OutOfMemoryError: Java heap space