A Mask provides a dense bitset implementation. This replaces uses of
BitSet. The major difference is that we don't box the Ints.
An explanation of some of the arithmetic you'll see here:
We store the bits in array of words. Each word contains 64 bits and the
words are in order. So, the word containing bit n is n >>> 6 -
we simply drop the lower 6 bits (divide by 64). If n is set, then the bit
n & 0x3FL (the last 6 bits - ie n % 64 if n was an unsigned int), in
word bits(n >>> 6) will be true. We can check this by masking
the word with 1L << (n & 0x3FL) and checking if the result is
non-zero.
Note that we use shift-without-carry (> > >) and intersection
(&) to divide and mod by 64 instead of using / and % because they
do not behave correctly with negative numbers; they carry the sign through
in the result, and we want the absolute value.
An invariant of the underlying bits array is that the highest order word
(ie. bits(bits.length - 1)) is always non-zero (except if bits has 0
length). This sometimes means we must *trim* the array for some operations
that could possibly zero out the highest order word (eg. intersection and
subtraction.
A
Mask
provides a dense bitset implementation. This replaces uses ofBitSet
. The major difference is that we don't box theInt
s.An explanation of some of the arithmetic you'll see here:
We store the bits in array of words. Each word contains 64 bits and the words are in order. So, the word containing bit
n
isn >>> 6
- we simply drop the lower 6 bits (divide by 64). Ifn
is set, then the bitn & 0x3FL
(the last 6 bits - ie n % 64 if n was an unsigned int), in wordbits(n >>> 6)
will betrue
. We can check this by masking the word with1L << (n & 0x3FL)
and checking if the result is non-zero.Note that we use shift-without-carry (
> > >
) and intersection (&
) to divide and mod by 64 instead of using/
and%
because they do not behave correctly with negative numbers; they carry the sign through in the result, and we want the absolute value.An invariant of the underlying
bits
array is that the highest order word (ie.bits(bits.length - 1)
) is always non-zero (except ifbits
has 0 length). This sometimes means we must *trim* the array for some operations that could possibly zero out the highest order word (eg. intersection and subtraction.