There is fairly intuitive way to reason about the storage requirement. Lets start with you've seen no numbers in the range, you have the tuple (99,999,999, 0). That is two 32 bit numbers or 8 bytes of storage. Now lets say you've seen all the numbers in the range, you've got (0, 99,999,999), again 8 bytes of storage, two 32 bit numbers. Since we're describing a linear bit field, the worst case is : (1,1,1,1,1,1,1,1,1, ... 1,0) every odd number and none of the even numbers. So the memory to encode the virtual bit field will be (assuming 32 bit numbers always) 4 bytes * n where 'n' is the number of distinct regions in the bit field. With a perfectly uniform random number generator each number generated has possible outcomes:

1) It splits a region (it causes a string of zeros to have a one in them) (adds 8 bytes)

2) It coalesces a region (it removes the last remaining zero between two regions) (subtracts 8 bytes)

I'm sure there are other solutions, and as was pointed out it doesn't really deal with duplicates. I suspect a multi-value bit field might cover that.