有效地找到位集中第 k 个设置位的位置
Efficiently finding the position of the k'th set bit in a bitset
我有一个稀疏位集，可能有数百万甚至数十亿位宽。假设 bitset 已经被有效压缩，并且假设我也已经可以有效地查询 bitset 以查看在某个给定范围（即位置和长度）中设置了多少位。
鉴于此，我能否有效地找到位集中第 k 个设置位的位置，或者有效地指示它不存在？对编程语言中立的算法的描述将是理想的。假设我无法更改 bitset 实现的任何内部结构......也就是说，我可以对 bitset 做的唯一事情就是查询它的总宽度，并询问它在任何给定范围内设置了多少位。
如果可以高效查询每个范围内设置的位数，则可以对#set_bits(0,i)进行二分查找，找到该值等于k的第一个索引。
需要 O(log(n)*f(n))，其中 f(n) 是 #set_bits(0,i) 操作的复杂度。
我有一个稀疏位集，可能有数百万甚至数十亿位宽。假设 bitset 已经被有效压缩，并且假设我也已经可以有效地查询 bitset 以查看在某个给定范围（即位置和长度）中设置了多少位。
鉴于此，我能否有效地找到位集中第 k 个设置位的位置，或者有效地指示它不存在？对编程语言中立的算法的描述将是理想的。假设我无法更改 bitset 实现的任何内部结构......也就是说，我可以对 bitset 做的唯一事情就是查询它的总宽度，并询问它在任何给定范围内设置了多少位。
如果可以高效查询每个范围内设置的位数，则可以对#set_bits(0,i)进行二分查找，找到该值等于k的第一个索引。
需要 O(log(n)*f(n))，其中 f(n) 是 #set_bits(0,i) 操作的复杂度。