Минимальное количество переворотов, чтобы сделать A | B == C

Привет, друзья.

Несмотря на выходный день, у нас вами разбор новой задачи. В этот раз рассматриваем тему битовых манипуляций.

Сложность: 🟡 Средняя

ℹ️ Описание

Даны три целых положительных числа a, b и c.

Необходимо найти минимальное количество переворотов битов в a и b, чтобы результат операции a OR b (побитовая операция ИЛИ) был равен c. Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или c 0 на 1 в его двоичном представлении.

⚠️ Ограничения

Значение каждого аргумента находится в диапазоне от 1 до 10^9

1️⃣ Пример

Входные данные: a = 2, b = 6, c = 5

Ответ: 3

2️⃣ Пример

Входные данные: a = 4, b = 2, c = 7

Ответ: 1

3️⃣ Пример

Входные данные: a = 1, b = 2, c = 3

Ответ: 0

✅ Решение

Чтобы решить задачу, нам необходимо представить числа a, b и c в двоичном виде и произвести их сравнение побитно. Недостающие биты в числах мы заполняем ведущими нулями.

Если бит числа c равен 1, это означает, что в a и b как минимум один бит на этой же позиции должен быть равен 1, чтобы условие a | b == c было истинным. Если же оба бита в a и b равны 0, то нам необходимо изменить любой из битов на единицу. Не важно какой именно бит, потому что это не меняет результат.

Если бит числа c равен 0, это означает, что биты и в числе a, и в числе b должны быть равны нулю, чтобы условие a | b == c было истинным. В этом случае нам нужно изменять биты в a и b только в том случае, если они равны 1.

❓ Как получить двоичное представление числа ❓

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

- Чтобы получить младший бит числа в двоичном представлении (крайний справа) необходимо взять остаток от деления числа на 2. Это работает потому что у четных чисел младший бит всегда равен 0, а у нечетных — 1.

- Чтобы откинуть младший бит у числа достаточно разделить его на 2 без остатка. В таком случае мы получим новое число, которое в двоичном представлении равно предыдущему числу без младшего бита.

В итоге, нам необходимо иметь цикл, который проверяет младшие биты всех чисел на каждой итерации и увеличивает счетчик, а по завершению итерации модифицирует исходные числа. Этот цикл работает до тех пор, пока все числа не станут равны 0.

Посмотреть реализацию в блоге

#bit_manipulation #medium