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

Тема в разделе "Общие вопросы по С и С++", создана пользователем DmbITpo, 10 апр 2008.

  1. DmbITpo

    DmbITpo Гость

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

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

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

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

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

    Azrael Гость

    Чисто алгоритм, придумал только что. пусть 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

    ну и дальше в цикле
     
  3. DmbITpo

    DmbITpo Гость

    спасибо!

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


    Код (Text):
    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);
     
  4. Yason

    Yason Гость

    Краткий ответ:
    Код (Text):
    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-битные числа:
    Код (Text):
    unsigned char b; // reverse this byte
    b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;
    Ну и в нагрузку - книжка Г. Уоррена "Алгоритмические трюки для программистов" (djvu, 2.5MiB, зеркало), где сабжу посвящено три с лишним страницы в главе 7 :rolleyes:
     
  5. biz

    biz Гость

    что-то я не понял как ты этот результат получил... во-первых чем надо оперировать? байтами? словами?
    надо поменять только первый и последний или полнистью все число перевернуть!??
     
  6. tinto

    tinto Гость

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

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

    bizybiz Гость

    А третий и предпредпоследний менять не надо??
     
Загрузка...

Поделиться этой страницей