Encontrar el XOR máximo de dos números en un intervalo: ¿podemos hacerlo mejor que cuadrático?

Supongamos que se nos dan dos números y y que queremos encontrar para l \ le i, \, j \ le r .$l$$r$$\max{(i\oplus j)}$$l\le i,\,j\le r$

El algoritmo ingenuo simplemente verifica todos los pares posibles; por ejemplo en ruby ​​tendríamos:

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

Tengo la sensación de que podemos hacerlo mejor que la cuadrática. ¿Hay un mejor algoritmo para este problema?

Podemos lograr tiempo de ejecución lineal en la longitud de la representación binaria de y :$n$$l$$r$

El prefijo en la representación binaria de y , que es el mismo para ambos valores, también es el mismo para todos los valores entre ellos. Entonces estos bits siempre serán .$p$$l$$r$$0$

Como , el bit que sigue a este prefijo será en y en . Además, los números y están en el intervalo.$r>l$$1$$r$$0$$l$$p10^{n-|p|-1}$$p01^{n-|p|-1}$

Entonces, el máximo que estamos buscando es .$0^{|p|}1^{n-|p|}$

Es posible hacerlo en tiempo .$\mathcal{O}(\log r)$

El XOR máximo posible de cualquiera de los dos enteros de un intervalo puede determinarse a partir de , suponiendo que sean enteros. Este valor es igual a , donde es el valor más pequeño de modo que es mayor que . $[l, r]$$l \oplus r$$l, r$$2^p-1$$p$$2^p$$l \oplus r$

Aquí hay una implementación en C ++

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

Necesitamos maximizar el xor entre 'pequeño' y 'alto'. Así que tomemos un ejemplo para entender esto.

5 xo 2 = 101 xo 010 primer caso: el bit MSB no está establecido para ambos valores en el rango. Si queremos maximizar esto, entonces lo que tenemos que hacer es mantener el MSB de 5 (100) como está y pensar maximizando los bits inferiores restantes. Como sabemos que los bits más bajos, todos serán uno para el caso cuando todo es 11, que no es más que 3, es decir, 2 ^ 2-1. Como el problema es hablar del rango entre 2 y 5, definitivamente tenemos 3 en el rango. Entonces, todo lo que tenemos que hacer es encontrar el conjunto MSB más alto en el mayor de 2 valores y agregar los 1 restantes para los bits más bajos.

segundo caso: en cuanto al caso cuando MSB está configurado para ambos valores en el rango que hace xor, definitivamente tendrá esos bits establecidos como 0 y necesitamos volver a los bits más bajos. Nuevamente para bits más bajos, necesitamos repetir la misma lógica que el primer caso. ejemplo: (10, 12) (1010, 1100) Como puede ver que ambos tienen MSB configurado como 1, entonces tenemos que volver a los bits inferiores, que son 010 y 100. Ahora este problema es el mismo que el primer caso.

Hay varias formas de codificar esto. Lo que hice fue hacer solo el xor entre 'pequeño' y 'alto' y eso eliminará el bit MSB si ambos 'pequeño' y 'alto' tienen el bit MSB establecido. En caso de que no sea así, conservará el bit MSB. Después de eso, estoy tratando de hacer que todos los bits más bajos sean 1 descubriendo la potencia máxima de 2 en la salida xored y restando de 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

Bueno, puedes usar el XOR de l y r para encontrar la respuesta.

Supongamos que l = 4 yr = 6.

l = 100, r = 110 (equivalentes binarios de estos números)

l⊕r = 0 10

Lo que esto significa es que el valor máximo que está buscando definitivamente tendrá su primer bit (MSB) como cero. (Piénselo, ¿es posible que su valor máximo tenga un 1 en el primer bit? Si fuera 01010 y 00101, el xor habría sido = 01 111, es decir, el valor máximo entre 01010 y 00101 definitivamente tendrá un 1 en su segundo bit desde la izquierda, no es posible obtener un 1 antes del segundo bit desde la izquierda, es decir, en el primer bit desde la izquierda)

Entonces, te quedan los 2 bits restantes para encontrar el máximo. Sabemos que el valor máximo posible cuando tenemos n bits con nosotros es = 2 ⁿ −1, por lo tanto, la respuesta en este caso será 2 ² -1 = 4-1 = 3.

Del ejemplo anterior, podemos hacer un algoritmo general para esto.

Paso 1. num = número de bits requeridos para representar max ( l , r )

Paso 2. res = l ⊕ r

Paso 3. pos = Posición del primer bit que se establece desde la izquierda en res (indexación basada en 0)

Paso 4. n = num - pos

Paso 5. ans = 2 ⁿ −1

Complejidad de tiempo = O (n)

Para cada dígito binario, hay 4 posibilidades: 1_y_1, 1_y_0, 0_y_1 o 0_y_0. Los posibles dígitos más bajos no hacen ninguna diferencia o desaparecen muy poco a la salida xor de elección del siguiente dígito. El mejor algoritmo posible es ignorar todos los dígitos inferiores y solo considerar los siguientes 2 disponibles, dadas las elecciones anteriores sobre dígitos superiores. Si esto es 1_and_1 o 0_and_0, la opción es clara, pero si este dígito es 1_and_0 vs 0_and_1 (que tienen un valor igual xor pero desigual) entonces recursivamente debería ser igual al algoritmo https://en.wikipedia.org/wiki/Edit_distance , lo que significa el peor caso de log cuadrado.

Para intervalos de 32 bits, acabo de encontrar esta O(1)solución en los editoriales de Hacker Rank. No tengo idea de cómo funciona, pero funciona. (Quizás alguien pueda explicar por qué funciona).

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

Fuente: https://www.hackerrank.com/challenges/maximizing-xor/editorial