Перемещение немного внутри байта с использованием битового поля или побитовых операторов

Question

Есть ли элегантный способ немного двигаться внутри байта (или слова / длинного). Для простоты, давайте используем простой 8-битный байт и всего один бит для перемещения внутри байта.

Учитывая битовое число, основанное на от 0-7 битов от наименьшего сигма к большему количеству сигма (или биты 1-8, если хотите), я бы хотел переместить бит из одной позиции в другую :

7654 3210 <bit position
0101 1010 <some binary value
--x- --y- <move bit from x to y
0111 0100 <new value with x moved to y and intervening bits shifted left

Таким образом, x в битовой позиции 5 перемещается в y в битовой позиции 1, биты 0,6,7 остаются неизменными. Биты 2,3,4 сдвинуты влево, чтобы «освободить место» для бита, перемещенного с 5 на 2. Это всего лишь пример.

Важно, чтобы бит двигался, а не менялся с целью. Существует множество примеров обмена битами, но это довольно тривиально.

В идеале решение будет использовать простые побитовые и побитовые операторы. Предположим, что независимость от языка, простые биты И / ИЛИ / XOR, НЕ, СДВИГ влево / вправо / ВРАЩЕНИЕ или аналогичные инструкции подойдут в любой комбинации, плюс любой другой основной арифметический оператор, например: мод, сложение / вычитание и т. Д. Даже рабочий псевдо- код будет в порядке. Альтернативно, структура битового массива или типа битового поля, вероятно, была бы простой.

В дополнение к фактическому перемещению бита, я хотел бы найти способ:

• Переместить любой бит вверх или вниз.
• Укажите источник / назначение номера бита в любом удобном формате: например: 6> 2 подразумевает сдвиг вниз, 3> 7 сдвиг вверх или стартовый бит +/- смещение: 6-4 или 3 + 4, или взвешенный бит: бит 6 = 64 - бит 3 = 8.
• Возможно расширение от байта до целого без знака, long и т. Д.
• (в идеале, быть расширяемым более одного бита за раз, возможно, смежные биты, если проще)

Быстродействие не является серьезной проблемой, но что-то изящное, скорее всего, достаточно быстро.

Мой собственный основной подход заключается в том, чтобы определить исходные и целевые позиции битов, решить, будет ли сдвиг вверх или вниз, взять сдвинутую копию, замаскировать статические биты и найти исходный бит, объединить статические и сдвинутые биты и каким-то образом установить / очистить целевой бит. Однако, хотя теория кажется хорошей, элегантная реализация мне не подходит.

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

Любая помощь приветствуется. Заранее спасибо.

Answer 1

Во-первых, замечание об исходной проблеме и последующих расширениях, которые вы упомянули:

Операция "перемещение бита", которую вы описываете, на самом деле является вращением непрерывного диапазона битов. В вашем примере вы вращаете биты 1-5 включительно, на один бит влево:

  7   6   5   4   3   2   1   0          7   6   5   4   3   2   1   0
+---+---+---+---+---+---+---+---+      +---+---+---+---+---+---+---+---+
| 0 | 1 | 0<--1<--1<--0<--1 | 0 |  ->  | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
+---+---+-|-+---+---+---+-^-+---+      +---+---+---+---+---+---+---+---+
          |               |
          +---------------+

Если вы считаете, что более общей формой этой операции является «поворот диапазона битов, оставленных на некоторое количество» с тремя параметрами:

1. младший значащий бит для включения в ротацию
2. самый значащий бит для включения в ротацию
3. количество бит для поворота на

затем он становится единым базовым примитивом, который может выполнять все того, что вы хотите сделать:

• очевидно, что вы можете перемещать любой бит (выберите соответствующие наименее / наиболее значимые параметры битов);
• вы можете вращать влево или вправо, потому что если вы вращаете диапазон n битов, то вращение вправо на k битов - то же самое, что вращение влево на n - k бит;
• это тривиально обобщается на любую битовую ширину;
• по определению мы можем вращаться более чем на один бит за раз.

Итак, теперь все, что нужно, это построить этот примитив ...

---

Для начала нам почти наверняка понадобится битовая маска для битов, которые нас интересуют.

Мы можем сформировать маску для битов 0 - n , сдвинув 1 на n + 1 бит влево, а затем вычтя 1. Например, маска для битов 0-5 будет (в двоичном виде):

00111111

... который можно сформировать, взяв 1:

00000001

... сдвиг 5 + 1 = 6 бит влево:

01000000

... и вычитая 1, получим:

00111111

В C это будет (1 << (bit + 1)) - 1. Но здесь есть тонкость, по крайней мере для C (и я прошу прощения за отступление, когда вы пометили это как независимое от языка, но это важно, и, вероятно, есть и похожие проблемы и в других языках): сдвиг на Ширина вашего типа (или больше) приводит к неопределенному поведению. Поэтому, если бы мы пытались создать маску для битов 0-7 для 8-битного типа, вычисление было бы (1 << 8) - 1, что было бы неопределенным. (Это может работать в некоторых системах и некоторых компиляторах, но не может быть переносимым.) Существуют также неопределенные проблемы поведения со знаковыми типами в случае, если вы в конечном итоге перейдете на бит знака.

К счастью, в C мы можем избежать этих проблем, используя тип unsigned и записывая выражение как (1 << bit) + (1 << bit) - 1. Арифметика со значениями без знака n -бит определяется стандартом для уменьшения по модулю 2 ⁿ , и все отдельные операции четко определены, поэтому мы гарантированно получим правильный ответ.

(Конец отступления.)

