What do we do with bit operations on Integers?

[smarr]

Original issue: smarr/SOMns#218

More recent context/discussion: softdevteam/yksom#43 (comment)

---

I am unhappy with the fact that we have bit operations and cast to 32bit or so on number types.

In the presence of arbitrary length integers, these operations are problematic.
On the one hand, they reveal the internal representation (two-complement).
But perhaps more important, their semantics are problematic with respect to the arbitrary length.
For most algorithms that use bit operations, we want fixed-length bit representations.

Examples for bit vectors, bit sets, can be found for instance in Common Lisp, Java, Scala.

In the context of SOM, there is a tradeoff between introducing a new concept (perhaps BitArray) and simply declaring bit operations special.

At the moment I am wondering whether it would be a good compromise to declare all bit operations special, to restrict them as operating on the range of machine-word-sized two-complement integers only. This avoids introducing an extra concept, but defines the semantics in a way that is useful for the current use cases: benchmarks mostly.

If we introduce a new concepts, some thoughts on a name:

• BitArray this is my current choice, it is an array of bits (fixed size), or do we need a BitVector?
• BitSet as in Java or Scala doesn't make sense to me. It's not a set of bits is it? The Java doc even says it's a vector of bits.
• BitMap, better than BitSet

Tension between BitArray and BitVector:

• << operation semantics, wrapping on current size, or extending? >> and what with?
• we could of course have extending and non-extending (i.e. wrapping) operations
• however, main use case is for porting algorithms that do word-sized operations

[smarr]

More discussion: softdevteam/yksom#43 (comment)