Интерпретация std :: vector & lt; unsigned int & gt; как битвектор — эффективный алгоритм?
Я хотел бы интерпретировать
std::vector<unsigned int> numbers
как битвектор, то есть MSB numbers[0] 1-й бит, MSB numbers[1] это 33-й бит и так далее. Я хочу найти все последовательности Ones в этом векторе и сохранить соответствующие позиции в структуре данных. (Также сингл Один определяется как последовательность здесь)
Например: у меня есть значения 15 и 112, хранящиеся в числах. Таким образом, биты 29–32 и 58–60 равны единице.
Задача состоит в том, чтобы оптимизировать время выполнения этой функции.
Вот моя идея, как справиться с этим: я думал о работе с двумя за-петли. Первый цикл выполняет итерацию по элементам «numbers» (назовем его element_loop), а второй цикл используется для определения позиций всех единиц в одном элементе (назовем его bit_loop). Я думал об обнаружении «восходящих» и «падающих краев» последовательности для этой цели.
В начале каждого цикла bit_loop маска инициализируется в гекс. значение 0x80000000, С помощью этой маски я проверяю, равен ли 1-й бит единице. Если да, текущая позиция (0) сохраняется. Следуя маске в двоичном представлении1000 … «используется для обнаружения» падающего фронта «в следующем цикле. Если нет, маска сдвигается на один бит вправо»0100 … », чтобы обнаружить« нарастающий фронт »в следующем цикле. (Я забочусь только о паре жирных цифр)
После обнаружения края я сохраняю текущую позицию и соответствующим образом сдвигаю маску на один бит. Поэтому после поз. край (01) Я переключаюсь на нег. обнаружение края (10) и наоборот. Выполняя итерацию по 32-битному номеру, я сохраняю все граничные позиции в каком-то векторе. Этот вектор может быть 2-мерным. массив, где первый столбец является началом одной последовательности, а второй столбец — концом последовательности. Кроме того, мне понадобится особый подход к переходу от одного элемента к другому.
Вот мой общий вопрос: что вы думаете об этом подходе? Есть ли способ справиться с этим более эффективно? Большое спасибо за вашу помощь заранее.
Бен
Решение
Существуют различные побитовые приемы для эффективного сканирования, но если вы используете C ++, вы можете воспользоваться std::bitset или же boost::dynamic_bitset перебирать битовые позиции. Алгоритм, который вы описали, выполняет итерации в обратном направлении для каждого блока, так что вы можете инвертировать свои позиции, используя что-то вроде 32 - (32 - i),
В зависимости от архитектуры каждый бит должен занимать примерно цикл.
Другие решения
Существуют эффективные методы (с постоянным временем) для нахождения первого набора битов в слове, использующие либо специальные инструкции процессора, либо различные хитрые приемы (см., Например, Положение младшего значащего бита, который установлен).
С некоторой осторожностью вы можете работать в обратном направлении и использовать их для сканирования первого, затем выполнить некоторое маскирование и переключение битов и найти следующий ноль и так далее.
это может быть дать вам более быстрый алгоритм, особенно если последовательности в среднем длинные, так что выигрыш при быстром сканировании перевешивает стоимость битовой перестановки.