Shifting a Java BitSet

Question

I am using a java.util.BitSet to store a dense vector of bits.

I want to implement an operation that shifts the bits right by 1, analogous to >>> on ints.

Is there a library function that shifts BitSets?

If not, is there a better way than the below?

public static void logicalRightShift(BitSet bs) {   for (int i = 0; (i = bs.nextSetBit(i)) >= 0;) {     // i is the first bit in a run of set bits.      // Set any bit to the left of the run.     if (i != 0) { bs.set(i - 1); }      // Now i is the index of the bit after the end of the run.     i = bs.nextClearBit(i);  // nextClearBit never returns -1.     // Clear the last bit of the run.     bs.clear(i - 1);      // 0000111100000...     //     a   b     // i starts off the loop at a, and ends the loop at b.     // The mutations change the run to     // 0001111000000...   } } 

Answer 1

That should do the trick:

BitSet shifted = bs.get(1, bs.length()); 

It will give you a bitset equal to the orginial one, but without the lower-most bit.

EDIT:

To generalize this to n bits,

BitSet shifted = bs.get(n, Math.max(n, bs.length())); 

Answer 2

An alternative which is probably more efficient would be to work with the underlying long[].

Use bitset.toLongArray() to get the underlying data. Shift those longs accordingly, then create a new BitSet via BitSet.valueOf(long[]) You'll have to be very careful shifting the underlying longs, as you will have to take the low order bit and shift it into the high order bit on the next long in the array.

This should let you use the bit shift operations native on your processor to move 64 bits at a time, as opposed to iterating through each one separately.

EDIT: Based on Louis Wasserman's comment. This is only available in Java 1.7 API. Didn't realize that when I wrote it.