有效地找到第 k 个设置位在 bitset 中的位置 [英] Efficiently finding the position of the k'th set bit in a bitset

问题描述

我有一个稀疏的位集，它可能有数百万甚至数十亿位宽.假设 bitset 已经被有效地压缩，并假设我也已经可以有效地查询 bitset 以查看在某个给定范围(即位置和长度)中设置了多少位.

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).

鉴于此，我能否有效地找到第 k 个设置位在 bitset 中的位置，或者有效地给出它不存在的指示?对与编程语言无关的算法的描述将是理想的.假设我不能改变 bitset 实现的任何内部结构......也就是说，我唯一能对 bitset 做的事情就是查询它的总宽度，并询问它在任何给定范围内设置了多少位.

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.

推荐答案

如果你能高效地查询每个范围内设置的位数，你可以对 #set_bits(0,i) 找到该值等于 k 的第一个索引.

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.

需要O(log(n)*f(n))，其中f(n)是#set_bits(0,i) 操作.

这篇关于有效地找到第 k 个设置位在 bitset 中的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！