Учитывая два числа A и B, что может быть максимальным числом, которое может быть сформировано операцией AND любых двух чисел x и y между A и B, означает A ≤ x < y ≤ B.Максимальное число И двух чисел
Пример: а = 1 и в = 3, то ответ 2.
Я не могу пойти на грубый и как а и в могут пойти Шифрование до 10^18
Примечания: этот ответ предполагает ≥- , что справедливо, учитывая, что этот вопрос не привязан к конкретному языку или целочисленному представлению, которое придавало бы значение битным операциям для отрицательных целых чисел.
Если B нечетно, максимальный x & y - B-1, полученный путем выбора y = B и x = B-1.
Если B четный и A достаточно мал, чтобы можно было выбрать y = B-1 и x = B-2, то для этого выбора x и y максимальный B-2. В противном случае существует только один выбор: B & (B-1), независимо от того, что оценивается.
Это было очень очевидно в ретроспективе, приятное решение. – IVlad
@Pascal Cuoq Почему A <= 0 ??? – user3840069
Для расширения Pascal Cuoq's excellent answer, если мы позволяем < 0 и считать, two's complement арифметики (что практически все современные компьютеры используют для целых чисел), то мы снова имеем несколько случаев:
Если A B, то можно выбрать х = -1 и у = в, в этом случае х & у = B.
< Если A B < 0, то все работает так же, как и для положительных чисел: если B нечетно, или если A = B-1, то оптимальным выбором является x = B-1, y = B; в противном случае это x = B-2, y = B-1.
(Причина, по которой работает точно так же, потому что двоичное дополнение знаковой арифметика, по существу, идентична беззнаковая двоичной арифметика, за исключением того, что мы интерпретируем число с их старшим битом установлен как отрицательными. Таким образом, только действительно новые является случай, где диапазон от А до B «обтекает» от -1 до 0.)
Суммируя эти результаты, мы имеем, что для ≤ х < у ≤ B, с любой заданной (возможно, подписанное дополнение 2) A и B, максимум x & yi с:
< Если A 0 ≤ В, то х = -1 и у = В выход х у = & Б.
В противном случае, если В нечетно, х = В-1 и y = B выход x & y = B-1.
В противном случае, если B> A + 1, то x = B-2 и y = B-1 дают x & y = B-2.
Если не выполнено ни одного из вышеуказанных случаев, единственным оставшимся случаем является B = A + 1 (с четным B); в этом случае единственным возможным выбором является x = A, y = B; независимо от того, что x & y равно в этом случае, это тривиально максимум.
@SMA Я хочу, чтобы максимизировать И и его не нужно & B будет максимальной – user3840069
@SMA '& B' не максимум, который может быть получен с помощью операции AND с числами между' Ā' и 'B '. –