XOR of Consecutive Integers
Published:
Preliminaries
Let $A \oplus B$ be the bitwise XOR of $A$ and $B$. For each pair of bits, the table below shows the result of XOR.
\[\begin{array}{|c|c|c|} \hline A & B & A \oplus B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \hline \end{array}\]This means that for any $A$, $A \oplus A = 0$ and $A \oplus 0 = A$. In the context of bitwise operations, a number is the inverse of itself and 0 is the identity element.
Properties
Theorem 1 Let $A$ be an even natural. Then, $A \oplus (A+1) = 1$.
Proof Let $A$ be a natural Then, $2\cdot A$ is $A$ with a 0 added to the right. Similarly, $2\cdot A + 1$ is $A$ with a 1 added to the right. Taking the XOR of $2\cdot A$ and $2\cdot A + 1$ gives us
\[\begin{aligned} 2\cdot A \oplus (2\cdot A + 1) &= A0_2 \oplus A1_2 = 0\cdots 0 1 = 1. \end{aligned}\]Thus, we have shown that the XOR of an even number and the next odd number is 1.
From here, we can extend this property to the XOR of 4 consecutive numbers.
Theorem 2 Let $A$ be an even natural. Then,
\[\begin{aligned} A \oplus (A+1) \oplus (A+2) \oplus (A+3) = 0 \end{aligned}\]Proof By the previous theorem,
\[\begin{aligned} (A+0) \oplus (A+1) &= 1 \\ (A+2) \oplus (A+3) &= 1 \end{aligned}\]Then, $A \oplus (A+1) \oplus (A+2) \oplus (A+3) = 1 \oplus 1 = 0$.
Theorem 3 Let $A$ be an odd natural. Then, $A \oplus (A+1) = 2^n - 1$ where $n$ is some positive integer as described below.
Proof Since $A$ is odd, it must end in a 1 in binary. Then, $A+1$ will be $A$ with the rightmost 0 flipped to a 1 and all the bits to the right of it flipped to 0. Let $n$ be the position of such a bit. The XOR of $A$ and $A+1$ of the bits before the $n$th bit will be 0 because they are the same. The XOR of the $n$th bit will be 1 because they are different. The XOR of the bits after the $n$th bit will be 1 because by definition of $n$, the bits in $A$ must all be 1 and the bits in $A+1$ must all be 0. Thus, the XOR of $A$ and $A+1$ will be $2^n - 1$, or simply n 1s in binary.
Theorem 4 Let $A$ be an odd natural. Then,
\[\begin{aligned} A \oplus (A+1) \oplus (A+2) \oplus (A+3) = 2^n - 4 \end{aligned}\]where $n$ is some positive integer as described below.
Proof By the previous theorem,
\[\begin{aligned} (A+1) \oplus (A+2) \oplus (A+3) \oplus (A+4) &= 0 \end{aligned}\]Let $X$ be the XOR of the 4 consecutive numbers. Then,
\[\begin{aligned} X &= A \oplus (A+1) \oplus (A+2) \oplus (A+3) \\ A \oplus (A+4) \oplus X &= A \oplus A \oplus (A+1) \oplus (A+2) \oplus (A+3) \oplus (A+4) \\ A \oplus (A+4) \oplus X &= 0 \\ X &= A \oplus (A+4) \end{aligned}\]The proof is similar to the proof of Theorem 3, with only difference being that $n$ is the position of the rightmost $0$ in $A$ ignoring the last 2 bits.
Definition Let $f(A): \mathbb{N}_0 \to \mathbb{N}_0$ be a function that returns the XOR of all numbers from $0$ to $A$ inclusive. That is, $f(A) = 0 \oplus 1 \oplus 2 \oplus \cdots \oplus A$.
Corollary Let $A$ and $B$ be numbers such that $A < B$. Then, $f(A-1) \oplus f(B) = A \oplus (A+1) \oplus \cdots \oplus B$.
Generalization
Theorem 5 Let $A$ be a natural. Then,
\[\begin{aligned} f(A) &= \begin{cases} A & A \equiv 0 \pmod 4 \\ 1 & A \equiv 1 \pmod 4 \\ A+1 & A \equiv 2 \pmod 4 \\ 0 & A \equiv 3 \pmod 4 \\ \end{cases} \end{aligned}\]Proof The proof by cases is trivial with the theorems established above.