c++ - std :: bitsetのビットスキャン（bsf）？または類似

Question

私はいくつかのNP困難なグラフの問題を解決することを含むプロジェクトを行っています。具体的には、ベイジアンネットワークの三角測量...

とにかく、私は隣接行列を作成するためにstd :: bitsetを使用していますが、これは非常に便利です...しかし、bsf命令を使用してビットセットをスキャンしたいと思います。たとえば、whileループを使用していません。

これが可能かどうか誰かが知っていますか？

Answer 1

gcc 4.0.0に付属しているSTL、ビットセットメソッド_Find_firstを見て、_Find_nextすでに必要なことを実行します。具体的には、 （ここで__builtin_ctzl()説明する）を使用します。これは、適切な命令を使用する必要があります。（同じことが古いバージョンのgccにも当てはまると思います。）

そして、良い点は、ビットセットがすでに正しいことをしていることです。単一のunsigned long内に収まるビットセットの場合は、単一の命令です。複数使用している場合は、ロングのループ。ループの場合、それはコンパイル時に長さがわかっているループであり、いくつかの命令があるため、オプティマイザーによって完全に展開される可能性があります。つまり、自分でロールしてビットセットを打ち負かすことはおそらく難しいでしょう。

Answer 2

それを使用std::bitset::to_ulongしてからBSFします（ただし、32ビットよりも大きいものにはカスタムコンティアンが必要です。または、32/64ビットの各セットへの参照を取得するための何らかの方法が必要です。

MSVC上のBSFの場合は、他の方法で使用できます。ここ_BitScanForwardから何かを使用できます。

代わりにBitMagicの使用を検討することもできます

Answer 3

おそらく、ビット配列操作用のBITSCAN C ++ライブラリと、ビットエンコードされた無向グラフを管理するためのUgraphを検討することを検討してください。これは私のコードなので、これについてコメントを追加することはしません。

それが役に立てば幸い！（もしそうなら、私はどんなフィードバックにも興味があるでしょう）。