Open
Description
Proposal
- add bitwise shift (
<<
and>>
) operations toBitSet
collection (both mutable and immutable) - add in place bitwise shift (
<<=
and>>=
) operations to mutableBitSet
Motivation
- completeness of bitwise operations supported
- applicable in Dynamic Programming solutions to the Subset Sum / Knapsack types of problems
- feature parity with C++
std::bitset
: https://en.cppreference.com/w/cpp/utility/bitset/operator_ltltgtgt
Implementation
The operations can be efficiently implemented by shifting the 64 bit words of the backing array of the BitSet
.
The implementation (in the form of extension methods) is readily available in scala-collection-contrib
project:
- https://github.com/scala/scala-collection-contrib/blob/master/src/main/scala/scala/collection/decorators/BitSetDecorator.scala
- https://github.com/scala/scala-collection-contrib/blob/master/src/main/scala/scala/collection/decorators/MutableBitSetDecorator.scala
Alternatives
<<
can be emulated with .map(_ + shiftBy)
,
>>
can be emulated with .collect { case b if b >= shiftBy => b - shiftBy }
,
but performance difference is up to two orders of magnitude.