位集不适用于Integer.MAX_VALUE和Integer.MIN_VALUE

我尝试使用BitSet(Java)来查找两个数组中的公共数字。(它在查找重复字符方面似乎工作得很好)，然而，当我尝试角点用例时，例如Integer.MAX_VALUE(它不能显示在RES中)和Integer.MIN_VALUE(它显示IndexOutOf边界异常("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);
}

}

---

解决方案

BitSet索引不能为负；请参阅the javadoc的第三句。Integer.MIN_VALUE为负数，因此不是有效索引。

Integer.MAX_VALUE适合我，只要：

• 有足够的堆空间可用，这在32位JVM中不是缺省情况，至少不是我手边的Oracle 32位JVM。一个小实验发现，每最大400米的BitSet就足够了。(我敢打赌实际使用量是256M，但-Xmx是一个粗糙的工具，它包括几个堆空间和一些开销。)

• 您没有使用最大大小出现故障的length()或size()(或toString())。如果我天真地(就像您的代码一样)循环到Integer.MAX_VALUE，那么它可以工作，但大约需要一分钟；在javadoc中显示的nextSetBit方法要快得多。