I have a sparse bitset that may be many millions or even billions of bits wide. Assuming that the bitset is already efficiently compressed, and assume that I can also already efficiently query the bitset to see exactly how many bits are set in in some given range (ie, position and length).
Given this, can I efficiently find the position of the k'th set bit in the bitset, or else efficiently give an indication that it doesn't exist? A description of the algorithm that is programming language neutral would be ideal. Assume that I cannot change any of the internals of the bitset implementation... that is, the only things I can do with the bitset are to query its total width, and to ask it how many bits are set in any given range.
If you can efficiently query the number of bits set in every range, you can perform binary search on #set_bits(0,i) to find the first index where this value equals k.
It will take O(log(n)*f(n)), where f(n) is the complexity of #set_bits(0,i) op.