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.
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 ^ YY = X ^ YX = 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)
------------
^ 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 !!!
Super...
ReplyDelete