Reputation: 53
Actually it's a hackerrank problem, the lonely integer. I understand the XOR logic used here. I just couldn't understand deeply the concept how is every number being processed after input. I have marked the line in code. Please help me in understanding it.
#include <iostream>
using namespace std;
int main()
{
int n, a, c = 0, i;
cin >> n;
for (i = 0; i < n; i++)
{
cin >> a;
c ^= a; // THIS LINE .... i WANT TO KNOW HOW IS THIS WORKING ?
// HOW IS COMPARISON BEING CARRIED OUT HERE ?
}
cout << a << endl;
return 0;
}
Upvotes: 2
Views: 135
Reputation: 106102
Program finds the number which is lonely, i.e. not in pair. XORing a number to itself results in 0
. Using this concept all numbers are XORed one by one. A pair of number is xored and then the result is xored with another number in the input sequence and so on. At last the number which comes single will be left.
For example :
For the input 1 1 2 3 0 0 3
1 ^ 1 = 0
0 ^ 2 = 2
2 ^ 3 = 1
1 ^ 0 = 1
1 ^ 0 = 1
1 ^ 3 = 2
and 2
is lonely.
Upvotes: 3