битовое сканирование (bsf) на std :: bitset?Или похожие

Question

Я делаю проект, который включает в себя решение некоторых NP-сложных задач с графами.В частности, триангуляция байесовских сетей ...

В любом случае, я использую std :: bitset для создания матрицы смежности, и это очень хорошо ... Но я хотел бы сканировать набор битов, используя инструкцию bsf.Например, не с использованием цикла while.

Кто-нибудь знает, возможно ли это?

Answer 1

Глядя на STL, который поставляется с gcc 4.0.0, методы набора битов _Find_first и _Find_next уже делают то, что вы хотите. В частности, они используют __builtin_ctzl() (описано здесь ), что должно использовать соответствующую инструкцию. (Я предполагаю, что то же самое относится и к более старым версиям gcc.)

И приятно то, что набор битов уже делает правильные вещи: одиночная инструкция, если набор битов вписывается в одну беззнаковую длину; цикл по длинным, если он использует несколько. В случае цикла это цикл, длина которого известна во время компиляции с несколькими инструкциями, поэтому оптимизатор может полностью развернуть его. То есть Вероятно, было бы трудно победить битсет, выполнив свой собственный.

Answer 2

Используйте std::bitset::to_ulong и затем BSF его (хотя вам понадобится пользовательский контианат для чего-то большего, чем 32-битные, или какой-то способ получить ссылки на каждый набор битов 32/64.

для BSF на MSVC вы можете использовать _BitScanForward иначе вы можете использовать что-то из здесь

Возможно, вы также захотите изучить BitMagic вместо

Answer 3

Возможно, вы могли бы рассмотреть возможность поиска библиотеки BITSCAN C ++ для работы с битовыми массивами и Ugraph для управления битовыми кодированными неориентированными графами. Поскольку это мой код, я не буду добавлять дополнительные комментарии к этому.

Надеюсь, это поможет! (Если это так, я был бы заинтересован в любой обратной связи).