Задача Bitwise AND

В задаче Bitwise ANDopen in new window дано множество чисел [latex]S = \{1, 2, 3, ..., N\}[/latex], нужно найти два числа [latex]A[/latex] и [latex]B[/latex] такие что значение [latex]A \& B[/latex] (побитовый оператор И) наибольшее, но меньше заданного [latex]K[/latex]. Вывести наибольшее возможное [latex]A \& B[/latex].

Ограничения:

• [latex]2 \leq N \leq 10^3[/latex]
• [latex]2 \leq K \leq N[/latex]

Решение

Решение с перебором рабочее, но не проходит по скорости: всего пар [latex]N * (N - 1)[/latex], сложность получается [latex]O(n^2)[/latex].

У этой задачи есть решение за константное время. Предположим число [latex]K[/latex] нечётное. Это значит что в побитовой записи справа у него находится единица:

[latex]11_{10} = 1011_2[/latex]

Рассмотрим [latex]K-1[/latex], в двоичной записи все его цифры совпадают с [latex]K[/latex] кроме последней в которой находится 0:

[latex]10_{10} = 1010_2[/latex]

Исходя из этого, для нечётного [latex]K[/latex] всегда выполняется равенство [latex](K - 1) \& K = K - 1[/latex].

Так как [latex]N \geq K[/latex] то мы всегда можем взять [latex]A = K - 1[/latex] и [latex]B = K[/latex] и получить максимальный ответ [latex]K - 1[/latex].

Остался случай с чётным [latex]K[/latex]. Если [latex]K[/latex] чётное число, то [latex]K-1[/latex] нечётное, для него можно провести те же самые рассуждения и получить ответ [latex]K-2[/latex]. Но можно ли для чётного [latex]K[/latex] получить ответ [latex]K-1[/latex]?

Рассмотрим детальнее числа входящие в выражение [latex]A \& B[/latex]. Будем исходит из того что в ответе задачи получается число [latex]K-1[/latex], значит либо [latex]A[/latex], либо [latex]B[/latex] равно [latex]K - 1[/latex]. Предположим число [latex]A = K - 1[/latex]. Число [latex]B[/latex] не может быть меньше [latex]A[/latex], так как должно содержать единицы в тех же позициях что и число [latex]A[/latex]. Чтобы [latex]B[/latex] отличалось и было минимальным оно должно содержать дополнительную единицу в самом правом разряде в котором в [latex]A[/latex] содержится 0. Такое число получается при [latex]B = (K - 1) | K[/latex] (побитовое ИЛИ).

По условию задачи [latex]A, B \leq N[/latex]. [latex]A = K - 1[/latex] подходит под это условие, а вот [latex]B = (K - 1) | K[/latex] неизвестно. Пример с числами:

• [latex]K = 46_{10} = 101110_2[/latex]
• [latex]K - 1 = 45_{10} = 101101_2[/latex]
• [latex](K - 1) | K = 101111_2 = 47_{10}[/latex]

При выполнении условия [latex](K - 1) | K \leq N[/latex] получаем что максимально возможное число в ответе [latex]K - 1[/latex]. Если же условие не выполняется, то ответ будет [latex]K - 2[/latex].

Причём чётность числа проверять не обязательно. Решение для чётного [latex]K[/latex] всегда подходит и для нечётного, так как условие [latex](K - 1) | K \leq N[/latex] всегда выполняется для нечётного [latex]K \leq N[/latex].

Код решения на Python:

n, k = [int(x) for x in input().split()]

print(k - 1 if (k - 1) | k <= n else k - 2)