Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?

14

Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lrmax(ij)li,jr

Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy:

def max_xor(l, r)
  max = 0

  (l..r).each do |i|
    (i..r).each do |j|
      if (i ^ j > max)
        max = i ^ j
      end
    end
  end

  max
end

Mam poczucie , że możemy zrobić lepiej niż kwadratowy. Czy istnieje lepszy algorytm dla tego problemu?

Jacopo Notarstefano
źródło
Powinieneś pozwolić jbiegać i+1..ri ibiegać, l...r-1by być precyzyjnym.
Ahmet Alp Balkan,

Odpowiedzi:

20

Możemy osiągnąć liniowy czas działania na długości reprezentacji binarnej i :nlr

Przedrostek binarnej reprezentacji i , który jest taki sam dla obu wartości, jest również taki sam dla wszystkich wartości między nimi. Więc te bity zawsze będą wynosić .plr0

Ponieważ , bit po tej prefiks będzie z i do . Ponadto liczby i znajdują się w przedziale.r>l1r0lp10n|p|1p01n|p|1

Zatem maksimum, którego szukamy, to .0|p|1n|p|

FrankW
źródło
1
To było łatwe! Chyba powinienem przemyśleć ten problem.
Jacopo Notarstefano
Autor wątku poprosił o „lepszy niż kwadratowy w liczbach”. Jest to liniowy rozmiar liczb, więc jest logarytmiczny w samych liczbach.
gnasher729,
18

Można to zrobić w czasie .O(logr)

Maksymalne możliwe XOR dowolnych dwóch liczb całkowitych z przedziału można określić na podstawie l r , zakładając, że l , r są liczbami całkowitymi. Ta wartość jest równa , gdzie jest najmniejszą wartością, tak że jest większe niż . [l,r]lrl,rp 2 p l r2p1p2plr

Oto implementacja w C ++

int maximumXOR(int l, int r) {
    int q = l ^ r, a = 1;
    while(q){
        q /= 2;
        a <<= 1;
    }
    return --a;
}
ysb.4
źródło
Czy możesz wyjaśnić uzasadnienie tego algorytmu?
sk1pro99
Ten film może ci pomóc: youtube.com/watch?v=3j-ok4gMjXU
Jack Kinsella
0

Musimy zmaksymalizować xor między „małym” a „wysokim”. Weźmy więc przykład, aby to zrozumieć.

5 xor 2 = 101 xor 010 pierwszy przypadek: bit MSB nie jest ustawiony dla obu wartości w zakresie.Jeśli chcesz to zmaksymalizować, musimy zachować MSB na poziomie 5 (100) i zastanowić się nad maksymalizacja pozostałych niższych bitów. Jak wiemy, niższe bity wszystkie będą jednym dla przypadku, gdy wszystko ma wartość 11, co jest niczym innym jak 3, tj. 2 ^ 2-1. Ponieważ problem dotyczy zakresu od 2 do 5, z pewnością mamy 3 w zakresie. Więc wszystko, co musimy zrobić, to znaleźć najwyższy zestaw MSB w większej z 2 wartości i dodać pozostałe 1 dla niższych bitów.

Drugi przypadek: tak jak w przypadku, gdy MSB jest ustawione dla obu wartości w zakresie wykonującym xor, z pewnością mają te bity ustawione na 0 i musimy wrócić do niższych bitów. Ponownie dla mniejszych bitów musimy powtórzyć tę samą logikę jak w pierwszym przypadku. przykład: (10, 12) (1010, 1100) Jak widać, oba mają ustawiony MSB na 1, więc musimy wrócić do niższych bitów, czyli 010 i 100. Teraz ten problem jest taki sam jak w pierwszym przypadku.

Istnieje kilka sposobów na zakodowanie tego. Zrobiłem tylko xor między „małym” a „wysokim”, a to usunie bit MSB, jeśli zarówno „mały”, jak i „wysoki” mają ustawiony bit MSB. Jeśli nie jest to przypadek, zachowa bit MSB. Następnie staram się uzyskać wszystkie niższe bity 1, znajdując maksymalną moc 2 na wyjściu xored i odejmując od 1.

