Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [С++] Программа перестановки битов

Автор: RoyalFox 12.1.2011, 10:18

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

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

Автор: Silent 12.1.2011, 10:31

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

Код


#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

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

Автор: Silent 13.1.2011, 10:58

Кстати, полистывая книжку Г. Уоррена (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