在一个bitarray中find第一个零

我有一个位图

uint64_t bitmap[10000] 

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

我知道在glibc中有ffsll(unsigned long long)来查找第一个设置位,我假设它使用硬件指令来执行它。

要使用这个函数在我的情况下,首先我需要初始化数组,以设置每一位为1,然后当我做资源分配,我必须线性search数组的第一个非零字。 然后使用ffsll()来查找第一个设置位。

我怎么能做得更快?

更新:我在一个x86-64 CPU。

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

基本上,这是通过将您的数组分成64个字块,并为每个块分配一个64位索引。 如果相应的位集合中的所有位都置位,那么索引字的一个位被置位。 当你改变一个位时,你调整相应的索引字。

然后你可以在顶部建立另一个索引数组来构成一棵树。

它需要一点额外的工作来改变每一点,但额外的工作(和存储)的总量是可以忽略不计的,相比之下,当你需要一个空闲的位时,不必线性搜索你的位。

我不确定你会如何得到比这更快的速度,但我打开被证明是错误的:

 uint64_t bitmap[10000]; unsigned int i; for (i = 0; i < (sizeof(bitmap) / sizeof(*bitmap)) && 0xFFFFFFFFFFFFFFFF == bitmap[i]; ++i); const int bitInWord = ffsll(bitmap[i]); const unsigned int firstZeroBit = bitInWord ? i * sizeof(*bitmap) * CHAR_BIT + bitInWord : 0; 

如果你使用的是32位的CPU,那么你不想这样做。 而是使用32位整数的数组。 数组上的循环会更快。

您也可以将每个值编码为1个字节,然后预先存储该字节中设置的第一个位。 所以当你发现一个不是全部为0xFFFFFFFF的整数时,你可以简单地比较这些字节。 如果第一个字节不是0xFF,那么它在那个字节中,依此类推。

所以如果一个字节不是0xFF,这意味着它是该字节的255个可能的值之一。 每个值都有一个第一位。

查看问题的另一种方法是尽可能把它分成块。 我不知道你的资源是什么,所以我不能说。

还要考虑在之前的扫描中未设置的位。 如果您存储了前一个结果的索引,则可以简单地从下一个搜索的相同索引开始。 将此索引称为pos,并且每次都使用它。

您也可以在每次将某个位设置为零时创建一个“空闲”索引的小数组,因此当“pos”到达数组末尾时,只需从其中一个保存的索引重新开始。

换句话说,你真的不想每次都跑这么长的循环。 这是你的问题,而不是最终的指示。 使用如上所述的索引跟踪,它将会快上百倍。