def range_xor_max(small, high):
  if small == high:
    return 0
  xor = small ^ high
  #how many power of 2 is present
  how_many_power_of_2 = math.log(xor, 2)
  #we need to make all one's below the highest set bit
  return 2**int(math.floor(how_many_power_of_2)+1) - 1
Noman pouigt
źródło
0

Cóż, możesz użyć XOR l i r, aby znaleźć odpowiedź.

Załóżmy, że l = 4 ir = 6.

l = 100, r = 110 (binarne odpowiedniki tych liczb)

l⊕r = 0 10

Oznacza to, że maksymalna wartość, której szukasz, na pewno będzie miała swój pierwszy bit (MSB) jako zero. (Pomyśl o tym, czy w ogóle twoja maksymalna wartość może mieć 1 w pierwszym bicie? Gdyby to było 01010 i 00101, xor byłby = 01 111, tzn. Maksymalna wartość między 01010 a 00101 na pewno miałaby 1 w swoim drugim bitem od lewej, to nie jest możliwe, aby uzyskać 1 przed drugim bitem od lewej czyli w pierwszym bitem od lewej)

Pozostały Ci pozostałe 2 bity, aby znaleźć maksimum. Wiemy, że maksymalna możliwa wartość, gdy mamy z sobą n bitów, wynosi = 2 n- 1, dlatego odpowiedź w tym przypadku będzie wynosić 2 2 -1 = 4-1 = 3.

Z powyższego przykładu możemy stworzyć ogólny algorytm do tego.

Krok 1. num = liczba bitów wymagana do przedstawienia max ( l , r )

Krok 2. res = lr

Krok 3. pos = Pozycja pierwszego bitu ustawiana od lewej w res (indeksowanie 0)

Etap 4. n = num - Pos

Krok 5. ans = 2 n- 1

Złożoność czasu = O (n)

UjjwalAyyangar
źródło
-1

Dla każdej cyfry binarnej istnieją 4 możliwości: 1_i_1, 1_i_0, 0_i_1 lub 0_i_0. Możliwe niższe cyfry nie powodują żadnej lub znikają z logarytmicznie niewielkiej różnicy w stosunku do wyjścia xor wybranej następnej cyfry. Najlepszym możliwym algorytmem jest zignorowanie wszystkich niższych cyfr i rozważenie tylko następnych 2 dostępnych, biorąc pod uwagę wcześniejsze wybory dotyczące wyższych cyfr. Jeśli jest to 1_i_1 lub 0_i_0, wybór jest jasny, ale jeśli ta cyfra to 1_i_0 w porównaniu do 0_i_1 (które mają równe xor, ale nierówną wartość), to rekurencyjnie powinna być równa algorytmowi https://en.wikipedia.org/wiki/Edit_distance , co oznacza najgorszy przypadek logarytmicznego kwadratu.

Ben Rayfield
źródło
1
Nie jestem pewien, co rozumiesz przez „niższą cyfrę”, „log-znikający mały” lub „to ... co oznacza najgorszy przypadek logarytmicznego kwadratu”. Czy możesz to wyjaśnić?
David Richerby
-1

Przez 32-bitowe interwały natknąłem się na to O(1)rozwiązanie w artykułach redakcyjnych Hacker Rank. Nie mam pojęcia, jak to działa, ale działa. (Być może ktoś może wyjaśnić, dlaczego to działa.)

def max_xor(L,R):
  v = L^R
  v |= v >> 1
  v |= v >> 2
  v |= v >> 4
  v |= v >> 8
  v |= v >> 16
  return b

Źródło: https://www.hackerrank.com/challenges/maximizing-xor/editorial

Ahmet Alp Balkan
źródło
2
Jak twoja odpowiedź (po korekcie) różni się od ysb.4 (poza tym, że wyjaśnił, co się dzieje)? Co „zwrot b” robi z zadeklarowanym „b”? Przepraszamy, ale nie mogę uzyskać dostępu do podanego linku.
Zły