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