Разбор задачи «Ночной сигнал»

Идея задачи

Дано положительное целое число n. Нужно перевести его в двоичную запись без ведущих нулей, затем заменить каждый бит на противоположный:

• 0 → 1
• 1 → 0

После этого надо вернуть получившееся число в десятичной системе.

Например:

• 5 в двоичной системе — это 101
• после инвертирования получаем 010
• это число 2

Главная тонкость задачи состоит в том, что инвертировать нужно не все биты типа int, а только значащие биты числа.

Почему нельзя просто взять ~n

Может показаться, что задача решается одной операцией побитового НЕ.

Например, для числа 5 можно попробовать написать:

~5

Но это будет неправильный подход.

Оператор ~ переворачивает все биты числа в памяти. У типа int битов гораздо больше, чем в короткой записи 101. Поэтому вместе со значащими битами перевернутся и старшие биты.

Нам же по условию нужно работать только с записью числа без ведущих нулей.

Значит, нам нужно:

1. понять, сколько бит занимает число;
2. построить маску из такого же количества единиц;
3. перевернуть нужные биты с помощью XOR.

Основная идея решения

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

Например:

• n = 5
• двоичная запись: 101
• здесь k = 3
• нужная маска: 111

Теперь сделаем:

n ^ mask

Почему это работает?

Потому что в XOR:

• 0 ^ 1 = 1
• 1 ^ 1 = 0

То есть XOR с единицей переворачивает бит.

Для нашего примера:

• 101
• 111
• 101 ^ 111 = 010

Получаем ответ 2.

Как построить маску

Будем постепенно получать числа:

• 1
• 11
• 111
• 1111
• ...

В десятичной записи это:

• 1
• 3
• 7
• 15
• ...

Каждый раз можно делать так:

mask = (mask << 1) | 1

Что здесь происходит:

• mask << 1 — сдвигаем биты влево;
• | 1 — приписываем справа единицу.

Например:

• было 11
• после сдвига: 110
• после | 1: 111

Будем расширять маску, пока она не станет не меньше числа n.

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

Рассмотрим n = 10.

В двоичной системе:

10 = 1010

Нужно перевернуть все 4 значащих бита.

Строим маску:

• 1
• 3 = 11
• 7 = 111
• 15 = 1111

Теперь считаем:

1010
1111
----
0101

Это число 5.

Значит, ответ: 5.

Алгоритм

1. Считать число n.
2. Создать маску mask = 1.

3. Пока mask < n, делать:

   • mask = (mask << 1) | 1
4. Вывести n ^ mask.

Почему цикл работает правильно

Пока маска меньше числа, в ней точно недостаточно единиц для покрытия всех значащих битов.

Например:

• n = 10 (1010)
• маска 7 — это 111

Маска 111 слишком короткая: в числе 4 бита, а в маске только 3 единицы.

Когда получим 15 (1111), длина маски станет достаточной.

Именно такая маска нам и нужна.

Решение на C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int mask = 1;
    while (mask < n) {
        mask = (mask << 1) | 1;
    }

    cout << (n ^ mask) << '\n';
    return 0;
}

Пояснение к коду

• mask = 1 — начинаем с одной единицы;
• в цикле расширяем маску;
• когда маска стала подходящей, берём XOR;
• результат выводим.

Решение на Python

n = int(input())

mask = 1
while mask < n:
    mask = (mask << 1) | 1

print(n ^ mask)

Пояснение к коду

Идея полностью такая же, как и в C++:

• строим маску из единиц;
• маска должна покрывать всю двоичную запись числа;
• затем инвертируем нужные биты через XOR.

Альтернативный способ мышления

Можно думать не через сравнение mask < n, а через количество битов.

Пусть мы хотим узнать длину двоичной записи числа. Тогда можно копию числа сдвигать вправо, пока она не станет равна нулю.

Например, для 13:

• 1101
• 110
• 11
• 1
• 0

Мы сделали 4 шага, значит, число занимает 4 бита. Тогда нужная маска — 1111.

Это тоже правильный подход, но вариант с прямым наращиванием маски обычно короче и удобнее.

Типичные ошибки

Ошибка 1. Использовать ~n

Это переворачивает все биты типа, а не только значащие.

Ошибка 2. Работать со строками без необходимости

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

В этой задаче намного естественнее решить всё побитовыми действиями.

Ошибка 3. Неправильно построить маску

Некоторые пытаются строить маску фиксированной длины, например на 31 бит. Это снова приводит к инвертированию лишних старших битов.

Маска должна быть ровно по длине числа.

Ошибка 4. Забыть про случай n = 1

Если n = 1, то двоичная запись — 1, после инверсии получаем 0.

Наш алгоритм это корректно обрабатывает:

• mask = 1
• цикл не выполняется
• 1 ^ 1 = 0

Проверим несколько примеров

Пример 1

n = 5

• двоичная запись: 101
• маска: 111
• ответ: 101 ^ 111 = 010 = 2

Пример 2

n = 1

• двоичная запись: 1
• маска: 1
• ответ: 1 ^ 1 = 0

Пример 3

n = 8

• двоичная запись: 1000
• маска: 1111
• ответ: 1000 ^ 1111 = 0111 = 7

Пример 4

n = 7

• двоичная запись: 111
• маска: 111
• ответ: 111 ^ 111 = 000 = 0

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

Пусть число занимает k бит.

Тогда:

• время работы: O(k)
• память: O(1)

Так как k примерно равно log2(n), можно также писать:

• время: O(log n)
• память: O(1)

Вывод

В этой задаче важно заметить, что инвертировать нужно только значащие биты числа. Поэтому мы не можем просто использовать побитовое НЕ.

Правильная идея такая:

• построить маску из единиц той же длины, что и число;
• выполнить XOR числа с этой маской.

Это короткое, красивое и очень надёжное решение, которое хорошо тренирует понимание двоичной записи и побитовых операций.