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

Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .$l$$r$$\max{(i\oplus j)}$$l\le i,\,j\le r$

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?

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

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ć .$p$$l$$r$$0$

Ponieważ , bit po tej prefiks będzie z i do . Ponadto liczby i znajdują się w przedziale.$r>l$$1$$r$$0$$l$$p10^{n-|p|-1}$$p01^{n-|p|-1}$

Zatem maksimum, którego szukamy, to .$0^{|p|}1^{n-|p|}$

Można to zrobić w czasie .$\mathcal{O}(\log r)$

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]$$l \oplus r$$l, r$p 2 p l ⊕ $2^p-1$$p$$2^p$$l \oplus r$

Oto implementacja w C ++

int maximumXOR(int l, int r) {
    int q = l ^ r, a = 1;
    while(q){
        q /= 2;
        a <<= 1;
    }
    return --a;
}

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

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 ² -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 = l ⊕ r

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)

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.

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