## Sunday, November 13, 2016

### Calculate XOR from 1 to n. - GeeksforGeeks

Calculate XOR from 1 to n. - GeeksforGeeks
Given a number n, the task is to find the XOR from 1 to n.

Method 1 (Naive Approach):
1- Initialize result as 0.
1- Traverse all numbers from 1 to n.
2- Do XOR of numbers one by one with result.
3- At the end, return result.

Method 2 (Efficient method) :
1- Find the remainder of n by moduling it with 4.
2- If rem = 0, then xor will be same as n.
3- If rem = 1, then xor will be 1.
4- If rem = 2, then xor will be n+1.
5- If rem = 3 ,then xor will be 0.
When we do XOR of numbers, we get 0 as XOR value just before a multiple of 4. This keeps repeating before every multiple of 4.
Number Binary-Repr  XOR-from-1-to-n
1         1           [0001]
2        10           [0011]
3        11           [0000]  <----- We get a 0
4       100           [0100]  <----- Equals to n
5       101           [0001]
6       110           [0111]
7       111           [0000]  <----- We get 0
8      1000           [1000]  <----- Equals to n
9      1001           [0001]
10     1010           [1011]
11     1011           [0000] <------ We get 0
12     1100           [1100] <------ Equals to n
int computeXOR(int n)
{
// If n is a multiple of 4
if (n % 4 == 0)
return n;

// If n%4 gives remainder 1
if (n % 4 == 1)
return 1;

// If n%4 gives remainder 2
if (n % 4 == 2)
return n + 1;

// If n%4 gives remainder 3
return 0;
}