Pythonの2つの数値のANDingの最大値を求める

Question

私はPythonコーディングの初心者です。私はユーザーから2つの数字AとBを持っています。

私の問題は、私はこのために今2つのソリューションを持っている最大（PとQ） < = P < Q < = B

を見つけることです。

解決方法1：＃すべての組み合わせでANDingするこの方法は、組み合わせが少ない場合に機能します。値を大きくすると、エラーを超えるメモリがスローされます。

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 ==奇数、MAX（値）= B-1およびBのための==でも、MAX（値）= 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にANDingを使用していません。まだ正しい出力が得られています。

しかし、私ははるかに簡単でPythonicロジックを探しています。これを解決する他の方法/ロジックはありますか？

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

あなたの第二の溶液は、最適なソリューションです。しかし、なぜ？まず、論理ANDが数値のバイナリ表現で実行され、AND演算子の最小のオペランド以下の数値を生成することのみが可能であると考えてください。例えば、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です。

ここで、evensと似たようなことを試してみましょう。例えば、14は、1110と表されます。私たちが14を別の番号で取得できる最大数は1100（または12）です。オッズと同様に、我々は常に1ビットを失う必要があり、失われる可能性のある最小のビットは2の位置にあるビットです。ここでは、幸いなことに、14がすでに2位に入っています。しかし、数字ではないのはどうですか？試してみましょう12（として表される1100）。 12から最小ビットを紛失した場合は、1000または8となります。しかし、これは可能な限り最大ではありません。11の最大値は10です（奇数の最大値は1より小さいため、奇数の最大値を示しているため）。これを簡単に証明できます。

2つの異なる数字から生成できる最も大きな数字が、その最も重要でないビットよりも大きい数字であることを既に示しました。したがって、そのビットが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を持っているとすぐに、正の数でアンドされたときに負の部分を失うことが保証されているすべての1秒のビットマスクがあります。したがって、max(P and Q)の最大値はA <= P < Q <= B and A < 0で、常にBです。 B < 0では、もはや負のビットを失うことができないので、正のビットを再び最大にしなければならない。