Может java.util.BitSet содержать больше, чем MAX_INT нет. бит?

Question

Как BitSet.get() функция использует int в качестве аргумента я думал, смогу ли я хранить более 2^32 бит в BitSetи если да, то как бы я их получить?

Я делаю задачу Project Euler, где мне нужно генерировать простые числа до 10^10. Алгоритм, который я в настоящее время использую для генерации простых чисел, - это Erathonesus Sieve, хранящий логические значения в виде битов в BitSet. Любой обходной путь для этого?

Answer 1

Вы можете использовать список битов как List<BitSet> и когда достигнут конец одного набора битов, вы можете перейти к следующему.

Тем не менее, я думаю, что ваш подход, вероятно, неверен. Даже если вы используете один бит для каждого нужного вам числа 10^10 биты о которых 1 GB память (8 бит в байте и 1024^3 байта в ГБ). Большинство задач Project Euler должны быть решаемы без необходимости в большом количестве памяти.

Answer 2

Нет, он ограничен индексацией int в своем интерфейсе. Поэтому они не удосужились использовать весь его потенциал (примерно в 64 раза), вероятно, потому, что было невозможно использовать столько оперативной памяти. я работал над LongBitSetреализация, опубликована здесь.

Это может занять:

      //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

Пришлось решать угловые случаи, в истории коммитов вы можете увидеть, что 1-й коммит является копией вставки из java.util.BitSet.

См. заводской метод:

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

Примечание: -Xmx24G -Xms24G -ea Минимальный ГБ, необходимый для запуска JVM для вызова getMaxSizeInstance()без java.lang.OutOfMemoryError: Java heap space