XOR also known as Exclusive OR is a logical operation operates on two operands which results in true only if one of the operand has a value true .
In Java,C++,C,C# it is represented by ^.
In computer Science it is often used for bitwise operations.
010 XOR 110 =100
001 XOR 000=001
111 XOR 111=000
1010 XOR 1111 = 0101
There are certain properties of XOR which accounts for its numerous uses. ( I came to know some of them when I was trying to solve a problem in codechef. )
- XOR operation is Commutative . A^B=B^A
- XOR operation is Associative . (A^B)^C=A^(B^C)
- XOR ing of same number is zero. A^A=0
- XOR has zero(0) as the identity element. A^0=A
Here are some of the problems where XOR minimizes our effort.
- Swapping the numbers.
- Finding the number in the list which has odd parity.
Swapping the numbers is very easy . There are many ways to do this
int x=10,y=5,temp; temp=x; // temp=10 x=y; // x=5 y=temp; // y=10
int x=10,y=5; x=x+y; // x=15 y=x-y; // y=10 x=x-y; // x=5;
Method 3( Using XOR):
int x=10,y=5; y=x^y; // 15 x=x^y; // 5(=y) y=y^x; // 10(=x)
How is it happening? and Why?
Recall the properties of XOR-
Merge steps : y=y^x and x=x^y as x=x^(y^x)
x=x^(x^y) ; // ( As XOR is commutative)
x=(x^x)^y; //( As XOR is associative)
x=0^y=y; //(As A XOR 0=A)
2. Finding the numbers having odd parity.
There is an array which contains 2n+1 elements in which there are n numbers having duplicates. Only one element is there which which is not paired. How we can find that element ?
Count the occurrence of every (distinct ) element . If for any element count is 1 ,that is the required element.
Time Complexity- O(n^2);
Can we do better?
Ya, of course.
int result=array; //assuming array is 1 based for(int i=2;i<=array.length;i++) result=result^array[i];
result contains the required element.
If you follow the Use of XOR in Swapping numbers then you can easily understand why it is happening that result contains the required element.
Happy Coding!!! 🙂