Find XOR of 1 to n

Programming

← Prev Next →

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

About XOR operator

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 <= 10³
2 <= N <= 10⁶

Example Input

Example Output

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 :-)

← Prev Next →