In a game application there is a session id assigned to each player every time they start a new session. Session id's are always unique and there can be billion users of this game. Whenever a user logs-in, get() function is called which basically assigns a bit to the user by setting a bit from a bitarray and when user logs out, set() function is called which resets that bit.
So,it may happen that at some point the bit array looks like below: 101010101000011111
For uint_32 bitarray, 100000 integers needs to be searched for finding out reset bit in worst case if linear search is used. Is it possible to make this search constant time?
For a 32/64 integer and not using bit array this would be pretty much constant using bit operation (x&-x) but for a bit array getting constant time it would be not that easy.
Is there any data structure which I can use for this purpose? I think we can use skip list for this but need some information as to the right approach to insert and delete element from this skip list?