1

What is the most efficient data structure to handle (i.e. perform all bitwise operations on) bitmasks that are of a known size but larger than 64bits?

byte[]? BigInteger? Something else entirely?

Needs to be Java 7 compatible and should be fast (or at least as fast as can reasonably be expected, given their size) for things like 

if(bitmask & 7 != 0){...}

and

bitmask1 |= bitmask2

and so on.

User1291
  • 7,664
  • 8
  • 51
  • 108
  • BigInteger can certainly do all of those things. But, a BigInteger instance is immutable, so any operation on it will produce a new BigInteger object. You may need to try it to determine whether the performance is acceptable. – VGR Oct 06 '17 at 13:38

1 Answers1

3

You can't do it directly because maximum size for a primitive number which can be used as a bitmask is actually 64 bit for a long value. What you can do is to split the bitmask into 2 or more ints or longs and then manage it by hand.

int[] mask = new int[4];
final int MAX_SHIFT = 32;

void set(int b) {
  mask[b / MAX_SHIFT] |= 1 << (b % MAX_SHIFT);
}

boolean isSet(int b) {
  return (mask[b / MAX_SHIFT] & (1 << (b % MAX_SHIFT))) != 0;
}

Or you use a BitSet

BitSet bitSet = new BitSet(101);
bitSet.set(100);
Dinh
  • 759
  • 5
  • 16
  • Yeah, BitSet is fast enough, and has some nice operations. Though not _shifting_ bits. – Joop Eggen Oct 06 '17 at 12:50
  • @JoopEggen for the right-shift, at least, there's a solution to that. https://stackoverflow.com/questions/9008150/shifting-a-java-bitset (they call it left shift, but a left shift goes the other direction, for me). For left shifts, I don't immediately see a solution but to extend ``BitSet`` and add a method that would increment the stored values by a given amount. Do you? – User1291 Oct 06 '17 at 13:13
  • @User1291 seems a subrange of the original bitset but not reindexed. A part of the shifting at least (clearing to the left or right) if you maintain a start index offset. – Joop Eggen Oct 06 '17 at 13:24