在位数组中找到第一个零 [英] Find the first zero in a bitarray

问题描述

我有一个位图

uint64_t bitmap[10000] 

跟踪系统中分配的资源. 现在的问题是，如何有效地找到此位图中的第一个未设置(零)位?

to keep track of the resources allocated in the system. Now the question is how do efficiently I find the first unset(zero) bit in this bitmap?

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

I am aware that there is ffsll(unsigned long long) in glibc for finding the first set bit, which I assume uses hardware instructions to do it.

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

To use this function in my case, first I need to initialize the array to set every bit to 1, then when I do the resource allocation, I have to linearly search the array for the first none zero word. then use ffsll() to find the first set bit.

我如何更快地做到呢?

更新: 我使用的是x86-64 CPU.

Update: I am on a x86-64 cpu.

推荐答案

您可以维护位图的树以有效地找到最低位.在64位CPU上，您只需要具有3的树深即可跟踪4096个64位元素-这意味着仅使用三个ffsll调用.

You can maintain a tree of bitmaps to efficiently find the lowest bit set. On a 64-bit CPU, you only have to have a tree depth of 3 to track 4096 64-bit elements -- that means only using three ffsll calls.

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

Basically, this works by dividing your array into 64-word chunks and assigning one 64-bit index to each chunk. A bit of the index word is set iff the corresponding bitset word has all bits set. When you change a bit in the bitset, you adjust the corresponding index word.

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

You can then build another index array on top to form a tree.

每次更改位都需要一点额外的工作，但是与不需要线性搜索位集而节省的开销相比，额外的工作(和存储)总量可以忽略不计.

It requires a little extra work on every bit change, but the total amount of extra work (and storage) is negligible compared to the savings you get from not having to linearly search your bitset when you need a free bit.

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