ОК, теперь у нас есть маска для битов 0 - msb . Мы хотим сделать маску для битов lsb - msb , что мы можем сделать, вычтя маску для битов 0 - ( lsb -1), что (1 << lsb) - 1. например,

  00111111      mask for bits 0-5:  (1 << 5) + (1 << 5) - 1
- 00000001      mask for bits 0-0:  (1 << 1) - 1
  --------                         -------------------------------
  00111110      mask for bits 1-5:  (1 << 5) + (1 << 5) - (1 << 1)

Итак, окончательное выражение для маски:

mask = (1 << msb) + (1 << msb) - (1 << lsb);

Биты, которые должны быть повернуты, могут быть выбраны побитовым И с маской:

to_rotate = value & mask;

... и биты, которые останутся нетронутыми, можно выбрать с помощью И с инвертированной маской:

untouched = value & ~mask;

Само вращение можно легко выполнить из двух частей: во-первых, мы можем получить самые левые биты вращаемой части, просто повернув to_rotate влево и отбросив любые биты, которые выходят за пределы маски:

left = (to_rotate << shift) & mask;

Чтобы получить самые правые биты, поверните to_rotate вправо на ( n - shift ) бит, где n - это количество бит, которые мы вращаем (это n может быть вычислено как msb + 1 - lsb):

right = (to_rotate >> (msb + 1 - lsb - shift)) & mask;

Окончательный результат может быть получен путем объединения всех битов из untouched, left и right:

result = untouched | left | right;

Ваш оригинальный пример будет работать следующим образом (msb равно 5, lsb равно 1 и shift равно 1):

    value = 01011010

    mask  = 00111110   from (1 << 5) + (1 << 5) - (1 << 1)

            01011010   value
          & 00111110   mask
          ----------
to_rotate = 00011010

            01011010   value
          & 11000001   ~mask  (i.e. inverted mask)
          ----------
untouched = 01000000

            00110100   to_rotate << 1
          & 00111110   mask
          ----------
     left = 00110100

            00000001   to_rotate >> 4  (5 + 1 - 1 - 1 = 4)
          & 00111110   mask
          ----------
    right = 00000000

            01000000   untouched
            00110100   left
          | 00000000   right
          ----------
   result = 01110100

Вот другой пример с 16-битным входным значением, msb = 15, lsb = 4 и shift = 4 (который вращает 3 верхние шестнадцатеричные цифры четырехзначного шестнадцатеричного значения):

    value = 0101011001111000   (0x5678)

    mask  = 1111111111110000   from (1 << 15) + (1 << 15) - (1 << 4)

            0101011001111000   value
          & 1111111111110000   mask
          ------------------
to_rotate = 0101011001110000

            0101011001111000   value
          & 0000000000001111   ~mask
          ------------------
untouched = 0000000000001000

            0110011100000000   to_rotate << 4
          & 1111111111110000   mask
          ------------------
     left = 0110011100000000

            0000000001010110   to_rotate >> 8  (15 + 1 - 4 - 4 = 8)
          & 1111111111110000   mask
          ------------------
    right = 0000000001010000

            0000000000001000   untouched
            0110011100000000   left
          | 0000000001010000   right
          ------------------
   result = 0110011101011000   =  0x6758

Answer 2

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

//
// bits.c
//

#include <stdio.h>
#include <stdlib.h>

//
// extract_bit
//
// extract bit at given index and move less significant bits left
//

int extract_bit(int *word, int index)
{
    int result = (*word & (1 << index)) != 0;
    int mask = (1 << index) + (1 << index) - 1;
    *word = ((*word << 1) & mask) | (*word & ~mask);
    return result;
}

//
// insert_bit
//
// insert bit at given index and move less significant bits right
//

void insert_bit(int *word, int index, int val)
{
    int mask1 = (1 << index) + (1 << index) - 1;
    int mask2 = (1 << index) - 1;
    *word = ((*word >> 1) & mask2) | (*word & ~mask1) | (val << index);
}

//
// move_bit
//
// move bit from given src index to given dest index
//

int move_bit(int *word, int src_index, int dest_index)
{
    int val = extract_bit(word, src_index);
    insert_bit(word, dest_index, val);
    return val;
}

int main(int argc, char * argv[])
{
    if (argc > 2)
    {
        int test = 0x55555555;
        int index1 = atoi(argv[1]);
        int index2 = atoi(argv[2]);

        printf("test (before) = %#x\n", test);
        printf("index (src) = %d\n", index1);
        printf("index (dest) = %d\n", index2);

        move_bit(&test, index1, index2);

        printf("test (after) = %#x\n", test);
    }

    return 0;
}

Answer 3

Скорее всего, это не квалифицируется как "элегантный", но вы могли бы втиснуть его в одну строчку, если это ваша вещь? План состоит в том, чтобы разбить число на четыре части (не должно быть сложно с битовыми операциями, верно?), Сделать с ними соответствующие вещи, а затем собрать три части вместе.

              Number: 01x1 10y1
       P1 (before x): 0100 0000
     P2 (just bit x): 00x0 0000
P3 (between x and y): 0001 10y0
        P4 (after y): 0000 0001

Тогда вам нужно набрать [P1] + [P3 shifted up by 1] + [P2 shifted down by 4] + [P4].

                  P1: 0100 0000
P2 shifted down by 3: 0000 00x0
  P3 shifted up by 1: 0011 0y00
                  P4: 0000 0001

                 Sum: 0111 0yx1               

Answer 4

Используете ли вы биты для экономии места? Это действительно нужно?

Возможно, вам лучше использовать класс списка, который позволяет вам удалять и вставлять элементы в список. В вашем случае элементы будут булевы.