How to shift bits to left and right in BitSet JAVA?

Question

I have a bitset with 100000 number of bits. I want to shift it to the right and to the left as efficiently as possible. I guess there is no function in BitSet class to shift bits, so I tried converting them into long array using toLongArray() but as expected it gives overflow.

A temporary solution which I found was to convert bitset into BigInteger and then shift the BigInteger and then convert BigInteger back to bitset, but that is very slow.

So my questions are:

Is there any better way to shift a bitset (by shifting I mean both left and right shift)
When I convert a bitset with number of bits greater than 64, into long array, I get negatives in the array. Why is there a function toLongArray() in the first place when BitSet can only represent bits of 1 number. Please correct me if I am wrong.

Following is the code to using BigInteger.

public static BitSet toBitSet(BigInteger val) {
  if(val.signum() < 0)
  throw new IllegalArgumentException("Negative value: " + val);
  return BitSet.valueOf(reverse(val.toByteArray()));
}
static byte[] reverse(byte[] bytes) {
  for(int i = 0; i < bytes.length/2; i++) {
    byte temp = bytes[i];
    bytes[i] = bytes[bytes.length-i-1];
    bytes[bytes.length-i-1] = temp;
  }
  return bytes;
}
public static BigInteger toBigInteger(BitSet val) {
  return new BigInteger(1, reverse(val.toByteArray()));
}
public static BitSet shiftLeft(BitSet bits, int n) {
  BigInteger temp= toBigInteger(bits);
  temp= temp.shiftLeft(n);
  return toBitSet(temp);
}

PS: All answers that I found were for number of bits <= 64

If you need it as efficient as possible you may use a List<Boolean> instead, e.g. a LinkedList<Boolean> should be the most efficient data structure for shifting as you can do the shift operations by inserting/removing elements in O(1). — Robert
@Robert yes, but I also want to perform operations like and, or, xor. Bitset has inbulit support for them, that's why I chose it. — Ojasv singh
Why do you think getting negative long values is a problem? If you use all 64 bits of a long negative values are possible, you just have to use the long on bit level, don't try to interpret it as value. BTW: Looking at the implementation of BitSet you can see that internally it uses long[] for storing the bits. Hence by calling toLongArray() you just get a copy of the internal representation. — Robert
@Robert. It was a problem because I thought that only a single value should be returned. But as you said, internal implementation uses long[] then I guess it makes sense to get an array filled with -ve values in case of overflow. — Ojasv singh

harold harold · Accepted Answer · 2020-10-11T13:13:08

When I convert a bitset with number of bits greater than 64, into long array, I get negatives in the array.

Negative elements are perfectly fine, that's just a consequence of using all 64 bits of a long, thereby including the sign bit. That doesn't matter as long as you anticipate it. Basically, it only looks strange when printing it with a signed interpretation, otherwise it's not a bad thing.

so I tried converting them into long array using toLongArray() but as expected it gives overflow.

That is a reasonable implementation strategy though, so let's fix it. I guess you shifted each element individually without handling the "carry". What needs to happen for a left shift, is that the top bit(s) of an element is put into the bottom bit(s) of the next element. For a right shift it's the opposite of that. For example, for n up to 63, (not tested)

static BitSet shiftRight(BitSet bits, int n) {
    long[] raw = bits.toLongArray();
    long carry = 0;
    for (int i = raw.length - 1; i >= 0; i--) {
        long newcarry = raw[i] << -n;
        raw[i] = (raw[i] >>> n) | carry;
        carry = newcarry;
    }
    return BitSet.valueOf(raw);
}

If n can be 64 or larger, there is an extra complication of moving whole elements to different positions.

Shifting left has the additional complication that the resulting set may be larger (not with more set bits, but physically larger, requiring a longer array) than the input.

How to shift bits to left and right in BitSet JAVA?

1 Answers