Exclusive OR

Following symbol are used to explain Exclusive OR in logic, or mathematics.

$A{\veebar}B \\ A{\oplus}B$

logical operation

A	B	$A{\oplus}B$
F	F	F
F	T	T
T	F	T
T	T	F

$X \oplus False(0) = X \\ X \oplus True(1) = \lnot X$

Commutative low, Associative low

Like Addition or Multiplication, commulative low and associative low can be applied to XOR.

Commutative low

$A \oplus B = B \oplus A$

Assciative low

$A \oplus (B \oplus C) = (A \oplus B) \oplus C$

A	B	C	$A{\oplus}(B{\oplus}C)$	$(A{\oplus}B){\oplus}C$
F	F	F	F	F
F	F	T	T	T
F	T	F	T	T
F	T	T	F	F
T	F	F	T	T
T	F	T	F	F
T	T	F	F	F
T	T	T	T	T



In [ ]:

    
# In Python, XOR operator is ^
for a in (False, True):
    for b in (False,True):
        for c in (False, True):
            # print (a, b, c, a^(b^c), (a^b)^c)
            print ("{!r:5} {!r:5} {!r:5} | {!r:5} {!r:5}".format(a, b, c, a^(b^c), (a^b)^c))

Find general rule from specific case

What will be returned for 1 True $\oplus$ 100 False
What will be returned for 2 True $\oplus$ 100 False
What will be returned for 3 True $\oplus$ 100 False
What will be returned for 101 True $\oplus$ 10000 False

What is the general rule ?

Bit operation

When 2 integers are calculated with XOR operator, each bit is calculated separately. (Same as AND, OR, NOT)

10(0b1010) xor 6(0b0110) = 12 (0b1100)
10(0b1010) and 6(0b0110) =  2 (0b0010)
10(0b1010) or  6(0b0110) = 14 (0b1110)
NOT 10(0b1010)           = 5  (0b0101)


0b1010    0b1010    0b1010    0b1010
0b0110    0b0110    0b0110
-(XOR)-   -(AND)-   -(OR)-    -(NOT)-
0b1100    0b0010    0b1110    0b0101



In [ ]:

    
# CONSTANT is not supported in Python, Upper case variable is typically used as Constant

INT10 = 0b1010
INT06 = 0b0110
REV_MASK = 0b1111

print('INT10:', INT10, 'INT06:', INT06)
print('Bit XOR:', INT10^INT06)
print('Bit AND:', INT10&INT06)
print('Bit OR: ', INT10|INT06)
print('Bit NOT', INT10, ':', (~INT10)&0x0f)
print('Reverse INT10:', INT10^REV_MASK)
print('Reverse INT06:', INT06^REV_MASK)

XOR usage

Bit reverse (ex. 32bit integer, remain upper 16bit, reverse lower 16bit)
CPU register 0 clear (Often used in assemblar): $X \oplus X = 0$
Encryption ($Original \oplus Key = Encrypted \rightarrow Encrypted \oplus Key = Original$)
Parity (RAID5 etc, N HDD with (N-1) Capacity, If one of the HDD is broken, its data can be recovered from other data)

XOR parity

$A \oplus A = 0$
$A \oplus B = 0 \rightarrow A = B$
$A \oplus B = C \rightarrow A \oplus B \oplus C = 0 \rightarrow A = B \oplus C$
$A \oplus B \oplus C \oplus ... Z = 0 \rightarrow X =$ XOR of other DATA



In [ ]:

    
# XOR data recovery test, Create parity from 3 random data, Recover any data from other data and parity

import random

data = [random.randrange(1000000) for i in range(3)]
print(data)

parity = 0
for x in data:
    parity ^= x

print('XOR of all data is:', parity)
print('DATA[0]:', data[1]^data[2]^parity)
print('DATA[1]:', data[0]^data[2]^parity)
print('DATA[2]:', data[0]^data[1]^parity)
print('Parity: ', data[0]^data[1]^data[2])
print('XOR of all data + Parity:', data[0]^data[1]^data[2]^parity)

XOR parity recalculation

Initialization: XOR of every data
Update:
- Calculate $OldData \oplus NewData = Diff$
- $NewParity=OldParity \oplus Diff$



In [ ]:

    
import random

data = [random.randrange(1000000) for i in range(5)]
print(data)

# Initialize Parity
parity = 0
for x in data:
    parity ^= x
    
# Update data[2]
olddata = data[2]
newdata = random.randrange(1000000)
print('data[2] is updated from:', olddata, 'to', newdata)
data[2] = newdata
diff = olddata ^ newdata

# Calc new parity
newparity = parity ^ diff
print('old parity:', parity)
parity = newparity
print('new parity:', parity)

# Check if parity is correct
chk_parity = 0
for x in data:
    chk_parity ^= x

print('updated parity:', chk_parity)