scala / scala-library-next

backwards-binary-compatible Scala standard library additions
Apache License 2.0
69 stars 17 forks source link

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

Open linasm opened 3 years ago

linasm commented 3 years ago

Proposal

Motivation

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:

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.