чередование битов с маской

Question

Входы:

arbitrary bitset, e.g. bit positions 012345
arbitrary bit mask, e.g. (x=1) xx0x0x

выход:

xx0x1x2345

То есть я хочу, чтобы первый бит набора битов помещался в первые 0 маски. Точно так же второй бит помещается во второй 0 маски.

пример:

mask = 1001001
bits = 1101
result = 1111011

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

edit: Я посмотрел на алгоритмы http://graphics.stanford.edu/~seander/bithacks.html и http://www.hackersdelight.org/HDcode.htm,, но пока не нашел точного метода.

Answer 1

Если я не понял неправильно, вам нужна функция f (bitmask, bitset), например:

f (0b00110101, 0b000ABCDE) = 0bABC11D1E1

, в котором первый аргумент (битовая маска) является относительно фиксированным.

Я думаю, вам придется перебирать битовую маску, и внутри этого цикла вы можете использовать побитовую операцию. Конечно, вы можете заранее скомпилировать битовую маску и сохранить позиции 0, такие как {1, 3, 6, 7, ...}, и сохранить некоторые циклы, зацикливая последовательность вместо этого.

Answer 2

Я думаю, что 012345 предназначен для BITSET, и он использовал 0..5 для обозначения комбинации 0 и 1.

Однако это не похоже на побитовую операцию. Я бы придерживался петли ..

Answer 3

Большинство функций чередования битов или общих агрегирующих битов выполняют цикл, но неочевидным образом.

Даже функция подсчета битов имеет сложность O (log2 (биты в целых числах)).

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

unsigned blah(unsigned bitmask, unsigned bits_to_insert)
{
    unsigned insertion_bitmask= ~bitmask;

    while (insertion_bitmask)
    {
        unsigned bit_position_to_insert= insertion_bitmask & -insertion_bitmask;
        unsigned current_bit= bits_to_insert & 1;
        unsigned bit_to_insert_into_mask= (-current_bit) & bit_position_to_insert;
        bitmask|= bit_to_insert_into_mask;

        bits_to_insert>>= 1;
        insertion_bitmask&= insertion_bitmask - 1;
    }

    return bitmask;
}

Answer 4

Я думаю, что эффект, который вы пытаетесь достичь, (используя данные в качестве примера, но выкладываете информацию несколько иначе):

bitmask = 1001001
bitset  =  11 01
result  = 1111011

Теперь, если мы описываем это как работу справа налево (сначала младший значащий бит), то финальная 1 из набора битов означает, что необходимо установить самый правый 0 из битовой маски. Ноль в битовом наборе означает, что следующий 0 битовой маски не изменился; следующая 1 означает, что третий ноль преобразуется в единицу; и самый значащий 1 означает, что четвертый ноль преобразуется в 1. Так как в наборе битов больше нет единиц, то это последнее изменение. Обратите внимание, что такая формулировка алгоритма позволяет избежать проблем с количеством битов в наборе битов или битовой маске, тогда как интерпретация слева направо приводит к большим проблемам.

Давайте рассмотрим другие примеры:

bitmask = 1001001      1001001      1100011000   0000000101001001
bitset  =  11 00        10 00         110  010     11100 1 00 11
result  = 1111001      1101001      1111011010   0011100111001111


bitmask = 01001101     01001011     11000010     0000000011111111
bitset  = 1 10  1      1 10 1          110 1         1101
result  = 11101111     11101111     11011011     0000110111111111

Если эта интерпретация верна, то значение набора бит варьируется в зависимости от битовой маски. Если битовая маска и набор битов ограничены 8 битами, то для каждого набора битов вы, вероятно, в конечном итоге вычисляете набор из 256 значений, которые могут быть ИЛИ с исходным значением битовой маски для получения результата. С другой стороны, вы можете так же легко вычислить результат, как значение, которое будет OR в основных данных.

Answer 5

вы уверены, что вам не нужен цикл? Если вы знаете количество битов, вы можете пропустить служебную информацию и просто сделать 16 или 32 строки битовых сдвигов, но цикл будет проще. Я не думаю, что есть действительно другой способ сделать это, но вы заставили меня задуматься об этом сейчас