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

Pour aller encore plus loin dans la réponse de FatalError, il est possible de prouver (par induction) que le schéma observé dans f() se déclenchera tous les 4 numéros.

Nous essayons de prouver que pour chaque entier k >= 0 ,

f(4k + 1) = 1
f(4k + 2) = 4k + 3
f(4k + 3) = 0
f(4k + 4) = 4k + 4

où f(n) est 1 ^ 2 ^ ... ^ n .

Comme notre cas de base on peut calculer à la main que

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

Pour notre pas inductif supposons que ces équations soient vraies jusqu'à un nombre entier particulier. 4x (c'est-à-dire f(4x) = 4x ). Nous voulons montrer que nos équations sont vraies pour 4x + 1 , 4x + 2 , 4x + 3 et 4x + 4 .

Pour aider à écrire et à visualiser la preuve, nous pouvons laisser b(x) désigne la représentation binaire (base 2) de la chaîne de caractères de x par exemple
b(7) = '111' , b(9) = '1001' .

et

b(4x)     = 'b(x)00'
b(4x + 1) = 'b(x)01'
b(4x + 2) = 'b(x)10'
b(4x + 3) = 'b(x)11'

Voici l'étape inductive :

Assume: f(4x) = 4x = 'b(x)00'
Then:

f(4x + 1) = f(4x)    ^ (4x + 1)  // by definition
          = f(4x)    ^ 'b(x)01'  // by definition
          = 'b(x)00' ^ 'b(x)01'  // from assumption
          = '01'                 // as b(x) ^ b(x) = 0

f(4x + 2) = f(4x + 1) ^ (4x + 2)
          = f(4x + 1) ^ 'b(x)10'       
          = '01'      ^ 'b(x)10'
          = 'b(x)11'             // this is 4x + 3

f(4x + 3) = f(4x + 2) ^ (4x + 3)
          = f(4x + 2) ^ 'b(x)11' 
          = 'b(x)11'  ^ 'b(x)11'
          = '00'

For the last case, we don't use binary strings, 
since we don't know what b(4x + 4) is.

f(4x + 4) = f(4x + 3) ^ (4x + 4)
          = 0         ^ (4x + 4)
          = 4x + 4

Donc le schéma se répète pour les quatre numéros suivants. 4x ce qui complète la preuve.