Scala位集和位移操作

Question

我正在寻找一种用位向量（即这个整数集的特征函数）表示整数集并能够对该集合执行按位操作的方法。

最初我认为 Scala 的 BitSet 是理想的选择。但是，根据文档 1，BitSet 不支持移位操作。经过进一步调查，我发现相关的 Java BitSet 实现也不支持移位操作2。

那么，我只能实现自己的 BitSet 类来支持移位操作了吗？此外，根据 3 中给出的描述，似乎在 Scala 的 BitSet 实现上支持移位操作并不困难，还是我误解了什么？

提前致谢。

- Asiri Rathnayake

Answer 1

当面临需要改进新功能的情况时，通常的方法是使用“Pimp My Library”模式。将BitSet隐式转换为专门执行添加操作的类型：

class ShiftableBitSet(bs: BitSet) {
  def shiftLeft(n: Int): BitSet = ... //impl goes here
}

implicit def bitsetIsShiftable(bs: BitSet) = new ShiftableBitSet(bs)

val sample = BitSet(1,2,3,5,7,9)
val shifted = sample.shiftLeft(2)

将shiftLeft更改为您喜欢的名称，并使用您喜欢的参数。

更新

如果您确定您有一个不可变的BitSet，则可以通过模式匹配轻松访问原始底层数组。这也不算太痛苦，因为不可变的BitSet只有三个可能的具体子类：

import collection.immutable.BitSet
val bitSet = BitSet(1,2,3)
bitSet match {
  case bs: BitSet.BitSet1 => Array(bs.elems)
  case bs: BitSet.BitSetN => bs.elems 
  case _ => error("unusable BitSet")
}

令人困扰的是，对于BitSet2，elems1参数不是可变的，而对于可变的BitSet，elems参数被标记为受保护状态。因此这并不完美，但如果您的集合是非平凡且不可变的，应该可以解决问题。对于简单情况，“正常”访问集合的代价不会太高。

是的，如上所述，这种技术将在包装器内部使用。

- Kevin Wright

---

由于BitSet在内部使用Longs数组来表示位向量，因此访问该数组对于有效实现移位操作至关重要（因为Longs上的移位操作是本地支持的）。然而，在像您建议的包装器实现中，只能使用BitSet接口本身支持的操作来实现所述功能，这在我看来并不那么高效。 - Asiri Rathnayake

谢谢你的更新，听起来（虽然有点hacky）很聪明！我曾考虑使用可变的BitSet来避免不必要的对象创建，但正如你所提到的，这个技巧只适用于不可变的BitSet。顺便说一下，在最后一段中，我认为你想说的是BitSet而不是BitMap，对吗？ - Asiri Rathnayake

毫无疑问，这是一种不太正规的方法，并且在未来 BitSet 实现面前并不稳健。但只要你愿意应对这些问题... - Kevin Wright

Answer 2

你可以使用 map 函数，例如将左移 4 个位置：

import collection.immutable.BitSet
val bitSet = BitSet(1,2,3)
bitSet map (_ + 4)

- Anton Kovsharov

---

那不是（按位）移位操作。您正在将集合中的所有元素加4。 - Asiri Rathnayake