Нахождение max of ANDing между двумя числами в Python

Question

Я начинаю программировать на Python. У меня есть два числа A и B от пользователя.

Моя проблема состоит в нахождении макс (Р и Q) где А = Р < < < В = В

У меня есть два решения прямо сейчас для этого.

Решение 1: # Идентификация со всеми комбинациями. Это решение работает, если комбинации меньше. Для более высоких значений он выдает большую память.

given = raw_input() 
n= list(map(int,given.split())) 

A = n[0] 
B = n[1] 

newlist = range(B+1) 
# print newlist 

# Finding all combinations 
comb = list(itertools.combinations(newlist,2)) 
# print comb 

# ANDing 
l = [] 
for i in com: 
    x = i[0] & i[1] 
    l.append(x) 
# print l 

print max(l) 

Раствор 2: После наблюдения множество входов, выходов, когда В == Одд, макс (значение) = B-1 и B == Даже, макс (значение) = В-2.

given = raw_input() 
n= list(map(int,given.split())) 

A = n[0] 
B = n[1] 
if B % 2 == 0: 
    print (B - 2) 
else: 
    print (B -1) 

В соответствии с заявлением о проблеме я не использую никаких решений для решения 2. Тем не менее, я получаю правильный вывод.

Но я ищу намного проще и питонскую логику. Есть ли другой способ/логика для решения этой проблемы?

Answer 1

Я думаю, что это должно работать:

given = raw_input() 
a, b = tuple(map(int,given.split())) 
print(max([p & q for q in range(a,b+1) for p in range(a,q)])) 

Answer 2

Ваше второе решение является оптимальным решением. Но почему? Во-первых, рассмотрим, что логическое И выполняется в двоичном представлении числа, и можно только создать число, меньшее или равное наименьшему операнду оператора И. Например, 9 представлен как 1001, и нет числа, которое может быть обработано 9, которое производит число, превышающее 9. Действительно, единственными возможными выходами для другого номера с 9 будут 9, 8, 1 и 0. Или, альтернативно, самый большой результат от анкетирования 9 с номером меньше 9, равен 9 меньше наименее значимого бита (так 8). Если вы не уверены в двоичном представлении числа, вы всегда можете использовать функцию bin. например. bin(9) =>'0b1001'.

Начнем с нечетных чисел (поскольку они самые простые). Нечетные числа легки, потому что они всегда имеют немного в позиции устройства. Таким образом, максимально возможное число, которое мы можем получить, это B меньше этого бита в позиции устройства (так что B - 1 является максимальным). Например, 9 представлен как 1001. Избавьтесь от единицы бит, и у нас есть 1000 или 8. 9 and 8 == 8, поэтому максимальный результат: 8.

Теперь попробуем нечто подобное с эвенов. Например, 14 представлен как 1110. Максимальное число, которое мы можем получить от 14-го с другим номером, будет 1100 (или 12). Как и с шансами, мы всегда должны проигрывать один бит, а наименьший возможный бит, который может быть потерян, - бит в позиции 2 с. Здесь нам повезло, так как 14 уже немного в позиции 2s. Но как насчет чисел, которые этого не делают? Попробуем 12 (представленный как 1100). Если бы мы потеряли наименьший бит от 12, у нас было бы 1000 или 8. Однако это не является максимально возможным.И это легко доказать, потому что максимум для 11 равен 10 (так как мы показали максимум для нечетного числа, это нечетное число меньше 1).

Мы уже показали, что наибольшее число, которое может быть получено при использовании двух разных чисел, - это большее число, меньшее его младшего значащего бита. Поэтому, если этот бит имеет значение 2 (в случае 14), когда мы можем просто потерять этот бит. Если этот бит имеет значение выше 2 (в случае 12), то мы знаем, что максимум является максимальным наибольшим нечетным числом, меньшим B (что на 1 меньше, чем нечетное число и 2 меньше, чем B).

Итак, у нас оно есть. Максимум для нечетного числа этого числа меньше 1. А максимум для четного числа является числом меньше 2.

def and_max(A, B): # note that A is unused 
    if B & 1: # has a bit in the 1 position (odd) 
     P, Q = B - 1, B 
    else: 
     P, Q = B - 2, B - 1 
    # print("P = ", P, "Q = ", Q) 
    return P & Q # essentially, return P 

Обратите внимание, что ни одно из этого не покрывают отрицательные числа. Это связано с тем, что большинство представлений отрицательных чисел находятся в two's complement. Это означает, что все отрицательные числа представлены как постоянное отрицательное число плюс положительное число. Например, используя 4-битное представление целых чисел, максимально возможное число будет 0111 (или 7, 4 + 2 + 1). Отрицательные числа будут представлены как -8 плюс некоторое положительное число. Эта отрицательная часть обозначается ведущим битом. Таким образом, -8 - 1000 (-8 + 0) и -1 - 1111 (-8 + 7). И это важная часть. Как только у вас есть -1, у вас есть все 1s битмаска, которая гарантированно потеряет отрицательную часть при использовании с положительным числом. Таким образом, максимум для max(P and Q), где A <= P < Q <= B and A < 0 всегда B. Где B < 0, мы больше не можем потерять отрицательный бит и поэтому должны максимизировать положительные бит снова.