c - 在缓冲区中找到第一个未设置的位(优化)

Question

在任意长度的数组中找到第一个未设置位的位偏移的最快/最干净的方法是什么？

假设你的函数的原型(prototype)是这样的 size_t first_unset_bit(char unsigned const *buf, size_t bit_count, size_t start_bit); 并且它可以在同一个上快速连续调用多次缓冲。如果能给出更好的原型(prototype)，请论证。

如果您使用任何程序集，请提供将在 core2 或更高版本上运行的 x86 示例。我会将答案授予提供速度与美观最佳结合的解决方案。

更新0

这是我天真的实现。我不知道它是否真的正确，它还没有在实时系统中使用。

static size_t first_unset_bit(char unsigned const *buf, size_t bit_count, size_t start_bit)
{
    for (; start_bit < bit_count; ++start_bit)
    {
        size_t buf_index = start_bit / CHAR_BIT;
        int bit_index = start_bit % CHAR_BIT;
        if (!((buf[buf_index] >> bit_index) & 1))
            return start_bit;
    }
    return -1;
}

Answer 1

Linux 有一个我认为是名为“find_first_zero_bit”的高度调整的实现。