On vous donne une large plage [a, b] où «a» et «b» peuvent généralement être compris entre 1 et 4 000 000 000 inclus. Vous devez trouver le XOR de tous les nombres dans la plage donnée.

Ce problème a été utilisé dans TopCoder SRM. J'ai vu l'une des solutions proposées dans le match et je ne suis pas en mesure de comprendre comment cela fonctionne.

Quelqu'un pourrait-il vous expliquer la solution gagnante:

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);
}

Voici getXor()la fonction réelle pour calculer le xor de tous les nombres dans la plage passée [a, b] et "f ()" est une fonction d'assistance.

C'est une solution assez intelligente - elle exploite le fait qu'il existe un modèle de résultats dans les XOR en cours d'exécution. La f()fonction calcule la course totale XOR à partir de [0, a]. Jetez un œil à ce tableau pour les nombres 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]

Où la première colonne est la représentation binaire, puis le résultat décimal et sa relation avec son index (a) dans la liste XOR. Cela se produit parce que tous les bits supérieurs s'annulent et les deux bits les plus bas effectuent un cycle tous les 4. Voilà comment arriver à cette petite table de recherche.

Maintenant, considérons une plage générale de [a, b]. Nous pouvons utiliser f()pour trouver le XOR pour [0, a-1] et [0, b]. Puisque toute valeur XOR'd avec elle-même est zéro, le f(a-1)juste annule toutes les valeurs dans l'exécution XOR inférieure à a, vous laissant avec le XOR de la plage [a, b].

Ajoutant à l'excellente réponse de FatalError, la ligne return f(b)^f(a-1);pourrait être mieux expliquée. En bref, c'est parce que XOR a ces merveilleuses propriétés:

• C'est associatif - Placez des crochets où vous le souhaitez
• C'est commutatif - cela signifie que vous pouvez déplacer les opérateurs (ils peuvent «faire la navette»)

Voici les deux en action:

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

• Il se renverse

Comme ça:

a ^ b = c
c ^ a = b

Ajouter et multiplier sont deux exemples d'autres opérateurs associatifs / commutatifs, mais ils ne s'inversent pas. Ok, alors, pourquoi ces propriétés sont-elles importantes? Eh bien, un moyen simple est de l'étendre à ce qu'il est vraiment, et vous pourrez ensuite voir ces propriétés à l'œuvre.

Tout d'abord, définissons ce que nous voulons et appelons-le n:

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

Si cela aide, pensez à XOR (^) comme s'il s'agissait d'un ajout.

Définissons également la fonction:

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

best supérieur à a, donc simplement en ajoutant en toute sécurité quelques crochets supplémentaires (ce que nous pouvons car c'est associatif), nous pouvons également dire ceci:

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

Ce qui se simplifie en:

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

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

Ensuite, nous utilisons cette propriété d'inversion et cette commutivité pour nous donner la ligne magique:

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

Si vous avez pensé à XOR comme un ajout, vous y auriez ajouté une soustraction. XOR est à XOR ce que ajouter c'est soustraire!

Comment puis-je trouver cela moi-même?

Souvenez-vous des propriétés des opérateurs logiques. Travaillez avec eux presque comme un ajout ou multipliez si cela aide. Il semble inhabituel que et (&), xor (^) et ou (|) soient associatifs, mais ils le sont!

Exécutez d'abord l'implémentation naïve, recherchez des modèles dans la sortie, puis commencez à trouver des règles qui confirment que le modèle est vrai. Simplifiez encore plus votre mise en œuvre et recommencez. C'est probablement la route empruntée par le créateur original, mise en évidence par le fait qu'elle n'est pas complètement optimale (c'est-à-dire utiliser une instruction switch plutôt qu'un tableau).

J'ai découvert que le code ci-dessous fonctionne également comme la solution donnée dans la question.

C'est peut-être peu optimisé, mais c'est exactement ce que j'ai obtenu en observant la répétition comme indiqué dans la réponse acceptée

Je voudrais connaître / comprendre la preuve mathématique derrière le code donné, comme expliqué dans la réponse de @Luke Briggs

Voici ce code 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];
}

J'ai résolu le problème de la récursivité. Je divise simplement l'ensemble de données en une partie presque égale pour chaque itération.

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;
}

Faites-moi savoir ce que vous pensez de la solution. Heureux de recevoir des commentaires d'amélioration. La solution proposée calcule le XOR en complexité 0 (log N).

Je vous remercie

Pour prendre en charge XOR de 0 à N, le code donné devait être modifié comme ci-dessous,

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

int getXor(int a, int b) {
    return f(b) ^ f(a);
}