xor and mod 2

so there’s a interesting property between the XOR operation and mod 2

turns out, the xor (^) of any sequence of bits is equal to the sum of those bits modulo 2

for example

1 ^ 0 ^ 1 ^ 1 is the same as (1 + 0 + 1 + 1) % 2

if you take this step by step, the xor side:

1 ^ 0 = 1

1 ^ 0 = 1

1 ^ 1 = 0

0 ^ 1 = 1 (answer)

the modulo side:

1 + 0 + 1 + 1 = 3

3 % 2 = 1

why?

lets look at the truth table for XORs using two bits

left bitright bitxor result
000
011
101
110
xor table

XOR is an exclusive OR, so it will only be 1 if there’s ONLY ONE bit that’s on. if there’s two bits or no bits, the result is 0. what other operation of two operands where the result is 0 given 0 and 0 and 1 and 1? modulo 2!

this equivalence exists because when we’re dealing with two bits, their sum is 2. 2 mod 2 is 0. when both bits are 0, the sum is 0 and 0 mod 2 is 0. when only one of them (and odd number) is on, we always get a sum of 1 and 1 mod 2 is 1

even though we’re only looking at two bits, this actually generalizes to any sequence of bits because it turns out that XORing any sequence of bits results in 0 when there is an even number of 1 bits and 1 when there is an odd number of 1 bits (or none)