Разбор задачи «Переключатели на панели»

Идея задачи

Нам даны два числа:

• start — текущее состояние,
• goal — требуемое состояние.

За один ход можно изменить ровно один бит числа start.

Нужно найти минимальное количество таких изменений, чтобы получить число goal.

Главное наблюдение

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

Например:

• start = 10 → 1010
• goal = 7 → 0111

Сравним биты по позициям:

• первый отличаются,
• второй отличаются,
• третий совпадают,
• четвёртый отличаются.

Всего различаются 3 бита, значит и ответ равен 3.

Итак, задача сводится к очень простой мысли:

ответ — это количество позиций, в которых двоичные записи чисел различаются.

Как быстро найти различающиеся биты

Для этого очень удобно использовать побитовую операцию XOR (^).

Свойство XOR

Для двух битов:

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

То есть XOR даёт 1 ровно тогда, когда биты различаются.

Значит, если вычислить:

start ^ goal

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

Остаётся только посчитать количество единичных битов.

Пример

Пусть:

• start = 10
• goal = 7

Тогда:

• 10 = 1010
• 7 = 0111

Посчитаем XOR:

• 1010 ^ 0111 = 1101

В числе 1101 три единицы.

Значит, нужно сделать 3 изменения.

Почему это решение корректно

Докажем это аккуратно.

Рассмотрим любую битовую позицию.

Случай 1. Биты равны

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

Случай 2. Биты различаются

Если в некоторой позиции биты разные, то этот бит обязательно нужно перевернуть хотя бы один раз.

Причём одного переворота достаточно: после него бит станет таким, как в goal.

Получается, что:

• каждая различающаяся позиция требует ровно одного действия;
• каждая совпадающая позиция не требует действий.

Следовательно, минимальное число действий равно числу различающихся битов.

А XOR как раз показывает такие позиции, поэтому ответ — это количество единиц в числе start ^ goal.

Алгоритм

1. Считать числа start и goal.
2. Вычислить x = start ^ goal.
3. Посчитать количество единичных битов в x.
4. Вывести ответ.

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

Если числа стандартного размера (например, до 32 бит), то:

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

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

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

Вариант с готовой функцией

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

int main() {
    int start, goal;
    cin >> start >> goal;

    cout << __builtin_popcount(start ^ goal) << '\n';
    return 0;
}

Пояснение

В C++ функция __builtin_popcount(x) считает количество единичных битов в числе x.

Поэтому запись

__builtin_popcount(start ^ goal)

сразу даёт ответ.

Решение на Python

Вариант с готовым методом

start, goal = map(int, input().split())
print((start ^ goal).bit_count())

Пояснение

В Python у целых чисел есть метод .bit_count(), который считает количество единиц в двоичной записи числа.

Поэтому здесь логика полностью та же:

• сначала делаем XOR,
• потом считаем число единичных битов.

Если нельзя использовать готовые функции

Иногда полезно уметь считать единичные биты вручную.

Вариант на C++

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

int main() {
    int start, goal;
    cin >> start >> goal;

    int x = start ^ goal;
    int ans = 0;

    while (x > 0) {
        ans += x % 2;
        x /= 2;
    }

    cout << ans << '\n';
    return 0;
}

Вариант на Python

start, goal = map(int, input().split())

x = start ^ goal
ans = 0

while x > 0:
    ans += x % 2
    x //= 2

print(ans)

Более эффективный ручной способ

Есть полезный приём:

x & (x - 1) удаляет последнюю единицу в двоичной записи числа x.

Например:

• x = 110100
• x - 1 = 110011
• x & (x - 1) = 110000

То есть одна единица исчезает.

Если делать так в цикле, то количество итераций будет равно числу единиц.

C++

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

int main() {
    int start, goal;
    cin >> start >> goal;

    int x = start ^ goal;
    int ans = 0;

    while (x > 0) {
        x = x & (x - 1);
        ans++;
    }

    cout << ans << '\n';
    return 0;
}

Python

start, goal = map(int, input().split())

x = start ^ goal
ans = 0

while x > 0:
    x = x & (x - 1)
    ans += 1

print(ans)

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

Ошибка 1. Пытаться сравнивать числа по значению, а не по битам

Например, иногда хочется взять модуль разности abs(start - goal), но это никак не связано с количеством изменяемых битов.

Например:

• start = 8 (1000)
• goal = 7 (0111)

Разность равна 1, но поменять нужно 4 бита.

Ошибка 2. Забыть, что нужен минимум действий

В каждой несовпадающей позиции достаточно одного изменения. Больше не нужно.

Ошибка 3. Неправильно считать единицы вручную

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

Вывод

Это короткая, но очень полезная задача на побитовые операции.

Ключевая идея такая:

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

Эта задача хорошо показывает, как одна удачная побитовая операция сразу превращает задачу в очень простую.