我有一个位图
uint64_t bitmap[10000]
跟踪系统中分配的资源。
现在的问题是如何有效地找到该位图中的第一个未设置（零）位？
我知道有ffsll(unsigned long long)在 glibc 中查找第一个设置位，我认为这是使用硬件指令来完成的。
要在我的例子中使用这个函数，首先我需要初始化数组以将每个位设置为 1，然后当我进行资源分配时，我必须线性搜索数组中的第一个非零字。然后使用 ffsll() 查找第一个设置位。
我怎样才能做得更快？
更新：
我使用的是 x86-64 cpu。
您可以维护一个tree位图以有效地找到最低位集。在 64 位 CPU 上，只需将树深度设置为 3 即可跟踪 4096 个 64 位元素——这意味着仅使用三个ffsll calls.
基本上，这是通过将数组划分为 64 字块并为每个块分配一个 64 位索引来实现的。当且仅当对应的位集字已设置所有位时，索引字的一位被设置。当您更改位集中的某个位时，您可以调整相应的索引字。
然后，您可以在顶部构建另一个索引数组以形成一棵树。
它需要对每个位进行一些额外的工作，但是与当您需要空闲位时不必线性搜索位集所节省的费用相比，额外工作（和存储）的总量可以忽略不计。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
