快速高效的位扫描转发和重置

Question

我正在使用正向位扫描找出第一个设置位，然后将该位重置为 0。使用 GCC 和 64 位平台，我想出了这个：

uint64_t b = 0, cb = some random arbitrary data

asm("bsfq %0, %0" : "=r" (b) : "0" (cb));

// b now holds the index of first set bit.

cb &= cb - 1; // Reset the first bit.

我希望有一些指令可以同时执行这两项操作，但经过大量谷歌搜索后，还没有找到更有效的方法来执行此操作。那么，有没有？

Answer 1

没有既重置最低设置位又获取其索引的指令。但是还有其他选择，其中一些可能比 bsf\lea\and.

更快

例如，

bsf rax, rdi
btr rdi, rax

在 Intel 上有帮助（P4 除外），但在 AMD btr r,r 上需要两个周期，因此它与 bsf\lea\and 的延迟相同。

其他例子，

tzcnt rax, rdi
blsr rdi, rdi

在 Intel 上，这并不差（但支持较少）。在 AMD 上这很棒，在 Jaguar 上节省了听起来很疯狂的 5 个周期，因为 bsf 太慢了。

快速高效的位扫描转发和重置

Fast and efficient bit scan forward and reset

gcc

bit-manipulation