Here goes

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.

^

------------

*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 ^ 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.

**0**0100100 (X)

^

**0**1100011 (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