# 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;  //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!!! 🙂

## 5 thoughts on “XOR Properties”

1. Sankha Narayan Guria says:

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!

Like

2. Harsh Trivedi says:

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…

Like

1. Deven Bhooshan says:

Ya you are right!!

Like

3. subrat pandey says:

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;
}

Like

4. Sunil says:

Wow, very well explained! Thanks…

Like