std::bitset 上的位扫描（bsf）？或类似

Question

我正在做一个项目，涉及解决一些 NP 难图问题。特别是贝叶斯网络的三角测量......

不管怎样，我使用 std::bitset 来创建邻接矩阵，这非常好......但我想使用 bsf 指令扫描位集。例如不使用 while 循环。

有人知道这是否可能吗？

Answer 1

看看 gcc 4.0.0 附带的 STL，bitset 方法_Find_first已经_Find_next可以做你想做的事情了。具体来说，他们使用__builtin_ctzl()（此处描述），其中应该使用适当的指令。（我猜这同样适用于旧版本的 gcc。）

令人高兴的是，位集已经做了正确的事情：如果它是适合单个无符号长整型的位集，则为单个指令；如果使用多个长整型，则循环。在循环的情况下，它是一个长度在编译时已知的循环，带有少量指令，因此它可能会被优化器完全展开。也就是说，通过自己推出可能很难击败 bitset。