XOR is one of the standard bitwise operation. Here is the truth table for same..

1 XOR 0 = 1

0 XOR 1 = 1

0 XOR 0 = 0

1 XOR 1 = 0

The trick that XOR provides is that if you take XOR of two N bit numbers(let say c = a XOR b), which is another N bit number then given one number(a or b) and the XOR result(c) you can determine the other number.

Basically( it can be easily proved by using truth tables)

a XOR (a XOR b) = b

b XOR (a XOR b) = a

This trick can be used to, for example, swap two integers without using a temporary variable.

Let say you wanted to swap x and y. Here is the required sequence.

x = x XOR y

y = x XOR y (y becomes old x)

x = x XOR y (x becomes old y)

In another use of this trick, you can implement doubly-linked list from a singly linked list without storing two pointers(prev, next) but just one(prev XOR next).

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment