作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我有一个位图
uint64_t bitmap[10000]
跟踪系统中分配的资源。现在的问题是如何有效地找到此位图中的第一个未设置(零)位?
我知道 glibc 中有 ffsll(unsigned long long)
用于查找第一个设置位,我假设它使用硬件指令来完成。
要在我的例子中使用这个函数,首先我需要初始化数组以将每一位设置为 1,然后当我进行资源分配时,我必须线性搜索数组以找到第一个非零单词。然后使用 ffsll() 找到第一个设置位。
我怎样才能做得更快?
更新:我在 x86-64 cpu 上。
最佳答案
您可以维护位图的树,以高效地找到最低位集。在 64 位 CPU 上,您只需将树深度设置为 3 即可跟踪 4096 个 64 位元素——这意味着只需使用三个 ffsll
调用。
基本上,这是通过将数组分成 64 字 block 并为每个 block 分配一个 64 位索引来实现的。索引字的一位被设置当且仅当对应的位集字已设置所有位。当您更改位集中的位时,您会调整相应的索引字。
然后您可以在顶部构建另一个索引数组以形成一棵树。
它需要在每个位更改上做一些额外的工作,但与您在需要空闲位时不必线性搜索位集所节省的成本相比,额外工作(和存储)的总量可以忽略不计。
关于c - 在位数组中找到第一个零,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14866848/
我是一名优秀的程序员,十分优秀!