std :: bitsetのbitscan（bsf）？または類似

Question

私は、いくつかのNPハードグラフの問題を解決することを伴うプロジェクトを行っています。特にベイジアンネットワークの三角測量...

とにかく、隣接するマトリックスを作成するためにstd :: bitesetを使用していますが、これは非常に素晴らしいです...しかし、BSF命令を使用してビットセットをスキャンしたいと思います。例えば いいえ 時間ループを使用します。

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

Answer 1

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

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

Answer 2

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

MSVCのBSFの場合、使用できます _BitScanForward それ以外の場合は、から何かを使用できます ここ

また、使用を検討することもできます BitMagic 代わりは

Answer 3

おそらくあなたは見ることを検討するかもしれません ビットスカン ビットアレイ操作のためのC ++ライブラリ ugraph ビットエンコードされた無向グラフを管理するため。それは私のコードなので、これについて追加のコメントを追加しません。

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