CODEWITHSUNDEEP
javabitsetbit-shift
Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

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

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.

Upvotes: 14

Views: 3534

Answers (2)

user949300
user949300

Reputation: 15729

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.

Upvotes: 1

Eli Courtwright
Eli Courtwright

Reputation: 192921

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.

Upvotes: 9

Related Questions