Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Реверс бит в слове

Автор: l2_mik 22.3.2008, 15:12

Скажем, есть 16-разрядное слово
необходимо поменять в нем биты местами, не изменяя их значения
0-й и 15-й,
1-й и 14-й,
.......
7-й и 8-й
Требования к алгоритму: простота и быстродействие
У кого есть идеи для решения данной задачи!
Жду с нетерпением!

Автор: Optimus 22.3.2008, 16:43

Алгоритм:
Есть переменная slovo(есть 16-разрядное слово), создаём новыю переменную temp,
Начинаем проверять биты с 15-го в slovo, если там единица то увеличиваем temp
на 2 в степень (кол. итерации - 1, для первой итерации 0, для второй 1...)
slovo = temp

Допустим int имеет 2 байта

Код


  int slovo = 12345;
  long i, pow;

  // Выводим slovo в битах
  for (i = 32768; i > 0; i /= 2)
  {
    if ((slovo & i) == 0)
    {
      cout << "0 ";
    }
    else
    {
      cout << "1 ";
    }
  }

  cout << endl << endl;

  int temp = 0;
  for (i = 32768, pow = 1; i > 0; i /= 2, pow *= 2)
  {
    if ((slovo & i) != 0)
    {
      temp += pow;
    }
  }

  slovo = temp;

  // Выводим slovo в битах
  for (i = 32768; i > 0; i /= 2)
  {
    if ((slovo & i) == 0)
    {
      cout << "0 ";
    }
    else
    {
      cout << "1 ";
    }
  }

Автор: Mayk 22.3.2008, 17:38

А что тут думать, используй табличный поиск и всё.
Таблицу хоть питоном хоть bash'ом сгенерируй.

Код


static uint16_t reversed[65536] = {
 0,
 0x80000000,
 0x40000000, ....
}

uint16_t reverse( uint16_t n )
{
    return reversed[n];
}

проще некуда.

Добавлено @ 17:41
Или вначале засвопь полуслова (по 8 бит) в слове, а потом зареверси их хоть той же таблицей:
на вскидку

Код


uint8_t reversed8[256]={0,0x80, 0x40...}

uint16_t reverse(uint16_t n)
{
    union{
        uint16_t i16; 
        uint8_t i8[2]; //подразумеваем что i8[0] | (i8[1] << 8) = i16
    };
    i16 = n;
    return reversed8[i8[1]] | (reversed[i8[0]] << 8);
}

Автор: maxdiver 22.3.2008, 20:47

Уоррен "Алгоритмические трюки"

Код

unsigned rev(unsigned x) {
   x = (x & 0x55555555) <<  1 | (x >>  1) & 0x55555555; 
   x = (x & 0x33333333) <<  2 | (x >>  2) & 0x33333333; 
   x = (x & 0x0F0F0F0F) <<  4 | (x >>  4) & 0x0F0F0F0F; 
   x = (x << 24) | ((x & 0xFF00) << 8) | 
       ((x >> 8) & 0xFF00) | (x >> 24); 
   return x; 
}

(здесь, правда, 32-битное число, но изменить несложно)

Цитата

Bit reversal can be done quite efficiently by interchanging adjacent single bits, then interchanging adjacent 2-bit fields, and so on, as shown below. These five assignment statements can be executed in any order:
x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>  1;
x = (x & 0x33333333) <<  2 | (x & 0xCCCCCCCC) >>  2;
x = (x & 0x0F0F0F0F) <<  4 | (x & 0xF0F0F0F0) >>  4;
x = (x & 0x00FF00FF) <<  8 | (x & 0xFF00FF00) >>  8;
x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;

Автор: Akina 22.3.2008, 21:21

Код


push bx
push cx
mov cx,16
repeat:
rcl ax
rcr bx
loop repeat
mov ax,bx
pop cx
pop bx

Автор: l2_mik 22.3.2008, 23:41

Всем большое спасибо!

Я пока остановлюсь на решении которое предложил maxdiver, т.к. оно наиболее полно отвечат требованиям,
а именно: простота и быстродейстие.

       Optimus - предложенный тобой алгоритм, значительно сложнее,
       Mayk      - твое решение наверное самое быстрое, но занимает много места;
       Akina     - я не силен в Ассемблере может прокоментируешь как работает программа?

С Уважением!

Автор: Akina 23.3.2008, 22:37

Цитата(l2_mik @ 23.3.2008, 00:41

)

может прокоментируешь как работает программа?

Сначала в образах. Представь 2 трубки. В одной - 16 разноцветных шариков. Мы берем из нее сверху по одному шарику и бросаем во вторую трубку. Когда мы проделаем это 16 раз, шарики окажутся во второй трубке, а цвета будут перевернуты вверх ногами.

Именно это делает мой код с битами в регистрах.

Изначально считаем, что слово, подлежащее реверсу, передается в регистре АХ (это в общем достаточно стандартный способ передачи).
Строки 1 и 2 просто прячут в стек содержимое 2 регистров, которые мы будем использовать и попортим (мы же не хотим гадить?)
Строка 3 запихивает в СХ число 16 - это будет наш счеткчик цикла
Строка 4 - это просто метка, понадобится позднее
Строки 5 и 6 как раз делают то, что описано с шариками. Первая команда выталкивает очередной бит из АХ в регистр флага переноса, вторая оттуда засовывает его в регистр ВХ. При этом биты в АХ выталкиваются влево (т.е. в регистр выталкивается старший бит), и соответственно заталкиваются в ВХ справа (со старших). Можно было сделать и со младших - используя пару rcr ax/rcl bx - это непринципиально.
Строка 7 уменьшает содержимое СХ на единичку (мы туда 16 запихали, помнишь?) и сравнивает с нулем. Если ноль НЕ получился - идет возврат на метку, на строку 4. А если ноль - то выполнение продолжается дальше
Строка 8 полученный нам нужный результат из ВХ копирует в АХ - возврат результата в нем тоже стандартен
Строки 9 и 10 просто восстанавливают значения использованных нами регистров

Вот собсно и всё.

Автор: Earnest 24.3.2008, 13:51

Цитата(l2_mik @ 23.3.2008, 00:41

)

Mayk - твое решение наверное самое быстрое, но занимает много места;

Можно обойтись табличкой реверса байтов. Тогда реверс битов в WORD == обмен байтов + замена каждого байта.

Добавлено через 1 минуту и 35 секунд
Сразу не заметила, Mayk уже это написал.
Тогда не пойму, что тут много места занимает - табличка на 256 байтов?

Автор: l2_mik 25.3.2008, 22:19

Большое спасибо Akina,
Все гениальное просто!

Ув. Earnest - этот алгоритм будет крутиться в ПЛК у которого с памятью острый дефицит.

Благодарю всех за советы