java.util.BitSet -- set() doesn't work as expected

Question

Am I missing something painfully obvious? Or does just nobody in the world actually use java.util.BitSet?

The following test fails:

@Test
public void testBitSet() throws Exception {
    BitSet b = new BitSet();
    b.set(0, true);
    b.set(1, false);
    assertEquals(2, b.length());
}

It's really unclear to me why I don't end up with a BitSet of length 2 and the value 10. I peeked at the source for java.util.BitSet, and on casual inspection it seems to fail to make sufficient distinction between a bit that's been set false and a bit that has never been set to any value...

(Note that explicitly setting the size of the BitSet in the constructor has no effect, e.g.:

BitSet b = new BitSet(2);

Answer 1

You highest bit set (as in "set to 1") is Bit 0. So the length should be 1.

See the JavaDoc for length:

public int length()

Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one. Returns zero if the BitSet contains no set bits.

Maybe you're looking for size although it's possible that might be higher than two if bits are allocated at a certain resolution (say 16 bit boundaries)?

Answer 2

People do use BitSet; however, they use it for something other than what you intend. It's probably best to think of BitSet as a very compact, memory-efficient form of Set<Integer> that has the peculiar property that you can't put negative numbers into it.

It's very common with BitSets to use them in the pattern of

for (int id = set.nextSetBit(0); id >= 0; id = set.nextSetBit(id + 1)) {
  // do stuff to a set index
}

after you do something to fill them up. This is equivalent to iterating over the elements of the Set.

Answer 3

Given that the bitset is backed by a long[], the minimum size is 64 (because 1 long is 64 bits). The size gets incremented by a multiple of 64 and for some reason, they have not maintained the # of bits you intended to represent when you use the constructor that takes an int.

Answer 4

This puzzled me too, not sure of the rationale behind BitSet's current rather unexpected functionality. However since it's not final, we can use some embrace and extend tactics and do the following to get a fixed BitSet with length semantics as expected:

import java.util.BitSet;

/**
 * Variation of BitSet which does NOT interpret the highest bit synonymous with
 * its length.
 *
 * @author [email protected]
 */
public class FixedBitSet extends BitSet{

    int fixedLength;

    public FixedBitSet(int fixedLength){
        super(fixedLength);
        this.fixedLength = fixedLength;
    }

    @Override
    public int length() {
        return fixedLength;
    }
}