Você recebe um grande intervalo [a, b], onde 'a' e 'b' podem estar normalmente entre 1 e 4.000.000.000 inclusive. Você tem que descobrir o XOR de todos os números no intervalo fornecido.

Este problema foi usado no TopCoder SRM. Eu vi uma das soluções apresentadas na partida e não estou conseguindo entender como está funcionando.

Alguém poderia ajudar a explicar a solução vencedora:

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

Aqui, getXor()está a função real para calcular o xor de todos os números no intervalo passado [a, b] e "f ()" é uma função auxiliar.

Esta é uma solução muito inteligente - ela explora o fato de que há um padrão de resultados nos XORs em execução. A f()função calcula a execução total de XOR de [0, a]. Dê uma olhada nesta tabela 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]

Onde a primeira coluna é a representação binária e então o resultado decimal e sua relação com seu índice (a) na lista XOR. Isso acontece porque todos os bits superiores se cancelam e os dois bits mais baixos dão um ciclo a cada 4. Então, é assim que se chega àquela pequena tabela de pesquisa.

Agora, considere uma faixa geral de [a, b]. Podemos usar f()para encontrar o XOR para [0, a-1] e [0, b]. Uma vez que qualquer valor XOR com ele mesmo é zero, o f(a-1)apenas cancela todos os valores no XOR executado menos que a, deixando você com o XOR do intervalo [a, b].

Somando-se à ótima resposta de FatalError, a linha return f(b)^f(a-1);poderia ser explicada melhor. Resumindo, é porque o XOR tem essas propriedades maravilhosas:

• É associativo - coloque colchetes onde quiser
• É comutativo - isso significa que você pode movimentar os operadores (eles podem "se deslocar")

Ambos estão em ação:

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

• Se inverte

Como isso:

a ^ b = c
c ^ a = b

Adicionar e multiplicar são dois exemplos de outros operadores associativos / comutativos, mas não se revertem. Ok, então, por que essas propriedades são importantes? Bem, um caminho simples é expandi-lo para o que realmente é, e então você poderá ver essas propriedades em funcionamento.

Primeiro, vamos definir o que queremos e chamá-lo de n:

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

Se ajudar, pense em XOR (^) como se fosse um acréscimo.

Vamos também definir a função:

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

bé maior que a, então, apenas colocando com segurança alguns colchetes extras (o que podemos porque é associativo), também podemos dizer o seguinte:

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

O que simplifica para:

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

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

Em seguida, usamos essa propriedade de reversão e comutividade para nos dar a linha mágica:

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

Se você tem pensado em XOR como um acréscimo, você teria adicionado um subtrato ali. XOR é para XOR o que adicionar é subtrair!

Como faço isso sozinho?

Lembre-se das propriedades dos operadores lógicos. Trabalhe com eles quase como adicionar ou multiplicar se ajudar. Parece incomum que and (&), xor (^) e or (|) sejam associativos, mas são!

Execute primeiro a implementação ingênua, procure padrões na saída e, em seguida, comece a encontrar regras que confirmem que o padrão é verdadeiro. Simplifique sua implementação ainda mais e repita. Este é provavelmente o caminho que o criador original seguiu, destacado pelo fato de que não é totalmente ideal (ou seja, use uma instrução switch em vez de um array).

Descobri que o código abaixo também está funcionando como a solução dada na pergunta.

Pode ser que isso seja um pouco otimizado, mas é apenas o que eu obtive observando a repetição como dada na resposta aceita,

Gostaria de saber / compreender a prova matemática por trás do código fornecido, conforme explicado na resposta de @Luke Briggs

Aqui está o 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];
}

Resolvi o problema da recursão. Eu simplesmente divido o conjunto de dados em uma parte quase igual para cada iteração.

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

Deixe-me saber sua opinião sobre a solução. Fico feliz em receber feedbacks de melhoria. A solução proposta calcula o XOR em complexidade 0 (log N).

Obrigado

Para suportar XOR de 0 a N, o código fornecido precisava ser modificado conforme abaixo,

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