我有一个稀疏的比特集，可能有数百万甚至数十亿比特宽假设位集已经被有效地压缩，并且假设我也可以有效地查询位集，以查看在某个给定范围（即位置和长度）中到底设置了多少位。
鉴于此，我能有效地找到比特集中的第k个集合位的位置，还是有效地给出它不存在的指示？对算法的描述应该是编程语言中立的。假设我不能更改位集实现的任何内部内容…也就是说，我唯一能对位集做的就是查询它的总宽度，并询问它在任何给定范围内设置了多少位。
最佳答案
如果可以有效地查询每个范围中设置的位数，则可以对#set_bits(0,i)执行二进制搜索，以查找该值等于k的第一个索引。
它将采用O(log(n)*f(n))，其中f(n)是#set_bits(0,i) opp的复杂性。
关于algorithm - 有效地找到位集中第k个设置位的位置，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28485961/