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)


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 ?

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 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. 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!


  2. 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;


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s