VPF::Перестановка бит в двоичном числе

DmbITpo

Дата 10.4.2008, 18:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 10.4.2008

Репутация: нет
Всего: нет

В общем надо поменять местами первый бит и последний, второй и предпоследний и т.д.

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

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

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

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

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

Это сообщение отредактировал(а) DmbITpo - 10.4.2008, 22:34

korian

Дата 10.4.2008, 18:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 651
Регистрация: 8.3.2008
Где: Украина, Харьков

Репутация: 3
Всего: 17

Код


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

Это сообщение отредактировал(а) korian - 10.4.2008, 18:52

vinter

Дата 10.4.2008, 18:53 (ссылка)

(нет голосов)

Загрузка ...

Explorer

Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: 13
Всего: 56

Код


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

Это сообщение отредактировал(а) vinter - 10.4.2008, 18:54

--------------------

Мой блог

korian

Дата 10.4.2008, 18:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 651
Регистрация: 8.3.2008
Где: Украина, Харьков

Репутация: 3
Всего: 17

vinter, в вашем коде nDst == (nSrc & 0xFFFF).

Это сообщение отредактировал(а) korian - 10.4.2008, 18:55

vinter

Дата 10.4.2008, 18:55 (ссылка)

(нет голосов)

Загрузка ...

Explorer

Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: 13
Всего: 56

угу, забыл две инструкции добавить

--------------------

Мой блог

korian

Дата 10.4.2008, 18:57 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 651
Регистрация: 8.3.2008
Где: Украина, Харьков

Репутация: 3
Всего: 17

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

DmbITpo

Дата 10.4.2008, 19:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 10.4.2008

Репутация: нет
Всего: нет

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

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

Это сообщение отредактировал(а) DmbITpo - 10.4.2008, 19:18

DmbITpo

Дата 10.4.2008, 19:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 10.4.2008

Репутация: нет
Всего: нет

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

korian

Дата 10.4.2008, 21:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 651
Регистрация: 8.3.2008
Где: Украина, Харьков

Репутация: 3
Всего: 17

мой пример работает тока с 8 битами.
и строка 011 (00000011) преобразовывается в 11000000

MastEdm

Дата 10.4.2008, 21:27 (ссылка)

(нет голосов)

Загрузка ...

Master

Профиль
Группа: Участник
Сообщений: 178
Регистрация: 3.12.2005
Где: Москва, МГИУ

Репутация: 1
Всего: 2

Вот реверс 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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 16.2.2008

Репутация: нет
Всего: нет

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

MastEdm

Дата 10.4.2008, 21:32 (ссылка)

(нет голосов)

Загрузка ...

Master

Профиль
Группа: Участник
Сообщений: 178
Регистрация: 3.12.2005
Где: Москва, МГИУ

Репутация: 1
Всего: 2

Ну можно схитрить:

Код


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

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

Это сообщение отредактировал(а) MastEdm - 10.4.2008, 21:35

korian

Дата 10.4.2008, 21:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 651
Регистрация: 8.3.2008
Где: Украина, Харьков

Репутация: 3
Всего: 17

Цитата(blinded @ 10.4.2008, 20:31

)

Вот только со знаковыми типами результат сдвига влево implementation defined

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

Это сообщение отредактировал(а) korian - 10.4.2008, 21:41

MAKCim

Дата 10.4.2008, 21:48 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 52
Всего: 207

Цитата(blinded @ 10.4.2008, 21:31

)

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

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

--------------------

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

mes

Дата 10.4.2008, 22:02 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(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:08

--------------------

http://opendots.net

mes

Дата 10.4.2008, 22:20 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

вот альтернативный похожий вариант

Код


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

--------------------

http://opendots.net

DmbITpo

Дата 10.4.2008, 22:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 10.4.2008

Репутация: нет
Всего: нет

mes, исправил ошибку.

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

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

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

Это сообщение отредактировал(а) DmbITpo - 10.4.2008, 22:32

korian

Дата 10.4.2008, 22:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 651
Регистрация: 8.3.2008
Где: Украина, Харьков

Репутация: 3
Всего: 17

буква алфавита имеет стока бит, скока ей назначат smile

а на компах x86, char - 8 бит, wchar_t - 16 бит.

mes

Дата 10.4.2008, 22:54 (ссылка)

(голосов:2)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(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' - конец строки) - со всеми вытекающими последствиями

Это сообщение отредактировал(а) mes - 10.4.2008, 22:57

--------------------

http://opendots.net

DmbITpo

Дата 10.4.2008, 23:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 10.4.2008

Репутация: нет
Всего: нет

В общем исспользую я вот такой код:

Код


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 (за кол-во нулей не ручаюсь, но много лишних). Как бы мне эти хвосты подчистить?

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

Это сообщение отредактировал(а) DmbITpo - 10.4.2008, 23:22

blinded

Дата 10.4.2008, 23:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 16.2.2008

Репутация: нет
Всего: нет

Цитата(MAKCim @ 10.4.2008, 21:48)

Цитата(blinded @ 10.4.2008, 21:31

)

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

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

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

mes

Дата 10.4.2008, 23:23 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(DmbITpo @ 10.4.2008, 23:13

)

выдаёт 110010100000000000000

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

--------------------

http://opendots.net

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »