Минимальные битовые перестановки между заданными числами, чтобы сделать их побитовое ИЛИ равным побитовому И

Для заданных двух положительных целых чисел A и B задача состоит в том, чтобы вычислить минимальное количество требуемых операций, чтобы побитовое ИЛИ для A и B равнялось побитовому И для A и B , т. е . (A&B)=(A|B) , где в каждой операции выбираются два индекса i и j и i ^-й бит A меняется местами с j ^-м битом B. Если невозможно сделать (A&B)=(A|B), выведите -1.

Примеры:

Input: A = 1, B = 2
Output: 2
Explanation:
A₁₀ ≡ 01₂, B₁₀ ≡ 10₂
The following sequence of moves can be performed:

• i = 1, j = 1⇒ A = 11, B = 00 (A|B = 3, A&B = 0).
• i = 1, j = 0⇒ A = 01, B = 01 (A|B = 1, A&B = 1).

Thus, 2 moves are required.

Input: A = 27, B = 5
Output: 3
Explanation:
A₁₀ ≡ 11011₂, B₁₀ ≡ 00101₂
The following sequence of moves can be performed:

• i = 4, j = 3⇒ A = 01011, B = 01101 (A|B = 15, A&B = 9).
• i = 2, j = 2⇒ A = 01111, B = 01001 (A|B = 15, A&B = 9).
• i = 2, j = 1⇒ A = 01011, B = 01011 (A|B = 11, A&B = 11).

Thus, 3 moves are required.

Подход :
Наблюдение: основное наблюдение для решения этой проблемы заключается в том, что для (A&B)=(A|B) A должно быть равно B, потому что если установлены только два бита, то равны только их побитовое И и побитовое ИЛИ.

Выполните следующие шаги, чтобы решить проблему:

1. Подсчитайте общее количество установленных битов в A и B .
2. Если число нечетное, два числа нельзя сделать равными, поэтому выведите -1.
3. Инициализировать два счетчика oneZero =0 и zeroOne =0
4. Пройдите через биты A и B и сделайте следующее:
   • Если текущий бит A установлен, а текущий бит B не установлен, то есть (1, 0), увеличьте oneZero .
   • Если текущий бит A не установлен, а текущий бит B установлен, т. е. (0, 1), увеличивается на ноль .
5. Чтобы минимизировать количество требуемых операций, оптимально выбрать два (1, 0) или два (0, 1) индекса и поменять местами любой из них, т. е. требуется только половина операций oneZero и zeroOne .
6. Если oneZero нечетный (что означает, что zeroOne также нечетный), потребуются еще две операции, чтобы превратить (0, 1) и a (1, 0) в (1, 1) и (0, 0)
7. Итак, окончательный ответ: (oneZero/2)+(zeroOne/2)+(oneZero%2?2:0).

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(Log ₂ N)
Вспомогательное пространство: O(1)