scala-library-next
scala-library-next copied to clipboard
Add bitwise shift (<< and >>) operations to BitSet collection
Proposal
- add bitwise shift (
<<and>>) operations toBitSetcollection (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.