K-е наименьшее натуральное число, имеющее сумму с заданным числом, равную побитовому ИЛИ с заданным числом

Даны два положительных целых числа X и K , задача состоит в том, чтобы найти K -е наименьшее натуральное число Y такое, что X + Y = X | Y , где | обозначает побитовую операцию ИЛИ.

Пример:

Input: X = 5, K = 1
Output: 2
Explanation: The first number is 2 as (2 + 5 = 2 | 5 )

Input: X = 5, K = 5
Output: 18
Explanation: The list of correct values is 2, 8, 10, 16, 18. The 5th number is this list is 18

Подход: данная проблема может быть решена следуя приведенным ниже шагам:

• Пусть конечное значение будет Y . Из свойств побитовых операций известно, что X + Y = X & Y + X | Y , где & - это побитовое И двух чисел
• Чтобы уравнение в постановке задачи было верным, значение X и Y должно быть равно 0.
• Таким образом, для всех позиций, если i-й бит в X включен, то он должен быть выключен для всех возможных решений Y.
• Например, если X = 1001101001 в двоичном формате (617 в десятичном представлении), то последние десять цифр y должны быть Y = 0**00*0**0, где '*' обозначает либо ноль, либо единицу. Кроме того, мы можем добавить любое количество любых цифр в начало числа, поскольку все старшие биты равны нулям.
• Таким образом, окончательное решение будет состоять в том, чтобы рассматривать все позиции, где бит может быть равен 0 или 1, как последовательность слева направо и находить двоичную запись K .
• Заполните все позиции в соответствии с двоичной записью K

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

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