Why does Java `BitSet` not have `shiftLeft` and `shiftRight` functions?

Question

Is there any particular reason why these are missing?

They do exist in BigInteger, but due to the immutable design pattern of BigInteger these are usually awfully slow. BitSet is much nicer because it is mutable, but I really miss the shift functions (<< and >>> for longs). For BitSet, an inplace shifting would also be useful, as well as cyclic rotation.

I have seen the reply to Shifting a Java BitSet (using get(off, len) for shifting; however this requires copying).

Don't get me wrong. I know where to report bugs. I'm just wondering if there was a particular reason to omit them, e.g. some design pattern or such a concept. In particular as they are included in BigInteger.

@bmargulies: A `long` is not a string either. Yet, it has shift operators. And a `String` actually has not. And the `get(i,j)` semantics essentially agree with `substring`, and are not available for `long` either... — Has QUIT--Anony-Mousse, Feb 01 '12 at 18:55
The term 'set' means 'an *unordered* collection'. The BitSet has the job of knowing which powers of 2 are turned on, not of shuffling them. — bmargulies, Feb 01 '12 at 18:57
@bmargulies - Despite it's name, a BitSet is actually designed as a vector (a collection of values indexed by non-negative integers), not a set. — Ted Hopp, Feb 01 '12 at 18:59
@Anony-Mousse: it's hard to say "why" but *one* reason I could see would be the following: people shifting bits and doing optimized things like "packing stuff" in integers/longs by packing and shifting bits are typically concerned with *speed* and *performances*. But *speed* and *optimization* are basically the opposite of *"creating Java objects"*: not that a Java object creation is particularly slow... But manipulating long/int and shifting bits is basically as close to the metal as one can get so... (it's just a theory of course) — TacticalCoder, Feb 01 '12 at 20:04
@user988052 I've been considering that, too. In fact, I have my own class for manipulating `long[]` by now. But I doubt that the overhead from a `long[]` to an object managing a `long[]` is this big. A `long[]` also is an object for Java, not a native. So once you get beyond the 64 bits barrier, there shouldn't be much difference. — Has QUIT--Anony-Mousse, Feb 01 '12 at 20:50

score 9 · Accepted Answer · answered Feb 01 '12 at 18:52

9

Conceptually, a BitSet is typically / often used for tracking a lot of settings, such that each bit in the set has a specific meaning. So a shift operation makes little sense in that context.

You've clearly found another useful purpose for a BitSet, but it's outside the scope for which BitSet was probably envisioned.

answered Feb 01 '12 at 18:52

Eli Courtwright

186,300
67
213
256

2

To quote from [the docs](http://docs.oracle.com/javase/6/docs/api/java/util/BitSet.html): BitSet was envisioned as _"a vector of bits that grows as needed." This is a lot more general than the typical use you suggest. Other vector classes (Vector, ArrayList, etc.) don't have a "shift" operation, but they do have "insert" and "delete" operations that effectively do the same thing. It would make sense for BitSet to have similar functionality, but it doesn't. – Ted Hopp Feb 01 '12 at 18:56
The (unordered) `set` point is good, except that it is somewhat inconsequently used. Thank you. – Has QUIT--Anony-Mousse Feb 01 '12 at 19:03
I question the view that BitSet is for settings. If I'm doing settings, I either use bits in an int/long , just like "real programmers" :-) did 20 years ago, or, more properly, I'll use Enums and an EnumSet. I tend to use BitSets more as a sparse/compact `Set`. – user949300 Feb 01 '12 at 20:21

score 1 · Answer 2 · answered Feb 01 '12 at 19:11

My guess is that it would make some of their code way more complicated. For example, if you "left shift by 3" everything, you could have one additional field, shift, which is -3 (or maybe 3, I've only got a 50% chance to get it right :-) . And, for the get() and set() methods, if you simply adjust bitIndex by shift, the code should work. e.g.

public boolean get(int bitIndex) {
    bitIndex += shift;  // new code!!!
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    checkInvariants();

    int wordIndex = wordIndex(bitIndex);
    return (wordIndex < wordsInUse)
        && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }

However, for some of the other operations, like intersects() and or(), the code would start getting really messy. Right now the core of the or() method is very simple and fast:

 // Perform logical OR on words in common
   for (int i = 0; i < wordsInCommon; i++)
      words[i] |= set.words[i];

   // Copy any remaining words
   if (wordsInCommon < set.wordsInUse)
     System.arraycopy(set.words, wordsInCommon,
                  words, wordsInCommon,
              wordsInUse - wordsInCommon);

If both BitSets had possible shifts this would get messy fast. They probably figured that if you really want to shift, you should use get and copy.

One thing that surprised me - in get(), they do not do 1L << bitIndex&31. Apparently << loops around, which, now that I remember my long distant machine language, makes sense.

Yes, I considered doing that. But I really needed `or` and `xor` to work. Java does actually have code to do shifts on `int[]` in `BigInteger`, and they could pretty much copy that over to `BitSet` for `long[]`. It's not really much different. — Has QUIT--Anony-Mousse, Feb 01 '12 at 19:20

Why does Java `BitSet` not have `shiftLeft` and `shiftRight` functions?

2 Answers2