3

I'm doing a project that involves solving some NP-hard graph problems. Specifically triangulation of Bayesian networks...

Anyway, I'm using std::bitset for creating an adjacency matrix and this is very nice... But I would like to scan the bitset using a bsf instruction. E.g. not using a while loop.

Anybody know if this is possible?

4

3 回答 3

4

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

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

于 2010-10-10T05:20:00.410 回答
1

使用std::bitset::to_ulong然后 BSF 它（你需要一个自定义的 contian 来获得比 32 位更大的东西，或者某种方式来获取对每个 32/64 位集的引用。

对于 MSVC 上的 BSF，你可以使用_BitScanForward，否则你可以使用这里的东西

您可能还想考虑使用BitMagic

于 2010-10-08T10:23:20.240 回答
0

您可能会考虑查看用于位数组操作的BITSCAN C++ 库和用于管理位编码无向图的Ugraph 。由于这是我的代码，因此我不会对此添加其他评论。

希望能帮助到你！（如果是这样，我会对任何反馈感兴趣）。

于 2014-07-30T16:36:08.613 回答