Practice › Bit Manipulation
XOR from 1 to N
Easy · Bit Manipulation · Asked at Amazon, Microsoft, Samsung
Print 1 ^ 2 ^ 3 ^ … ^ n (bitwise XOR).
Input
One integer n.
Output
The XOR value.
Constraints
- 1 ≤ n ≤ 10^18
The result repeats with period 4: n, 1, n + 1, 0 for n % 4 = 0, 1, 2, 3.
Example 1
Input
5
Output
1
Example 2
Input
4
Output
4
Hints
- n is up to 10^18 — looping is far too slow. Write out the prefix XORs for n = 1..8 and look for a pattern.
- The result depends only on n % 4: n, 1, n + 1, 0 for remainders 0, 1, 2, 3.
Approach
XOR of 1..n repeats with period 4: 1, 3, 0, 4, 1, 7, 0, 8, … For every multiple of 4 (k = 4t), (k) ^ (k+1) ^ (k+2) ^ (k+3) = 0, because the high bits cancel and the low two bits give 0^1^2^3 = 0. So only the last partial block matters. That gives n when n % 4 == 0, 1 when it's 1, n + 1 when it's 2, and 0 when it's 3.
Complexity: O(1) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
long long ans;
switch (n % 4) {
case 0: ans = n; break;
case 1: ans = 1; break;
case 2: ans = n + 1; break;
default: ans = 0;
}
cout << ans << "\n";
return 0;
}Python solution
n = int(input())
print([n, 1, n + 1, 0][n % 4])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long[] byRemainder = {n, 1, n + 1, 0};
System.out.println(byRemainder[(int) (n % 4)]);
}
}