Programming
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.
Remember! XOR of odd 1s = 1 XOR of even 1s = 0
Remember!
XOR of odd 1s = 1
XOR of even 1s = 0
Check out Boolean Algebra tutorial.
Lets solve the problem.
Find 1 ⊕ 2 ⊕ 3 ⊕ ... N where value of N is provided as 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.
Print the output of each test cases in a separate line.
1 <= T <= 103 2 <= N <= 106
4 3 4 5 6
0 4 1 7
In the naive approach we will loop from 1 to N and compute the XOR.
#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; }
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.
Note! % represents the modulus operator.
%
#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 :-)