java - BitSet 不适用于 Integer.MAX_VALUE 和 Integer.MIN_VALUE

Question

我尝试使用 BitSet(java) 查找两个数组中的公共(public)数字。 (它似乎在查找重复字符方面效果很好)，但是，当我尝试诸如 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 位 JVM 中不是这样。一个小实验发现每个最大 BitSet 大约 400m 的 -Xmx 就足够了。 (我敢打赌实际使用量是 256m，但是 -Xmx 是一个粗糙的工具，包括几个堆空间和一些开销。)

• 您不使用 length() 或 size() (或 toString())，它们在最大时会发生故障尺寸。如果我天真地循环(就像您的代码那样)直到 Integer.MAX_VALUE 它可以工作，但需要大约一分钟； javadoc 中显示的 nextSetBit 方法要快得多。