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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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