获取前2个连续1位索引的有效方法

Question

我有这个二进制表示： 0b0110010

对于 gcc，有一个内置函数__builtin_ffs将返回 1 加最低有效 1 位的索引，在我的示例中返回 2。

我正在寻找一种有效的方法来返回 2 个连续 1 位的索引，在我的示例中为 5。语言是 C，我有 64 位数字 * 1024 需要检查。如果解决方案也能涵盖 N 个连续位的情况，那就太好了。

简单的解决方案是通过右移操作迭代位并使用掩码，但效率不高。

Answer 1

由于 gcc 已经内置了，一种方法是将数字右移一位，and与原始数字按位，然后将工作转发到__builtin_ffs，即

__builtin_ffs((x >> 1) & x)

请注意，这使用编译器内部函数，并且根据定义不可移植。

在 x86 等体系结构上，有内置的用于位扫描的汇编指令 ( bsf)。手写的 C 实现的性能不太可能比这更好。