查找位数组中的第一个零

Question

我有位图

uint64_t bitmap[10000] 

跟踪系统中分配的资源。现在的问题是如何有效地找到此位图中的第一个未设置（零）位？

我知道ffsll(unsigned long long)glibc 中有用于查找第一个设置位，我假设它使用硬件指令来完成。

要在我的情况下使用此函数，首先我需要初始化数组以将每一位设置为 1，然后当我进行资源分配时，我必须线性搜索数组以查找第一个非零字。然后使用 ffsll() 找到第一个设置位。

我怎样才能做得更快？

更新：我在 x86-64 cpu 上。

Answer 1

您可以维护位图树以有效地找到最低位集。在 64 位 CPU 上，您只需将树深度设为 3 即可跟踪 4096 个 64 位元素——这意味着只需使用三个ffsll调用。

基本上，这是通过将数组划分为 64 字块并为每个块分配一个 64 位索引来实现的。如果相应的位集字已设置所有位，则设置索引字的一位。当您更改 bitset 中的某个位时，您将调整相应的索引字。

然后，您可以在顶部构建另一个索引数组以形成一棵树。

它需要对每个位更改进行一些额外的工作，但是与在需要免费位时不必线性搜索位集所获得的节省相比，额外工作（和存储）的总量可以忽略不计。