Нахождение максимального XOR двух чисел в интервале: можем ли мы сделать лучше, чем квадратичное?

Предположим, нам даны два числа и и мы хотим найти для .$l$$r$$\max{(i\oplus j)}$$l\le i,\,j\le r$

Наивный алгоритм просто проверяет все возможные пары; например, в ruby ​​у нас будет:

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

Я чувствую, что мы можем сделать лучше, чем квадратичные. Есть ли лучший алгоритм для этой проблемы?

Мы можем достичь линейного времени выполнения по длине двоичного представления и :$n$$l$$r$

Префикс в двоичном представлении и , одинаковый для обоих значений, также одинаков для всех значений между ними. Таким образом, эти биты всегда будут .$p$$l$$r$$0$

Поскольку , бит, следующий за этим префиксом, будет в и в . Кроме того, числа и находятся в интервале.$r>l$$1$$r$$0$$l$$p10^{n-|p|-1}$$p01^{n-|p|-1}$

Таким образом, максимум, который мы ищем, равен .$0^{|p|}1^{n-|p|}$

Это можно сделать за время .$\mathcal{O}(\log r)$

Максимально возможное XOR любых двух целых чисел из интервала может быть определено из l ⊕ r , предполагая, что l , r - целые числа. Это значение равно 2 p - 1 , где p - наименьшее значение, такое, что 2 p больше, чем l ⊕ r . $[l, r]$$l \oplus r$$l, r$$2^p-1$$p$$2^p$$l \oplus r$

Вот реализация в C ++

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

Нам нужно максимизировать xor между «маленьким» и «высоким». Итак, давайте рассмотрим пример, чтобы понять это.

5 xor 2 = 101 xor 010 первый случай: бит MSB не установлен для обоих значений в диапазоне. Если мы хотим максимизировать это, то нам нужно сохранить MSB равным 5 (100) и подумать о максимизация оставшихся младших битов. Поскольку мы знаем, что младшие биты все будут едины для случая, когда все равно 11, что является ничем иным, как 3, т.е. 2 ^ 2-1. Поскольку проблема говорит о диапазоне от 2 до 5, мы определенно имеем 3 в диапазоне. Таким образом, все, что нам нужно сделать, это найти самый высокий набор старших битов из двух больших значений и добавить оставшиеся 1 для младших битов.

Второй случай: Что касается случая, когда MSB установлен для обоих значений в диапазоне, при выполнении xor эти биты определенно будут установлены в 0, и нам нужно вернуться к младшим битам. Опять же для младших битов нам нужно повторить ту же логику, что и в первом случае. пример: (10, 12) (1010, 1100) Как вы можете видеть, что оба MSB установлены в 1, тогда мы должны вернуться к младшим битам, которые равны 010 и 100. Теперь эта проблема такая же, как в первом случае.

Есть несколько способов закодировать это. Я просто сделал xor между «small» и «high», и это удалит бит MSB, если для «small» и «high» установлен бит MSB. Если это не так, тогда он сохранит бит MSB. После этого я пытаюсь сделать все младшие биты 1, определив максимальную мощность 2 в xored выходе и вычитая из 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

Ну, вы можете использовать XOR l и r, чтобы найти ответ.

Предположим, что l = 4 и r = 6.

l = 100, r = 110 (двоичные эквиваленты этих чисел)

l⊕r = 0 10

Это означает, что максимальное значение, которое вы ищете, будет иметь первый бит (MSB) в качестве нуля. (Подумайте об этом, возможно ли даже, чтобы у вашего максимального значения была 1 в первом бите вместо этого? Если бы это было 01010 и 00101, xor был бы = 01 111, т.е. максимальное значение между 01010 и 00101 определенно будет иметь 1 в их второй бит слева, это не возможно , чтобы получить 1 до второго бита слева , т.е. в первый бит слева)

Итак, у вас осталось 2 оставшихся бита, чтобы найти максимум. Мы знаем, что максимально возможное значение, когда у нас есть n битов, равно = 2 ⁿ -1, поэтому ответ в этом случае будет 2 ² -1 = 4-1 = 3.

Из приведенного выше примера мы можем сделать общий алгоритм для этого.

Шаг 1. num = количество битов, необходимых для представления max ( l , r )

Шаг 2. res = l ⊕ r

Шаг 3. pos = Позиция первого бита, установленного слева в res (индексирование на основе 0)

Шаг 4. n = num - pos

Шаг 5. ans = 2 ^{n −} 1

Временная сложность = O (n)

Для каждой двоичной цифры существует 4 варианта: 1_and_1, 1_and_0, 0_and_1 или 0_and_0. Возможные младшие цифры не имеют значения или исчезают из логарифмически малой разницы для выхода xor выбора следующей цифры. Наилучший возможный алгоритм - игнорировать все младшие цифры и рассматривать только следующие 2 доступные, учитывая более ранний выбор старших цифр. Если это 1_and_1 или 0_and_0, выбор очевиден, но если эта цифра равна 1_and_0 против 0_and_1 (которые имеют равные xor, но неравное значение), то рекурсивно она должна равняться алгоритму https://en.wikipedia.org/wiki/Edit_distance , что означает наихудший случай бревна в квадрате.

Для 32-битных интервалов я только что натолкнулся на это O(1)решение в редакционных статьях Hacker Rank. Я понятия не имею, как это работает, но это работает. (Возможно, кто-то может объяснить, почему это работает.)

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

Источник: https://www.hackerrank.com/challenges/maximizing-xor/editorial