c - 寻找算法以在位集中找到 n 个未设置的位

Question

背景: 我正在编写一个分配 4KiB block 的物理内存分配器。它使用一个位集来标记哪些 4KiB 内存块已被使用。我没有可用的标准 C 库。

问题: 我正在寻找一种算法，它会在最小的间隙中找到 n 个连续的未设置位，这样我就可以留下最大的未设置位可用间隙。

例子: 假设一个位集包含以下位:

 0010 0000 0111 0001 1100 0011

如果我想设置 4 位，算法应该返回位号 18。

Answer 1

我认为你可以分 2 次完成:

第 1 关:
扫描数组，注意连续零位的数量，以及这些位的开头。

根据您的示例，扫描将产生:

2 bits, starting at 0
6 bits, starting at 3
3 bits, starting at 12
4 bits, starting at 18

第 2 轮:
扫描第 1 遍的数据，寻找目标值 (4)，或大于目标的最小值。

用 C 编写这两个过程似乎微不足道，这应该是适用于所有情况的通用解决方案。

在您完成这项工作后，我还看到了一些优化，因此在某些情况下您可能根本不需要运行第 2 次传递。