scala-library-next icon indicating copy to clipboard operation
scala-library-next copied to clipboard

Add bitwise shift (<< and >>) operations to BitSet collection

Open linasm opened this issue 4 years ago • 0 comments

Proposal

  • add bitwise shift (<< and >>) operations to BitSet collection (both mutable and immutable)
  • add in place bitwise shift (<<= and >>=) operations to mutable BitSet

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.

linasm avatar Nov 21 '20 20:11 linasm