BitSet не работает для Integer.MAX_VALUE и Integer.MIN_VALUE

Question

Я попытался использовать BitSet (java), чтобы найти общие числа в двух массивах. (Кажется, очень хорошо работает поиск повторяющихся символов), однако, когда я попробовал использовать угловой регистр, такой как Integer.MAX_VALUE (он не может отображаться в res) и Integer.MIN_VALUE (он показывает IndexOutOfBoundsException ("bitIndex < 0:" + bitIndex)) Я думал, что размер BitSet автоматически расширяется. Кто-нибудь может понять это? Благодарю. BitSet так удобен. :)

public static List<Integer> common(List<Integer> A, List<Integer> B) { 
    List<Integer> res = new ArrayList<Integer>(); 
    BitSet bitSetA = new BitSet(); 
    BitSet bitSetB = new BitSet(); 
    for (Integer x : A) { 
     bitSetA.set(x); 
    } 
    for (Integer x : B) { 
     bitSetB.set(x); 
    } 
    bitSetA.and(bitSetB); 
    for (int i = 0; i < bitSetA.size(); i++) { 
     if (bitSetA.get(i)) { 
      res.add(i); 
     } 
    } 
    return res; 
} 

public static void main(String[] args) { 
    List<Integer> A = new ArrayList<Integer>(); 
    A.add(1);A.add(2);A.add(Integer.MIN_VALUE); 
    List<Integer> B = new ArrayList<Integer>(); 
    B.add(Integer.MIN_VALUE);B.add(4);B.add(4); 
    List<Integer> res = new ArrayList<Integer>(); 
    res = common(A,B); 
    System.out.println(res); 
} 

}

Answer 1

BitSet индексы не должны быть отрицательными; см. третье предложение от the javadoc. Integer.MIN_VALUE отрицательный и, следовательно, не является допустимым индексом.

Integer.MAX_VALUE работает для меня, до тех пор, как:

• имеется достаточно куча свободного места, что это не так, по умолчанию в 32-разрядной JVM, по крайней мере, не в Oracle 32-разрядные виртуальные машины Мне удобно. Небольшой эксперимент находит -Xmx около 400 м за максимальный BitSet. (Я держал пари, что фактическое использование является 256m, но -Xmx является грубым инструментом, который включает в себя несколько куч пространства и некоторые накладные расходы.)

• вы не используете length() или size() (или toString()), которые неисправностью при максимальном размере , Если я петлю наивно (как ваш код) до Integer.MAX_VALUE, он работает, но занимает около минуты; подход nextSetBit, показанный в javadoc, намного быстрее.