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

  • Автор темы DmbITpo
  • Дата начала
D

DmbITpo

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

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

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

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

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

Azrael

#2
Чисто алгоритм, придумал только что. пусть x = 00100001
В цикле формируем числа a1 = 10000001, в следующем a2 = 01000010 и т.д. Внутри цикла
1. b = x and a(i). для a1 получим b = 00000001
2. c = not( b ). получим с = 11111110
3. d = a(i) and c. получим d = 10000000
4. x = x and (not(a(i)), x = 00100000
5. x = x or d, x = 10100000

ну и дальше в цикле
 
D

DmbITpo

#3
спасибо!

Мы вот такой код придумали :


Код:
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);
 
Y

Yason

#4
Краткий ответ:
Код:
char bit_reverse (char bits)
{
bits = ((bits & 0x0F) << 4) | ((bits & 0xF0) >> 4);
bits = ((bits & 0x33) << 2) | ((bits & 0xcc) >> 2);
bits = ((bits & 0x55) << 1) | ((bits & 0xaa) >> 1);
return bits;
}
(с)тырено отсюда (там же есть шикарный код на асме для AVRов, 13 тактов).

Ещё вариант через 64-битные числа:
Код:
unsigned char b; // reverse this byte
b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;
Ну и в нагрузку - книжка Г. Уоррена "Алгоритмические трюки для программистов" (djvu, 2.5MiB, зеркало), где сабжу посвящено три с лишним страницы в главе 7 :rolleyes:
 
B
#5
...
Поменять местами эти биты надо в числе двоичном, например таком: 0010001. Результат должен быть 1010000 .
...
что-то я не понял как ты этот результат получил... во-первых чем надо оперировать? байтами? словами?
надо поменять только первый и последний или полнистью все число перевернуть!??
 
T

tinto

#6
а как сделать чтоб при ничётном количестве битов 7ой бит устанавливался в 0 а при чётно в 1?

вот задача сама вот сама задача
Задача 1.18. "ШИФРОВАНИЕ ОБРАТНОЙ ПЕРЕСТАНОВКОЙ БИТОВ". Вводится последовательность строк символов не длиннее 46 символов. Допустимые символы в строке - латинские буквы, цифры, знаки препинания и пробел. Окончание входного потока - ввод строки, начинающейся с символа "?". Максимальное количество строк равно 7. Шифрование состоит в том, что в двоичном коде каждого символа (байте) биты переставляются в обратном порядке, а затем бит 7 устанавливается в 0/1 при не/четном количестве 1-битов в байте, формируя код зашифрованного символа. Формируется также статистическая информация. Примерный вид выходной информации:
Входной текст:
(последовательность входных строк)
Введено К строк, всего N символов,
минимальная длина строки М1 символов.
максимальная длина строки М2 символов.
Получен шифрованный текст:
(последовательность обработанных строк