Разбор задачи «Зеркальный сигнал»

Идея задачи

Нам дано число n, которое рассматривается как 32-битное беззнаковое число. Нужно развернуть порядок его битов.

Если двоичная запись числа была такой:

b31 b30 b29 ... b2 b1 b0,

то после разворота должна получиться запись:

b0 b1 b2 ... b29 b30 b31.

Важно понимать: нас интересуют ровно 32 бита, даже если число маленькое и в обычной двоичной записи выглядит коротко.

Например, число 5 в 32-битной записи выглядит так:

00000000000000000000000000000101

После разворота получится:

10100000000000000000000000000000

Это уже совсем другое число.

Наблюдение

Когда мы хотим развернуть биты, удобно строить ответ постепенно.

Пусть у нас есть число n. Его последний бит можно получить так:

n & 1

• если последний бит равен 0, результат будет 0;
• если последний бит равен 1, результат будет 1.

После этого можно сдвинуть n вправо на один бит:

n >>= 1

Так мы убираем уже обработанный бит.

Теперь подумаем, как строить ответ.

Если мы хотим записывать новые биты справа, то перед добавлением очередного бита нужно освободить для него место. Это делается сдвигом ответа влево:

ans <<= 1

После этого можно дописать бит:

ans |= (n & 1)

Таким образом, мы по одному переносим биты из конца числа n в начало ответа.

Пошаговый пример

Разберём маленький пример: n = 13.

В двоичном виде это:

1101

Если смотреть как 32-битное число, то слева просто много нулей. Нам важны действия алгоритма.

Начинаем:

• ans = 0
• n = 13

Шаг 1

Последний бит числа n равен 1.

• ans = (0 << 1) | 1 = 1
• n >>= 1, теперь n = 6

Шаг 2

Последний бит числа n равен 0.

• ans = (1 << 1) | 0 = 2
• n >>= 1, теперь n = 3

Шаг 3

Последний бит числа n равен 1.

• ans = (2 << 1) | 1 = 5
• n >>= 1, теперь n = 1

Шаг 4

Последний бит числа n равен 1.

• ans = (5 << 1) | 1 = 11
• n >>= 1, теперь n = 0

Если бы мы работали только с четырьмя битами, получили бы:

1101 -> 1011

Но в задаче нужно выполнить ровно 32 шага, потому что число рассматривается как 32-битное.

Алгоритм

1. Заводим переменную ans = 0.

2. Повторяем 32 раза:

   • сдвигаем ans влево на 1;
   • добавляем в него последний бит числа n;
   • сдвигаем n вправо на 1.
3. Выводим ans.

Почему алгоритм работает

Докажем идею простыми словами.

На каждом шаге мы берём очередной бит числа n, начиная с самого правого.

• На первом шаге берётся бит b0 и становится самым правым битом текущего ответа.
• На втором шаге ответ сдвигается влево, и к нему приписывается b1.
• На третьем шаге приписывается b2.
• И так далее.

Через 32 шага в ответе окажутся биты в порядке:

b0 b1 b2 ... b30 b31

То есть ровно тот порядок, который и требуется по условию.

Значит, алгоритм корректен.

Оценка сложности

Мы всегда выполняем ровно 32 итерации.

• Время работы: O(32), то есть фактически O(1).
• Память: O(1).

Это очень эффективное решение.

Реализация на C++

Обычная версия

#include <bits/stdc++.h>
using namespace std;

uint32_t reverseBits(uint32_t n) {
    uint32_t ans = 0;
    for (int i = 0; i < 32; i++) {
        ans = (ans << 1) | (n & 1);
        n >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    uint32_t n;
    cin >> n;

    cout << reverseBits(n) << '\n';
    return 0;
}

Реализация на Python

Обычная версия

def reverse_bits(n):
    ans = 0
    for _ in range(32):
        ans = (ans << 1) | (n & 1)
        n >>= 1
    return ans


n = int(input())
print(reverse_bits(n))

Более понятная версия на Python

Если битовые операции пока кажутся непривычными, ту же идею можно записать почти арифметически.

def reverse_bits(n):
    ans = 0
    for _ in range(32):
        last_bit = n % 2
        ans = ans * 2 + last_bit
        n //= 2
    return ans


n = int(input())
print(reverse_bits(n))

Здесь:

• n % 2 — это последний бит числа;
• ans * 2 — это то же самое, что сдвиг влево;
• n //= 2 — это то же самое, что сдвиг вправо для неотрицательных чисел.

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

Частые ошибки

1. Делать не 32 шага, а пока n > 0

Это неверно.

Если число маленькое, в его записи много ведущих нулей, а в задаче они важны, потому что мы работаем именно с 32-битным представлением.

Например, для числа 1:

00000000000000000000000000000001

после разворота должно получиться:

10000000000000000000000000000000

Если остановиться слишком рано, правильный ответ не получится.

2. Использовать знаковый тип там, где нужен беззнаковый

В C++ лучше использовать uint32_t, потому что задача прямо говорит о 32-битном беззнаковом числе.

3. Путать направление сдвигов

• << — сдвиг влево;
• >> — сдвиг вправо.

В этой задаче:

• ответ сдвигаем влево;
• исходное число сдвигаем вправо.

Вывод

Это хорошая задача на аккуратную работу с битами.

Главная идея очень проста:

• берём у числа последний бит;
• дописываем его в ответ;
• повторяем 32 раза.

Несмотря на простую реализацию, задача отлично тренирует понимание:

• битовых операций;
• двоичной записи числа;
• различия между «обычной записью числа» и фиксированной 32-битной записью.

Если эта идея понятна, дальше будет гораздо легче разбирать более сложные битовые задачи.