Trouver le XOR de tous les nombres dans un intervalle donné

Question

On vous donne un grand intervalle [a,b] où "a" et "b" peuvent être compris entre 1 et 4 000 000 000 inclus. Vous devez trouver le XOR de tous les nombres de l'intervalle donné.

Ce problème a été utilisé dans TopCoder SRM. J'ai vu l'une des solutions soumises lors du match et je ne parviens pas à comprendre comment elle fonctionne.

Quelqu'un pourrait-il m'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);
}

Ici, getXor() est la fonction réelle pour calculer le xor de tous les nombres dans l'intervalle passé [a,b] et "f()" est une fonction d'aide.

Answer 1

Il s'agit d'une solution assez astucieuse, qui exploite le fait qu'il existe un modèle de résultats dans les XORs en cours. Le site f() calcule le parcours total XOR de [0, a]. Jetez un coup d'œil à ce tableau pour les nombres 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]

Où la première colonne est la représentation binaire, puis le résultat décimal et sa relation avec son indice (a) dans la liste XOR. Cela se produit parce que tous les bits supérieurs s'annulent et que les deux bits inférieurs font un cycle tous les 4. C'est ainsi que l'on arrive à cette petite table de conversion.

Maintenant, considérons un intervalle général de [a,b]. Nous pouvons utiliser f() pour trouver le XOR de [0,a-1] et [0,b]. Puisque n'importe quelle valeur XOR avec elle-même est zéro, la valeur f(a-1) annule juste toutes les valeurs dans le XOR moins de a ce qui vous donne le XOR de l'intervalle [a,b].

Answer 2

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

• C'est associatif - Placez les crochets où vous voulez
• 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 s'inverse

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, une façon simple de procéder est de l'étendre à ce qu'il est réellement, et vous pourrez alors 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 peut vous aider, pensez à XOR (^) comme si c'était une addition.

Définissons également la fonction :

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

b est supérieure à a Ainsi, en ajoutant quelques parenthèses supplémentaires (ce qui est possible car il s'agit d'une association), nous pouvons également dire ceci :

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

Ce qui se simplifie à :

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 la commutivité pour nous donner la ligne magique :

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

Si vous aviez pensé à XOR comme à une addition, vous auriez ajouté une soustraction ici. XOR est à XOR ce que l'addition est à la soustraction !

Comment je fais pour trouver ça moi-même ?

Rappelez-vous les propriétés des opérateurs logiques. Travaillez avec eux presque comme une addition ou une multiplication si cela vous aide. Il semble inhabituel que and (&), xor (^) et or (|) 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 implémentation et répétez. Il s'agit probablement de la voie choisie par le créateur original, ce qui est mis en évidence par le fait qu'elle n'est pas complètement optimale (c'est-à-dire qu'il faut utiliser une instruction switch plutôt qu'un tableau).

Answer 3

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

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

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

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

Answer 4

J'ai résolu le problème avec la récursion. Je divise simplement l'ensemble des 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 cette solution. Je suis heureux de recevoir des commentaires d'amélioration. La solution proposée calcule le XOR en 0(log N) complexité.

Merci.

Answer 5

Pour supporter le XOR de 0 à N, le code donné a dû ê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);
}