VPF::[С++] Программа перестановки битов

RoyalFox

Дата 12.1.2011, 10:18 (ссылка)

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

Загрузка ...

Новичок

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

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

Добрый день, помогите пожалуйста написать программу! Сижу на экзамене, а по программированию я полный ноль :(

Задача: "Разработать программу, осуществляющую перестановку битов целого положительного числа в обратном порядке, начиная со старшей единицы. Например, 20 (в десятичной системе) = 10100 (двоичная) -> 00101 (дв-я) = 5 (10-я), 79 (10-я) = 1001111 (2-я) -> 1111001 (2-я)= 121 (10-я)...
smile

Silent

Дата 12.1.2011, 10:31 (ссылка)

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

Загрузка ...

Опытный

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

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

Держи, двоешник. Передавай привет преподу

Код


#include <stdio.h>

int A,B;

int main()
{
  scanf("%d",&A);
  while (A != 0)
  {
    B = (B << 1) + (A & 1);
    A >>= 1;
  }
  printf("%d",B);
  return 0;
}

RoyalFox

Дата 12.1.2011, 10:40 (ссылка)

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

Загрузка ...

Новичок

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

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

спасибо!!! А можно комментарии еще? А то препод явно меня завалит из за объяснений

Silent

Дата 13.1.2011, 10:58 (ссылка)

(голосов:1)

Загрузка ...

Опытный

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

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

Кстати, полистывая книжку Г. Уоррена (Henry S. Worren) "Алгоритмические трюки для программистов" (стр.107), случайно нашел интересную вещь реверса битов (задача не точно та, которая в топике, но аналогичная) - изменить порядок следования битов на обратный. Пример:
reverse(0x01234567) = 0xE6A2C480

алгоритм:

Код


uint reverse(uint x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCC) >> 2;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4;
    x = (x << 24) | ((x & 0xFF00) << 8) |
        ((x >> 8) & 0xFF00) | (x >> 24);
    return x;
}

Данный прием можно использовать в поставленной задаче, если сдвинуть полученное число влево на количество ведущих нулей в первоначальном числе (для наглядности в примере будем оперировать типом byte):
перевернем с помощью вышеприведенного кода - 20(10)=00010100(2), reverse(00010100) = 00101000, и сдвинем влево на 3 разряда - 0010100 >> 3 = 00000101(2) = 5(10)

Моя неугомонная ж... эм... голова логично предположила, что сей автор имеет затычку и на такую подзадачу, как подсчет количества ведущих нулей - и я не ошибся, стр.86:

Код


int count_zeros(int x)
{
    int n = 0;
    if (x == 0) n = 32;
    if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFF) { n += 8;  x <<= 8;  }
    if (x <= 0x0FFFFFFF) { n += 4;  x <<= 4;  }
    if (x <= 0x3FFFFFFF) { n += 2;  x <<= 2;  }
    if (x <= 0x7FFFFFFF) { n += 1; }
    return n;
}

Так что предлагаю второй вариант решения задачи экзамена:

Код


#include <stdio.h>

typedef unsigned int uint;
uint A,B;

uint reverse(uint x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCC) >> 2;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4;
    x = (x << 24) | ((x & 0xFF00) << 8) |
        ((x >> 8) & 0xFF00) | (x >> 24);
    return x;
}

int count_zeros(uint x)
{
    int n = 0;
    if (x == 0) n = 32;
    if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFF) { n += 8;  x <<= 8;  }
    if (x <= 0x0FFFFFFF) { n += 4;  x <<= 4;  }
    if (x <= 0x3FFFFFFF) { n += 2;  x <<= 2;  }
    if (x <= 0x7FFFFFFF) { n += 1; }
    return n;
}

int main()
{
    scanf("%d",&A);
    B = reverse(A);
    B >>= count_zeros(A);
    printf("%u",B);
    return 0;
}

Конечно, понятность кода снизилась, да и применимость тоже, но он выполняется за всегда постоянное количество тактов, без условных переходов - его производительность выше. Замеры показывают цифру 4х в однопоточном варианте. Для многопоточного эта цифра будет еще выше.

P.S. Я бы за этот код, есс-но с развернутыми комментариями о производительности, применимости и прочих ньюансах, выгнал бы сдающего с экзамена, с "отлично" конечно же smile

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