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

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

Форум программистов > C/C++: Для новичков > Реализация алгоритма перестановки

Автор: Янус 14.2.2010, 18:34

Господа, окажите пожалуйста помощь в реализации алгоритма перестановки на С++. Задача следующая: есть двоичное число размером в байт, биты этого числа нужно переставить по определенному правилу 0->5; 1->4; 2->8 и т.д.Или дайте ссылочку где об этом можно почитать.

Автор: Albor 14.2.2010, 18:48

В чём проблема? Проверить биты числа? Переставлять их не надо, поскольку есть только 2 значения 0 и 1, нужно только установить/сбросить соответствующий бит.

Цитата(Янус @ 14.2.2010, 18:34

)

правилу 0->5; 1->4; 2->8 и т.д

а и т.д. означает 3->6 (2->7, т.к. бита 8 в байте нет)? smile

Автор: Янус 14.2.2010, 19:12

Нет биты надо именно переставить. Т.е до перестановки 00000001, после перестановки 00100000.

Автор: Albor 14.2.2010, 19:47

Цитата(Янус @ 14.2.2010, 19:12

)

Нет биты надо именно переставить. Т.е до перестановки 00000001, после перестановки 00100000.

Понимаешь, если бы цифер было больше, то можно говорить о перестановке, а так - просто нужно решить задачу. Если присмотреться к алгоритму, то можно увидеть, что 0 и 1 разряды младшего полубайта становятся соответствено 1-м и 0-м в старшем полубайте, то же самое и со старшими разрядами. Значит сначала можно просто поменять в младшем и старшем полубайте разряды местами : 0->1, 2->3, 4->5, 6->7. После сдвинуть младший полубайт влево, а старший вправо на 4 разряда. Объединив половинки получим целое.

Код


#include<iostream.h>

typedef unsigned char byte;

void main()
{
    cout.setf(ios::hex);
    byte b=0x55; // исходное число
    cout<<"before b = "<<(unsigned)b<<endl;
    byte c = (b & 0x55); // выделяем биты по маске 01010101
    byte d = (b & 0xAA);// выделяем биты по маске 10101010
    c<<=1;// сдвигаем влево на 1 разряд
    d>>=1;// сдвигаем вправо на 1 разряд
    b=c|d; // объединяем 
    c=(b & 0x0F);// запоминаем младший полубайт. маска 00001111
    c<<=4; // делаем младший старшим
    b>>=4;// а здесь наоборот
    b|=c; // объединяем результат
    cout<<"after b = "<<(unsigned)b<<endl;

}

Автор: bsa 14.2.2010, 21:06

Янус, в общем случае, тебе нужны побитовые операции: сдвиги, а так же операции "И" и "ИЛИ". Сдвигаешь число на N бит вправо и операцией "И" накладываешь маску 1. В результате получишь значение бита N. Затем результат сдвигаешь влево на M бит и операцией "ИЛИ" накладываешь на результат. Повторяешь для всех бит. Только не забудь обнулить результат перед началом действий.

Автор: Янус 14.2.2010, 21:18

Господа, я дико извеняюсь, но чисел действительно больше, а именно 64.... Вот перестановочный вектор.
{0,8,16,24,32,40,48,56,1,9,17,25,33,41,49,57,2,10,18,26,34,42,50,58,3,11,19,27,35,43,51,59,4,12,20,28,36,44,52,60,5,
13,21,29,37,45,53,61,6,14,22,30,38,46,54,62,7,15,23,31,39,47,55,63}; Т.е значения битов по номерам 0->0; 1->8;2->16 Значение бита с номером 0 остается на месте, а значение бита с номером 1 перебрасывется в бит с номером 8. Извените за некорректно поставленный вопрос.

Автор: Янус 14.2.2010, 21:40

После долгих раздумий у меня получилось следующее...

Код


void perestanS64(int *a,char *b)//int *a это ссылка на перестановочный вектор, char *b это ссылка на bin число записанное в char массив.
{
    char c[65];
    for (int i=0;i<64;i++)
    {
        c[a[i]]=b[i];
        
    }
    for(int i=0;i<64;i++)
    {
        cout << c[i];
    }
}

Эта функция работает, но может, кто подправит ее (сделает более правильной ) или подскажет более оптимальное решение ?

Автор: Albor 14.2.2010, 22:31

Цитата(Янус @ 14.2.2010, 21:18

)

