XOR Properties

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.

1. Swapping the numbers.
2. 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

Method 1: 

int x=10,y=5,temp;
temp=x; // temp=10
x=y; // x=5
y=temp;  // y=10

Method 2:

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)

OR

x=x^(x^y) ; // ( As XOR is commutative)

OR

x=(x^x)^y; //( As XOR is associative)

OR

x=0^y=y; //(As A XOR 0=A)

Similarly

y=0^x=x;

2.  Finding the numbers having odd parity.

Example:

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.

Happy Coding!!! 🙂