Finden Sie das Maximum von a & b in einer Menge s = {1, 2, ... n} kleiner als ein bestimmter Wert k

Question

Ich spielte ein wenig mit der Python-Sprache, um ein Tutorial über HackerRank zu lösen, hier verfügbar: https://www.hackerrank.com/challenges/30-bitwise-and

der Kern der Herausforderung ist es, die maximal a & b zu finden, wo a, b ∈ s, s der Satz wie definiert ist: s = {1, 2, ... n} wo a < b. Eine weitere Bedingung ist, dass a & b < k2 <= k <= n ist. Die angegebenen Eingänge sind n und k.

Ich schaffte es, eine O(n^2) und O(n) Lösungen zu haben, aber ich habe Schwierigkeiten, mit einer O(1) Lösung zu kommen.

Zum Beispiel ist hier unter einem Dummy O(n^2) Lösung:

def max_and(n, k): 
    if (n < k) or (k < 2): 
     raise ValueError() 
    else: 
     res = (0, 1, 0) 
     for a in range(n + 1): 
      for b in range(n + 1): 
       if a < b: 
        temp = a & b 
        if res[2] < temp < k: 
         res = (a, b, temp) 
     return res 


for n in range(2, 10): 
    print(["(n = {}, k = {}) = ".format(n, k) + str(max_and(n, k)) for k in range(2, n + 1)]) 

Ich bemerkte, dass die Antwort ist immer k - 1 oder k - 2, die für mich Sinn macht.

Ich denke, die Idee ist, dass das Maximum von a & b Einschränkung ist weniger als k und da die logische und Operator kann keine Zahl größer als b ausgeben.

Einige Leute auf HackerRank kam mit einem O (1) Lösung, aber ich habe nicht wirklich, wie es funktioniert tatsächlich:

a = k - 1 
b = (~a) & -(~a) 

if (a | b) > n: 
    print (a - 1) 
else: 
    print (a) 

Besonders warum b = (~a) & -(~a)

ich meine ich den Punkt, dass Es kann als

Answer 1

Lassen Sie j = k - 1, und lassen Sie unset_bit die niedrigste Potenz von zwei sein, so dass (j & unset_bit) == 0.

Wenn (j | unset_bit) <= n, dann wählen wir a = j und b = j | unset_bit für den optimalen Wert von (a & b) == j.

Wenn (j | unset_bit) > n, dann nicht möglich Auswahl an a und b wird uns (a & b) == j geben. Wir haben einfach nicht zwei Zahlen, um mit allen erforderlichen Bits auszuwählen. Da uns sogar (j | unset_bit) == j+1 <= n gegeben hätte, müssen wir j ungerade haben. Dann die Kommissionierung a = j - 1 und b = j gibt uns (a & b) == j - 1, den höchstmöglichen Wert.

---

Der Code, den Sie auf HackerRank gesehen haben, implementiert diese Idee. In dem Code, den Sie gefunden haben, ist ihr a unser j, und ihr b ist unser unset_bit, der durch einige Bitdrehtricks berechnet wird. Ich habe j und unset_bit anstelle von a und b verwendet, weil Sie diese Buchstaben bereits für andere Bedeutungen benutzt haben.