¿Por qué se puede simplificar el cálculo de XOR de valores consecutivos?

Question

Yo estaba tratando de calcular entero xor de 0..n. Puse el nombre de la función xored(n).

Tenga en cuenta que en los ejemplos de abajo ^ no significa poder, pero entero xor (como en C o Java lenguaje)

Así, xored(0) = 0, xored(1) = 0 ^ 1, xored(2) = 0 ^ 1 ^ 2, xored(3) = 0 ^ 1 ^ 2 ^ 3, etc...
O, si usted prefiere definición recursiva:
xored(0) = 0
xored(n) = n ^ xored(n-1)

En primer lugar, he creado un ingenuo aplicación que que se repite a través de los valores y xors ellos juntos.

Entonces, me di cuenta de una cosa curiosa. Me di cuenta de un patrón con mis resultados.

Todo lo que necesitas hacer es calcular n modulo 4 (m), entonces:
si m = 0, xored(n) = n
si m = 1, xored(n) = 1
si m = 2, xored(n) = n + 1
si m = 3, xored(n) = 0

Mi pregunta es. Por qué funciona? Cómo puede ser demostrado matemáticamente? No soy bueno en demostrar teoremas...

Answer 1

Creo que algunas de las pruebas se basan en observaciones y la generalización de los patrones. Ayuda en muchos lugares donde no se puede probar cosas usando un teorema, pero las cosas pueden ser clasificados usando observaciones.

Euler Poliédrica Fórmula $ V(vertices) + F(faces) - E(edges) = 2$ es un ejemplo. Euler no dar la prueba (aunque fue demostrado de muchas maneras después), este resultado inspirado grandes avances.

EDIT: Hay un montón de hilos con la misma pregunta y todos resuelto mediante la mera observación. Uno de los hilos se pueden encontrar aquí.