🧠 Michael Cordell's Brain Dump

XOR Algorithm Trick

1 min read

XOR has a few useful properties:

  1. x^0=x
  2. x^x=0
  3. x^y=y^x Commutative
  4. Pairs within a sequence can be removed: x^y^x=y

Given this, you can swap a two variables without an intermediary variable:

x = x ^ y
y = x ^ y
x = x ^ y

This can also be used to find a missing or duplicated element within a set.

Assume a “main” set of 1-n. Assume a separate “missing” set containing all but 1 of the numbers. XOR all of the main set, XOR all of the missing set and then XOR these two values and you have the missing number.

Graph View

Backlinks