Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Перестановка бит в двоичном числе


Автор: DmbITpo 10.4.2008, 18:17
В общем надо поменять местами первый бит и последний, второй и предпоследний и т.д. 

Вот такая вот задачка. Надо решить. 
Поменять местами эти биты надо в числе двоичном, например таком: 0010001. Результат должен быть 1000100 . 
В принципе она не сложная, если загнать это число в массив и потом менять местами элементы. Но вся соль состоит в том, что нужно _обязательно_ исспользовать побитовые операции (типа &, | или ^). 

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


У меня уже мозги кипят. Ничё умного не могу придумать. 
Может вы поможете ? 

Язык программирования - Си. Но если вы знаете как написать на другом языке - пишите. Мне важен именно алгоритм.... 

Может хоть какие-нить идеи подкините...

Автор: korian 10.4.2008, 18:50
Код

    char str[9] = "11100010";
    char number = strtol(str, NULL, 2);
    char newnumber = 0;
    for (int i = 0; i < 8; ++i)
        newnumber = newnumber | (((number >> i) & 1) << (7-i));
    itoa(newnumber, str, 2);

Автор: vinter 10.4.2008, 18:53
Код

int nSrc = 0xFFEAB564;
int nTmp1 = nSrc & 0xFFFF ;
int nTmp2 = nSrc & 0x0000FFFF;
nTmp1 = nTmp1 >> 16;
nTmp2 = nTmp2 << 16;
int nDst = nTmp1 | nTmp2;


  smile 

Автор: korian 10.4.2008, 18:54
vinter, в вашем коде nDst == (nSrc & 0xFFFF).

Автор: vinter 10.4.2008, 18:55
угу, забыл две инструкции добавить

Автор: korian 10.4.2008, 18:57
все равно не то =)
во первых условие задачи другое, а во вторых нолики не там smile 

Автор: DmbITpo 10.4.2008, 19:10
korian,ого!  это просто гениально! неужели ты просто мыслишь битовыми операциями? =) Спасибо огромное!
Щас попробую набрать этот код! 

Всё работает! огромное спасибо тебе!!
жаль что тут нет снопочки СПАСИБО....

Автор: DmbITpo 10.4.2008, 19:58
хм...при тестировании возникла проблемка. 
Попробуй , например перевернуть строку "011";
Получается какой-то бред....

Автор: korian 10.4.2008, 21:16
мой пример работает тока с 8 битами.
и строка 011 (00000011) преобразовывается в 11000000

Автор: MastEdm 10.4.2008, 21:27
Вот реверс 32-битной последовательности
Код

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;
}

Автор: blinded 10.4.2008, 21:31
Все прсто замечательно. Вот только со знаковыми типами результат сдвига влево implementation defined

Автор: MastEdm 10.4.2008, 21:32
Ну можно схитрить:
Код

int a = -100;
unsigned b = *(unsigned*)(&a);


Правда нужно реально представлять, что из этого получится  smile 

Автор: korian 10.4.2008, 21:41
Цитата(blinded @  10.4.2008,  20:31 Найти цитируемый пост)
Вот только со знаковыми типами результат сдвига влево implementation defined 

имху битовые операции изначально implementation defined. так что про сдвиг смысла нету думать.

Автор: MAKCim 10.4.2008, 21:48
Цитата(blinded @  10.4.2008,  21:31 Найти цитируемый пост)
Все прсто замечательно. Вот только со знаковыми типами результат сдвига влево implementation defined 

это еще почему?

Автор: mes 10.4.2008, 22:02
Цитата(DmbITpo @  10.4.2008,  18:17 Найти цитируемый пост)
В общем надо поменять местами первый бит и последний, второй и предпоследний и т.д. 

Цитата(DmbITpo @  10.4.2008,  18:17 Найти цитируемый пост)
например таком: 0010001. Результат должен быть 1010000 . 

Что то условие с примером не совпадают ))
во вторых не указано  размерность числа, а также ее постоянность
для  8 битного например подходит такая конструкция :

Код

byte func (byte source)
{
return    ((source & 128) ? 1:0)
            |  ((source &  64) ? 2:0)
            |  ((source &  32) ? 4:0)
            |  ((source & 16) ? 8:0)
            |  ((source & 8)  ? 16:0)
            |  ((source & 4)  ? 32:0)
            |  ((source & 2)  ? 64:0)
            |  ((source & 1)  ? 128:0);
};


P.S. где то эта тема уже обсуждалась

Автор: mes 10.4.2008, 22:20
вот альтернативный похожий вариант 
Код

byte func (byte source)
{
return         ((source & 128)>> 7)
            |  ((source & 64) >> 5)
            |  ((source & 32) >> 3)
            |  ((source & 16) >> 1)
            |  ((source & 8)  << 1)
            |  ((source & 4)  << 3)
            |  ((source & 2)  << 5)
            |  ((source & 1)  << 7);
}

Автор: DmbITpo 10.4.2008, 22:30
mes, исправил ошибку. 

Вопросик ко всем ещё один. Мне на самом деле надо вот что : 

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

В связи с этим вопрос - буквы латинского алфавита столько бит имеют? больше 8-и каждая? 

Автор: korian 10.4.2008, 22:40
буква алфавита имеет стока бит, скока ей назначат  smile 
а на компах x86, char - 8 бит, wchar_t - 16 бит.

Автор: mes 10.4.2008, 22:54
Цитата(DmbITpo @  10.4.2008,  22:30 Найти цитируемый пост)
В связи с этим вопрос - буквы латинского алфавита столько бит имеют? больше 8-и каждая? 

английских букв < 32 а значит для хранения достаточно 5 бит

Цитата(korian @  10.4.2008,  22:40 Найти цитируемый пост)
буква алфавита имеет стока бит, скока ей назначат   
а на компах x86, char - 8 бит, wchar_t - 16 бит.

"первые" 7 бит любой кодировки одинаковы и включают в себя спец символы и буквы английского языка..
для остальных ("национальных") символов зависит от кодировки (для не "стандартных" кодировок может быть как угодно)

Цитата(DmbITpo @  10.4.2008,  22:30 Найти цитируемый пост)
 в каждой его букве таким вот образом переставить биты. Следовательно получиться другой символ

в таком случае буква может превратиться в спецсимвол ( например в '\0' - конец строки) - со всеми вытекающими последствиями

Автор: DmbITpo 10.4.2008, 23:13
В общем исспользую я вот такой код: 

Код

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;

}


При кодировке всё нормально работает. Единственное что, например при перевороте числа 1010011, оно выдаёт 110010100000000000000 (за кол-во нулей не ручаюсь, но много лишних). Как бы мне эти хвосты подчистить? 

А то мне кажеться из-за этого при "раскодировке" (т.е. применения того же самого кода для зашифрованной строки), получается не первоначальная строка, а какой-то бред и ужас....

Автор: blinded 10.4.2008, 23:19
Цитата(MAKCim @ 10.4.2008,  21:48)
Цитата(blinded @  10.4.2008,  21:31 Найти цитируемый пост)
Все прсто замечательно. Вот только со знаковыми типами результат сдвига влево implementation defined 

это еще почему?

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

Автор: mes 10.4.2008, 23:23
Цитата(DmbITpo @  10.4.2008,  23:13 Найти цитируемый пост)
 выдаёт 110010100000000000000 

так она с 32 мя битами оперирует..
чтоб обрезать результат до 8 бит  : x >> (32-8) & 255

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)