Bit level tricks: XOR

Here goes exclusive post for Exclusive-OR / XOR !

XOR is a binary operator which acts on two number like A XOR B, denoted as A ^B.  A ^ B basically tells how different A is from B (or vice-versa). If a bit of A is different from the same bit of B, the resulting bit is 0.

Properties

1.   XOR with itself results 0

XOR-ing a number with itself returns 0. This also goes with the definition that XOR tells how different two numbers are. X ^ X = 0

     00000100   (4 in binary)                     
^   00000100   (4 in binary)
     ------------
     00000000

 

2.   XOR with 0 results number

 XOR-ing with zero gives back the same number.  X ^ 0 = X

     00000100   (4 in binary)                     
^   00000000   (0 in binary)
     ------------
     00000100

 

3.   XOR is associative and cumulative

 XOR is associative as well cumulative.

Associativity:  (X^Y)^Z = X^(Y^Z)

Cumulative:  X^Y = Y^X 

 

Bit Hacks

Let's see some XOR hacks.

#1: Swapping without temp variable

 X = X ^ Y

 Y = X ^ Y

 X = X ^ Y

Let's prove it by taking an example

X = A, Y = B

X = X ^ Y = A^ B

Y = X ^ Y = (A^B)^B = A^(B^B)  

    = A^0 //by property 1

    = A // by property 2

X = X ^ Y = (A^B)^A

    = B^(A^A)

    = B

#2: Check if two numbers have same sign

If two numbers have same sign then the MSB will be same (i.e. either both will be 0 or 1). This means that XOR of that bit will result in zero. 

 X ^ Y --> MSB of both numbers will be 0 if both numbers have same sign.

     00100100   (X)
^   01100011    (Y)
     ------------

     01000111     (>=0)

Above approach can be generalized as 

X ^ Y >= 0 

#3: Toggle between two values of a variable

Change value of a variable between two allowed values. So if the value is A change it to B and vice-versa. 

if X = A

change value of X to B 

XOR properties discussed above helps in achieving this. 

X = A ^ B ^ X

X = A ^ B ^ X

    = A ^ B ^ A   // X = A

    = (A^A)^B

    = B

 ---

keep coding !!!