为什么Java的BitSet没有shiftLeft和shiftRight函数？

Question

这些函数为什么会缺失呢？

虽然这些函数在BigInteger中确实存在，但由于BigInteger采用了不可变的设计模式，所以这些函数通常速度非常慢。而且BitSet更好一些，因为它是可变的，但我真的很需要long类型的左移（<<）和右移（>>>）函数。对于BitSet，就地移位也很有用，以及循环旋转。

我看到了Shifting a Java BitSet的回答（使用get(off, len)进行位移；但这需要复制）。

别误会我的意思，我知道在哪里报告错误。我只是想知道是否有特定的原因可以省略它们，例如某种设计模式或概念。特别是它们确实包含在BigInteger中。

- Has QUIT--Anony-Mousse

---

因为它是一个“集合”，而不是一个“字符串”。 - bmargulies

@bmargulies：long 也不是字符串。但它有移位运算符。而 String 实际上没有。get(i,j) 的语义基本上与 substring 相同，并且对于 long 也不可用... - Has QUIT--Anony-Mousse

术语“set”表示“无序集合”。BitSet的工作是知道哪些2的幂已经打开，而不是对它们进行洗牌。 - bmargulies

@bmargulies - 尽管它的名字是BitSet，但它实际上被设计为一个向量（由非负整数索引的值集合），而不是一个集合。 - Ted Hopp

@Anony-Mousse: 很难说“为什么”，但我可以想到一个原因：将位移和像在整数/长整型中 "打包" 一样进行优化处理的人通常关注速度和性能。但是，速度和优化基本上与 "创建Java对象" 相反：并不是Java对象的创建特别慢... 但操作 long/int 和位移基本上是最接近底层的操作...（当然这只是一个理论）。 - TacticalCoder

@user988052 我也一直在考虑这个问题。实际上，我现在已经有了自己的类来操作 long[]。但是我怀疑从 long[] 到管理 long[] 的对象的开销是否很大。对于Java而言，long[] 也是一个对象，不是本地对象。因此，一旦你超过了64位的限制，应该不会有太大的区别。 - Has QUIT--Anony-Mousse

Answer 1

从概念上讲，BitSet 通常用于跟踪大量设置，因此集合中的每个位都具有特定的含义。在这种情况下，移位操作几乎没有意义。

显然，您已经找到了BitSet 的另一个有用用途，但它超出了BitSet 可能预见的范围。

- Eli Courtwright

---

引用自文档：BitSet被设想为“需要时增长的位向量”。这比您建议的典型用法要更加通用。其他向量类（如Vector、ArrayList等）没有“移位”操作，但它们确实有“插入”和“删除”操作，这些操作实际上做的是相同的事情。BitSet具有类似的功能是有意义的，但它并没有。 - Ted Hopp

（无序的）set点很好，只是它有些不一致地使用。谢谢。 - Has QUIT--Anony-Mousse

我对BitSet仅用于设置的观点持怀疑态度。如果我要进行设置，我会像20年前的“真正的程序员”一样使用int/long中的位，或者更恰当地说，我会使用枚举和EnumSet。我倾向于将BitSet更多地用作稀疏/紧凑的Set<Integer>。 - user949300

Answer 2

我猜这会让他们的代码变得更加复杂。例如，如果你将所有东西都“左移3位”，你可以有一个额外的字段shift，它是-3（或者可能是3，我只有50%的几率猜对:-)。对于get()和set()方法，如果你简单地通过shift调整bitIndex，代码应该可以工作。例如：

public boolean get(int bitIndex) {
    bitIndex += shift;  // new code!!!
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    checkInvariants();

    int wordIndex = wordIndex(bitIndex);
    return (wordIndex < wordsInUse)
        && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }

然而，对于一些其他操作，比如intersects()和or()，代码会变得非常混乱。目前，or()方法的核心非常简单且快速：

 // Perform logical OR on words in common
   for (int i = 0; i < wordsInCommon; i++)
      words[i] |= set.words[i];

   // Copy any remaining words
   if (wordsInCommon < set.wordsInUse)
     System.arraycopy(set.words, wordsInCommon,
                  words, wordsInCommon,
              wordsInUse - wordsInCommon);

如果两个BitSet都有可能移位，那么这将很快变得混乱。他们可能认为，如果你真的想要移位，应该使用get和copy。

有一件事让我感到惊讶-在get()中，他们没有执行1L << bitIndex&31。显然<<会循环，现在我记得我的远古机器语言，这是有道理的。

- user949300

---

是的，我考虑过那种方法。但我确实需要or和xor能够正常工作。Java实际上有针对BigInteger中的int[]进行移位的代码，他们可以将其复制到BitSet中的long[]中。这并没有什么不同。 - Has QUIT--Anony-Mousse