The XOR Sum Trick
If you need to calculate
1 ^ 2 ^ 3 ^ ... ^ N(the bitwise XOR sum of all integers from to ), you do not need an loop. Thanks to a repeating mathematical pattern in binary representations, this can be solved in pure constant time.
Explanation
- If we write down the XOR sum from to and observe the results, a perfect repeating sequence of length 4 emerges.
- Let be the XOR sum of .
| N | Sequence | Binary | Result | Pattern |
|---|---|---|---|---|
| 1 | 1 | 001 | 1 | |
| 2 | 1 ^ 2 | 011 | 3 | |
| 3 | 1 ^ 2 ^ 3 | 000 | 0 | |
| 4 | 1 ^ 2 ^ 3 ^ 4 | 100 | 4 | |
| 5 | ... ^ 5 | 001 | 1 | |
| 6 | ... ^ 6 | 111 | 7 | |
| 7 | ... ^ 7 | 000 | 0 | |
| 8 | ... ^ 8 | 1000 | 8 |
- The Pattern:
Based on the remainder of :
- If
N % 4 == 0, then - If
N % 4 == 1, then - If
N % 4 == 2, then - If
N % 4 == 3, then
- If
Implementation
def compute_xor_1_to_n(n):
remainder = n % 4
if remainder == 0:
return n
elif remainder == 1:
return 1
elif remainder == 2:
return n + 1
else:
return 0
print(f"XOR Sum 1 to 100: {compute_xor_1_to_n(100)}")#include <iostream>
int computeXor1ToN(int n) {
switch(n % 4) {
case 0: return n;
case 1: return 1;
case 2: return n + 1;
case 3: return 0;
}
return 0; // Fallback, never reached
}
int main() {
std::cout << "XOR Sum 1 to 100: " << computeXor1ToN(100) << "\n";
return 0;
}
Finding XOR Sum between L and R
- Because XOR is its own inverse (), you can find the XOR sum of a range in time by computing:
XOR_Sum(L, R) = f(R) ^ f(L - 1)- This perfectly cancels out the prefix from to .
Key Takeaways
- The XOR sum from to repeats in a predictable 4-step cycle.
- Using modulo arithmetic, we bypass iteration entirely.
- Range queries can be computed in by combining two prefix sums.