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.

1. Swapping

Swapping the numbers is very easy . There are many ways to do this

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 ?

Method 1:

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.

Method 2:

int result=array[1]; //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.

Yes.. Using the XOR technique when swapping numbers is better, works even when the number is on the upper or lower bound of the datatypes like int or long!

Hey Deven ,
Just wanted to add one more property here , which can be very useful while solving many problems on CodeChef , HackerRank etc:
A = B ^ C then:
B = A ^ C
Well , its pretty easy to prove , but when you know it as a property , its very easy to use it:
B = B ^ 0
= B ^ (C ^ C)
= ( B ^ C ) ^ C
= A ^ C
Check: http://www.geeksforgeeks.org/find-the-missing-number/
For one of its many applications…

Yes.. Using the XOR technique when swapping numbers is better, works even when the number is on the upper or lower bound of the datatypes like int or long!

LikeLike

Hey Deven ,

Just wanted to add one more property here , which can be very useful while solving many problems on CodeChef , HackerRank etc:

A = B ^ C then:

B = A ^ C

Well , its pretty easy to prove , but when you know it as a property , its very easy to use it:

B = B ^ 0

= B ^ (C ^ C)

= ( B ^ C ) ^ C

= A ^ C

Check: http://www.geeksforgeeks.org/find-the-missing-number/

For one of its many applications…

LikeLike

Ya you are right!!

LikeLike

I must say, seems Method 2 is not clear to the Author himself .

The solution given in article doesn’t work.

Correct implementation goes like below:

public class Solution {

static int oddParity(int[] a) {

int result = 0;

for(int i=0;i<a.length;i++){

result = result ^a[i];

}

return result;

}

LikeLike

Wow, very well explained! Thanks…

LikeLike