セット内の「AND」の最大値を見つける

Question

数値（x）としきい値を指定すると、xまでのすべての数値にBinary ANDを実行することで達成できる最大値を見つけることができます。閾値よりも高い。

例：2、3が入力された場合、この例で

A = 1 ; B = 1 ; A & B = 1 
A = 1 ; B = 2 ; A & B = 0 
A = 2 ; B = 1 ; A & B = 0 
A = 2 ; B = 2 ; A & B = 2 

IはAND操作から得た最大値は2であり、それはそう閾値3 2未満であります印刷すべき答えです。

これらのすべての入力から最大値を見つけて印刷する必要があります。私はlist、mapのようなデータ構造のいくつかの種類を使用している場合、私はより効率的にこの問題を解決することができ、このような問題に私の以前の経験から、このコードで

maxValue = 0 
n,k1 = input().strip().split(' ') 
n,k1 = [int(n),int(k1)] 
for j in range (1,n): 
    for k in range (j+1,n): 
     jkValue = j&k 
     if jkValue > maxValue and jkValue < k1: 
      maxValue = jkValue 
print(maxValue) 

をこの問題を解決しました。

データ構造を使用してこの問題を解決することは可能ですか、それとも最小限の複雑さを達成できましたか？それがより良くできたら、どうやって？

Answer 1

私は、のようにi&jを最大にする0<i<j<nを見つけることが問題であると仮定しています。

ビットごとに結果を構成することで答えを見つけることができます。上位ビットから始まって、前の手順で既に決定された最高ビットの2つの数値があるかどうかを調べ、現在のビットが両方とも範囲内にあり、ビット単位でビットがk未満であることを確認します。

これは、O（ログk）時間（正確には、O（ログk）の算術演算を実行します）で実行されます。

# max_and returns the max i&j subject to: 
# 0 < i < j < n and i&j < k. 
def max_and(n, k): 
    r = 0 
    b = 1 
    while b < k: 
     b <<= 1 
    while b: 
     # Can we set bit b in the result? 
     # We can't if r|b >= k. 
     # Otherwise, are there two numbers greater than or equal to r, 
     # and less than n, both with bit b set? 
     # The two smallest numbers greater than or equal to r with 
     # bit b set are r|b and ((r|b) + 1) | (r|b). We need only 
     # test the latter against n. 
     if (r | b) | ((r | b) + 1) < n and r|b < k: 
      r |= b 
     b >>= 1 
    return r 

ここで、単純で、明らかに正しいOで実行された溶液（N^2）時間、及び効率的なバージョンは、小さなn及びkについて同じ結果を生成するいくつかのテストです。

def max_and_slow(n, k): 
    return max(i&j for i in xrange(n) for j in xrange(i+1, n) if i&j < k) 

for n in xrange(2, 20): 
    for k in xrange(1, 20): 
     mas = max_and_slow(n, k) 
     ma = max_and(n, k) 
     if ma != mas: 
      print 'max_and(%d, %d) = %d, want %d' % (n, k, ma, mas)