Java BitSet size larger then nbits set in Constructor

Question

I am creating a BitSet with a fixed number of bits. In this case the length of my String holding the binary representation is 508 characters long.

So I create BitSet the following way:

BitSet bs = new BitSet(binary.length());
// binary.length() = 508

But looking at the size of bs I always get a size of 512. I can see that there are always 4 Bits with value of 0 appended at the end.

Maybe there is some misunderstanding of the following documentation:

BitSet(int nbits)

Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1.

Is it that BitSet always enhances its size so that its size is powers of 2 or why is it larger?

Answer 1

The number of bits in the constructor is a sizing hint, not a limit on the number of bits allowed. The size() of a Bitset is effectively its current capacity, though the specification is rather more rubbery than that.

So I can't rely on the size if I get passed another bitset? There may also be some bits appended or it can be longer than "expected" ?

Correct, and yes.

If you want the logical size (i.e. the highest bit index that is set) use the length() method, not the size() method.

If length() gives me the highest bit set, this can't help in every situation. Because "my" highest bit on position 508 can also be 0.

In this case "set" means "set to 1 / true". So if your highest bit (at position 508) is a zero, the length() will be less than 508. I'm not sure if that will help. But if you have a concept of a highest bit position that is defined then you need to represent that position as a separate value.

A Bitset is actually modelled as a potentially infinite array of bits which is default initialized to all zeros. (That's why there is no "flip the entire Bitset" operation. It would use a huge amount of storage.)

Answer 2

According to the documentation, the actual size in memory is implementation dependent, so you can't really know for sure what size() you're going to get. You as a user shouldn't have to worry about it, though, because the length() of the BitSet is always accurate - even if the size in memory is larger, it returns the number of bits actually in use.

Since the BitSet can automatically grow to accomodate any data added to it, I wouldn't be surprised if it uses a growth strategy that's similar to lists, which tend to use increasing powers of two. But as said, that fact is an implementation detail, and it might not be the same everywhere and every time.

Answer 3

That's just a hint for a collection (this applies to all collections I think) so it don't have to resize itself after adding elements. For instance, if you know that your collection will hold 100 elements at maximum, you can set it's size to 100 and no resize will be made which is better for performance.

Answer 4

The BitSet size will be set to the first multiple of 64 that is equal to or greater than the number you use for 'size'. If you specify a 'size' of 508, you will get a BitSet with an actual size of 512, which is the next highest multiple of 64.