XOR for Beginners

help
1

I have seen questions that can be done using the XOR bitwise Operation. But I don’t get its concept and intuition of using this.
One such question is linked below which is of SPOJ. I can easily solve this question using hashmap but people solved it using XOR?
So, I need to know, why, where, and how we can use this beautiful or not XOR.

2

The property of xor is a^a=0 and a^0=a, and also a^b^c = a^c^b , so clearly anything that appears twice will become zero and the only unique element will remain

3 Likes
3

Only for this purpose we use it? XOR

4

Not only this. If you had tried this problem, you’ll understand one more beautiful property of Bitwise XOR:
If A and B are two integers, then

  1. If A has even number of set bits and B has even number of set bits, A^B will have even number of set bits.
  2. If any one of them has even number of set bits and the other has odd number of set bits, the result A^B will have odd number of set bits.
  3. If both of them have odd number of set bits, A^B will have even number of set bits.
1 Like
5

XOR has property like that
A^A=0
A^0=A
It is commutative and associative.
A^B=B^A
A^(B^C)= (A^B)^C
As in your question all numbers are occurring twice so you can take the XOR of all number. By taking for loop. You will.find that even occurrence of number become zero and the only remaining element will give your output.
Note:- But this is applicable only when only one numbers has odd occurrence and rest occurred even times.

2 Likes