The magic of XOR

XOR is an interesting operation and stands for 'exclusive OR'.  In this post, I will cover few problems which can be solved by using XOR.

Truth Table:

P ^ Q == (~P & Q) | (P & ~Q)

Problem 1:  Find number occurring odd no.of times

We can solve this problem by exploiting below mentioned XOR property.

p1^p2^p3^...^pn = true if no. of variables with the value true is ODD

p1^p2^p3^...^pn = false if no. of variables with the value true is EVEN

(This property doesn't hold true for variables with false value)

Problem 2: Find missing number in a range with out duplicates

1) Find XOR value of all numbers in the range

2) Find XOR value of all numbers in the array

3) XOR above values to know missing number

Problem 3: Swapping two numbers with out taking help of temp variable

Let's say we have to swap values of X and Y.

// X = A ,Y = B

// X = A ^ B, Y=B

X =  X ^ Y 

//Y = A^B ^ B -> A

Y =  X ^ Y

//A^B^A -> B

X = X ^ Y

X = B,Y=A

More about XOR on 

http://stackoverflow.com/questions/6398427/what-does-bitwise-xor-exclusive-or-mean

Hope you find this post useful.

Happy Learning