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 bit | right bit | xor result |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
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)