c++ - std::bitset 上的位扫描(bsf)？或类似

Question

我正在做一个涉及解决一些 NP-hard 图问题的项目。特别是贝叶斯网络的三角剖分...

无论如何，我正在使用 std::bitset 创建邻接矩阵，这非常好……但我想使用 bsf 指令扫描位集。例如。 不使用 while 循环。

有人知道这是否可行吗？

Answer 1

查看 gcc 4.0.0 附带的 STL，位集方法 _Find_first 和 _Find_next 已经完成了您想要的操作。具体来说，他们使用 __builtin_ctzl()(描述 here )，它应该使用适当的指令。 (我猜这同样适用于旧版本的 gcc。)

好消息是 bitset 已经做了正确的事情:如果它是适合单个 unsigned long 的 bitset，则为单个指令；如果它使用多个，则在多头上循环。在循环的情况下，它是一个循环，其长度在编译时是已知的，带有少量指令，因此它可能会被优化器完全展开。 IE。自己动手可能很难击败 bitset。