0
Challenge · 69Greedy, Bits & Math

Bit manipulation and the XOR trick

Techniquesused in ~70% of apps

A number is a row of switches, and there are five operations that read or flip them. The one worth real attention is XOR, because it cancels: anything combined with itself disappears, which turns some search problems into a single pass with no memory at all.

Core idea. XOR has three properties that do all the work. A number XORed with itself is 0, a number XORed with 0 is unchanged, and the order does not matter. Together they mean that XORing a whole list makes every duplicate vanish, leaving exactly what appeared an odd number of times.
Playground, this isn't a screenshot
click a bit position
value90
Each position is worth twice the one to its right. A number is just a set of switches, and the bit operations read and flip them one at a time.

There is nothing mysterious about bit operations. Shift to reach a position, AND to read, OR to set, XOR to flip.

↑ play a little first, then dig in