# Find XOR of 1 to n

Programming

Share

In this programming tutorial we will find XOR of 1 to n.

XOR operator is a binary operator and it gives us 1 for odd number of 1s and 0 for even number of 1s.

In programming XOR is represented by `^` caret symbol.

We also represent XOR with this `⊕` plus inside circle symbol.

Following is the truth table for the XOR operator.

A B A^B
0 0 0
0 1 1
1 0 1
1 1 0

Remember!

XOR of odd 1s = 1

XOR of even 1s = 0

Check out Boolean Algebra tutorial.

Lets solve the problem.

## Problem:

Find 1 ⊕ 2 ⊕ 3 ⊕ ... N where value of N is provided as input.

#### Input:

The first line of the input contains a single integer T, denoting the number of test cases. Then T lines follow each containing one integer value N.

#### Output:

Print the output of each test cases in a separate line.

#### Constraint:

``````1 <= T <= 103
2 <= N <= 106
``````

#### Example Input

``````4
3
4
5
6
``````

#### Example Output

``````0
4
1
7
``````

### Naive approach

In the naive approach we will loop from 1 to N and compute the XOR.

#### C++ code

``````#include <iostream>
using namespace std;

int main() {
long long T, N, i, ans;

cin >> T;
while(T--) {
cin >> N;

ans = 0;
for(i = 1; i <= N; i++) {
ans = ans ^ i;
}

cout << ans << endl;
}

return 0;
}
``````

### Better approach

If we write down the XOR values for some of the initial values of N we will notice a pattern as shown below.

XOR for some of the inital values of N.

``````For N = 2
1 ^ 2
= 3

For N = 3
(1 ^ 2) ^ 3
= 3 ^ 3
= 0

For N = 4
(1 ^ 2 ^ 3) ^ 4
= 0 ^ 4
= 4

For N = 5
(1 ^ 2 ^ 3 ^ 4) ^ 5
= 4 ^ 5
= 1

For N = 6
(1 ^ 2 ^ 3 ^ 4 ^ 5) ^ 6
= 1 ^ 6
= 7

For N = 7
(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6) ^ 7
= 7 ^ 7
= 0

For N = 8
(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7) ^ 8
= 0 ^ 8
= 8

For N = 9
(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8) ^ 9
= 8 ^ 9
= 1

For N = 10
(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9) ^ 10
= 1 ^ 10
= 11

For N = 11
(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10) ^ 11
= 11 ^ 11
= 0

For N = 12
(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11) ^ 12
= 0 ^ 12
= 12
``````

We can see the following pattern in the above output.

• When N is a multiple of 4 then answer is equal to N.
• When N % 4 is equal to 1 then answer is equal to 1.
• When N % 2 is equal to 2 then answer is equal to N+1.
• When N % 4 is equal to 3 then answer is equal to 0.

Note! `%` represents the modulus operator.

#### C++ code

``````#include <iostream>
using namespace std;

int main() {
long long T, N, i, ans;

cin >> T;
while(T--) {
cin >> N;

switch(N % 4) {
case 0: ans = N; break;
case 1: ans = 1; break;
case 2: ans = N + 1; break;
case 3: ans = 0; break;
}

cout << ans << endl;
}

return 0;
}
``````

Hope this tutorial helped. Don't forget to share this on social media. See you in the next tutorial. Have fun coding :-)

Share