I am confused about BitSet. Does a BitSet data structure stores 1s and 0s?
val b = BitSet(0, 2, 3)
means store 1s for bit locations 0, 2 and 3?
If so, what are the max. no. of bits, 32 or 64?
2
votes
2 Answers
6
votes
A BitSet in Scala is implemented as an Array[Long], where each bit signals the presence of a number in the array. Long is 64 bit in Scala (on the JVM). One such Long can store values 0 to 63, the next one after it 64 to 127, on so on. This is possible since we're only talking about positive numbers and don't need to account for the sign.
Given your example:
BitSet(0, 2, 3)
We can store all these numbers inside a single Long, which in binary would be:
1101
Since we're in the range of 0 to 63, this works on a single Long value.
In general, the upper limit, or the biggest value stored inside a BitSet in Scala is Int.MaxValue, meaning 2^31-1 (2147483647). In order to store it, you'd need 2147483647 / 64 "bits" representing the number, which is ~= 33554432 longs. This is why storing large numbers in a bit set can get quite expensive, and it is usually only recommended when you're dealing with numbers in around the hundreds.
As a side note, immutable.BitSet has a special implementation in Scala (of the BitSetLike trait), namely BitSet1 and BitSet2, which are backed by a one and two longs, respectively, avoiding the need to allocate an additional array to wrap them.
0
votes
From the documentation:
Bitsets are sets of non-negative integers which are represented as variable-size arrays of bits packed into 64-bit words. The memory footprint of a bitset is determined by the largest number stored in it.
Given that the API deals with adding and removing Ints, then it seems reasonable to believe the maximum bit that can be set is a max integer, i.e. 2^31-1. Looking at the source for scala.collection.immutable.BitSet, there's also an assert to disallow negative integers (which makes sense according to the above description):
def + (elem: Int): BitSet = {
require(elem >= 0, "bitset element must be >= 0")
