algorithm - muse - Encuentra XOR de todos los números en un rango determinado

algorithms book

Question

Se le otorga un rango amplio [a, b] donde ''a'' y ''b'' pueden ser típicamente entre 1 y 4,000,000,000 inclusive. Debes averiguar el XOR de todos los números en el rango dado.

Este problema se usó en TopCoder SRM. Vi una de las soluciones presentadas en el partido y no puedo entender cómo funciona.

¿Alguien podría ayudar a explicar la solución ganadora?

long long f(long long a) {
     long long res[] = {a,1,a+1,0};
     return res[a%4];
}

long long getXor(long long a, long long b) {
     return f(b)^f(a-1);
}

Aquí, getXor() es la función real para calcular el xor de todos los números en el rango pasado [a, b] y "f ()" es una función auxiliar.

Answer 1

Añadiendo a la gran respuesta de FatalError, la línea return f(b)^f(a-1); podría explicarse mejor. En resumen, es porque XOR tiene estas maravillosas propiedades:

• Es asociativo : coloca corchetes donde quieras
• Es conmutativo , eso significa que puedes mover a los operadores (pueden "conmutar")

Aquí están los dos en acción:

(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c

• Se invierte

Me gusta esto:

a ^ b = c
c ^ a = b

Agregar y multiplicar son dos ejemplos de otros operadores asociativos / conmutativos, pero no se invierten. Ok, entonces, ¿por qué son estas propiedades importantes? Bueno, una ruta simple es expandirlo a lo que realmente es, y luego puede ver estas propiedades en el trabajo.

Primero, definamos lo que queremos y llámenlo n:

n      = (a ^ a+1 ^ a+2 .. ^ b)

Si es útil, piense en XOR (^) como si fuera un complemento.

Vamos a definir la función:

f(b)   = 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ b

b es mayor que a , así que con solo dejar caer unos pocos corchetes adicionales (lo cual podemos hacer porque es asociativo), también podemos decir esto:

f(b)   = ( 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ (a-1) ) ^ (a ^ a+1 ^ a+2 .. ^ b)

Lo que simplifica a:

f(b)   = f(a-1) ^ (a ^ a+1 ^ a+2 .. ^ b)

f(b)   = f(a-1) ^ n

A continuación, usamos esa propiedad de reversión y commutividad para darnos la línea mágica:

n      = f(b) ^ f(a-1)

Si has estado pensando en XOR como un complemento, habrías soltado un restar allí. XOR es para XOR lo que agregar es restar

¿Cómo se me ocurre esto?

Recuerde las propiedades de los operadores lógicos. Trabaja con ellos casi como agregar o multiplicar si ayuda. Se siente inusual que y (&), xor (^) y o (|) son asociativos, ¡pero lo son!

Ejecute primero la implementación ingenua, busque patrones en la salida y luego comience a encontrar reglas que confirmen que el patrón es verdadero. Simplifique su implementación aún más y repita. Esta es probablemente la ruta que tomó el creador original, resaltada por el hecho de que no es completamente óptima (es decir, usa una declaración de cambio en lugar de una matriz).

Answer 2

Descubrí que el código siguiente también funciona como la solución dada en la pregunta.

Puede ser que esto esté poco optimizado, pero es solo lo que obtuve al observar la repetición como se da en la respuesta aceptada,

Me gustaría saber / entender la prueba matemática detrás del código dado, como se explica en la respuesta de @Luke Briggs

Aquí está ese código JAVA

public int findXORofRange(int m, int n) {
    int[] patternTracker;

    if(m % 2 == 0)
        patternTracker = new int[] {n, 1, n^1, 0};
    else
        patternTracker = new int[] {m, m^n, m-1, (m-1)^n};

    return patternTracker[(n-m) % 4];
}

Answer 3

Esta es una solución bastante inteligente: explota el hecho de que hay un patrón de resultados en los XORs en ejecución. La función f() calcula la ejecución total de XOR desde [0, a]. Eche un vistazo a esta tabla para números de 4 bits:

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

Donde la primera columna es la representación binaria y luego el resultado decimal y su relación con su índice (a) en la lista XOR. Esto sucede porque todos los bits superiores se cancelan y los dos bits más bajos ciclo cada 4. Entonces, así es como llegar a esa pequeña tabla de búsqueda.

Ahora, considere para un rango general de [a, b]. Podemos usar f() para encontrar el XOR para [0, a-1] y [0, b]. Como cualquier valor XOR''d consigo mismo es cero, f(a-1) simplemente cancela todos los valores en la ejecución XOR menor que a , dejándote con el XOR del rango [a, b].

Answer 4

He resuelto el problema con la recursividad. Simplemente divido el conjunto de datos en una parte casi igual para cada iteración.

public int recursion(int M, int N) {
    if (N - M == 1) {
        return M ^ N;
    } else {
        int pivot = this.calculatePivot(M, N);
        if (pivot + 1 == N) {
            return this.recursion(M, pivot) ^ N;
        } else {
            return this.recursion(M, pivot) ^ this.recursion(pivot + 1, N);
        }
    }
}
public int calculatePivot(int M, int N) {
    return (M + N) / 2;
}

Déjame saber tus pensamientos sobre la solución. Feliz de obtener mejoras en la retroalimentación. La solución propuesta calcula el XOR en complejidad 0 (log N).

Gracias