{0,8,16,24,32,40,48,56,1,9,...

Если заполнить матрицу 8х8 последовательными значениями построчно, а потом прочитать её столбцами, ты получишь то же самое. Перестановка битов здесь причём?

Код


#include<iostream.h>

typedef unsigned char byte;

void main()
{
    byte b[64];
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            b[i*8+j]=j*8+i;
        }
    }
    for (i=0;i<64;i++) cout<<(unsigned)b[i]<<", ";
    cout<<endl;

}

Автор: Albor 14.2.2010, 23:09

Цитата(Янус @ 14.2.2010, 21:40

)

После долгих раздумий

И я подумал, может я и не прав.
Янус, можно пример входных и выходных данных?

Автор: Янус 14.2.2010, 23:36

На вход подается 64-битное двоичное число(записано в символьном массиве) , затем в нем меняются местами биты, с использованием вектора перестановки, по описанному выше правилу.

Автор: Albor 15.2.2010, 07:17

Если правило не будет изменяться, то просто выводим исходный массив в нужной последовательности

Код


 for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            cout<<b[j*8+i];
        }
    }

Автор: NewDima 15.2.2010, 10:06

Код


inline int _getbit(char byte, int bit) {
    return (byte & (1 << bit)) >> bit;
}
// 1, 2, byteFrom, bitFrom, byteTo, bitTo
inline void _postoposa(char *vf, char *vt, int Bf, int bf, int Bt, int bt) {
    vt[Bt] = ((_getbit(vf[Bf], bf) << bt) | (vt[Bt] & (~(1 << bt))));
}
inline void _postopos(char *valueFrom, char *valueTo, int bitFrom, int bitTo) {
    _postoposa(valueFrom, valueTo, bitFrom/8, bitFrom%8, bitTo/8, bitTo%8);
}
template<typename T>
inline void movebit(T &valueFrom, T &valueTo, int bitIndex) {
    _postopos(reinterpret_cast<char*>(&valueFrom), reinterpret_cast<char*>(&valueTo), bitIndex, bitIndex%8*8 + bitIndex / 8);
}
    unsigned int v = 0x2;
    unsigned int k = 0;
    movebit(v, k, 1);

Так вроде работает, особо времени тестировать нет. movebit перемещает бит с индексом bi из переменной vf в переменную vt по твоему правилу.
Прбеги по битам циклом

Автор: mes 15.2.2010, 10:41

Цитата(NewDima @ 15.2.2010, 09:06

)

return (byte & (1 << bit)) >> bit;

можно короче :

Код


return (byte>>bit) &1;

да и остальное можно попроще..

Добавлено через 4 минуты и 58 секунд
однако перестановка битов тут все равно излишняя, так как

Цитата(Янус @ 14.2.2010, 22:36

)

На вход подается 64-битное двоичное число(записано в символьном массиве)

т.е операции идут с байтами, а не битами..

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

Код


unsigned vec [64] = {0,8,16,24,32,40,48,56,1,9,17,25,33,41,49,57,2,10,18,26,34,42,50,58,3,11,19,27,35,43,51,59,4,12,20,28,36,44,52,60,5,
    13,21,29,37,45,53,61,6,14,22,30,38,46,54,62,7,15,23,31,39,47,55,63};

uint64 encode (uint64 val)
{
  uint64 res = 0;
  for (size_t i=0; i<64; ++ i)
  {
     res |= ( (val >> i) & 1 ) << vec[i];
  }
  return res;
}

Автор: NewDima 15.2.2010, 11:13

mes, да, я действительно делаю через зад =(

Автор: NewDima 15.2.2010, 11:30

Код


// 1, 2, byteFrom, bitFrom, byteTo, bitTo
inline void _postoposa(char *vf, char *vt, int Bf, int bf, int Bt, int bt) {
    vt[Bt] |= (((vf[Bf] >> bf) & 1) << bt);
}
template<typename T>
//valueTo, valueFrom, bitIndex
inline void movebit(T &vf, T &vt, int bi) {
    _postoposa(reinterpret_cast<char*>(&vf), reinterpret_cast<char*>(&vt), bi/8, bi%8,bi%8+bi/64,bi/8%8);
}

Автор: bsa 15.2.2010, 15:50

Код

std::string encode(const std::string &data) {
   static const int ptrdiff_t enc[] = {
       0,8,16,24,32,40,48,56, 1,9,17,25,33,41,49,57,
       2,10,18,26,34,42,50,58, 3,11,19,27,35,43,51,59,
       4,12,20,28,36,44,52,60, 5,13,21,29,37,45,53,61,
       6,14,22,30,38,46,54,62, 7,15,23,31,39,47,55,63
   };
   std::string result(64, '0');
   for(ptrdiff_t i = 0; i != 64; ++i)
      result[enc[i]] = data[i];
   return result;
}