XOR and self-cancellation

One property does all the work: anything combined with itself vanishes.

Key idea

Three properties, and everything follows

Anything combined with itself gives zero. Anything combined with zero is unchanged. The operation does not care about order or grouping.

Together those mean that combining a whole collection cancels every value appearing an even number of times and leaves whatever appears an odd number of times. That single consequence is the entire technique.

Each of the three is worth seeing on its own before relying on the consequence.

1print("a value cancels itself:  ", 7 ^ 7)2print("zero changes nothing:    ", 9 ^ 0)3print("order does not matter:   ", (5 ^ 3) ^ 5, "and", 3 ^ (5 ^ 5))4print("so a pair anywhere drops:", 4 ^ 6 ^ 1 ^ 6 ^ 4)

The last line is the consequence: both pairs vanish wherever they sit, and only the unpaired 1 survives.

Predict the output· 5 min

Predict the output: what survives

Type the three values this prints, separated by single spaces.

Python

1print(5 ^ 3 ^ 5, 5 ^ 5 ^ 3 ^ 3, 1 ^ 2 ^ 3)

Printed output

Problem· 15 min

Single Number

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 15 min

Missing Number

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Bit Manipulation

163 / 170

Bit ManipulationLesson 3 of 5About 48 min

XOR and self-cancellation

One property does all the work: anything combined with itself vanishes.

Key idea

Three properties, and everything follows

Anything combined with itself gives zero. Anything combined with zero is unchanged. The operation does not care about order or grouping.

Each of the three is worth seeing on its own before relying on the consequence.

1print("a value cancels itself:  ", 7 ^ 7)2print("zero changes nothing:    ", 9 ^ 0)3print("order does not matter:   ", (5 ^ 3) ^ 5, "and", 3 ^ (5 ^ 5))4print("so a pair anywhere drops:", 4 ^ 6 ^ 1 ^ 6 ^ 4)

The last line is the consequence: both pairs vanish wherever they sit, and only the unpaired 1 survives.

Predict the output· 5 min

Predict the output: what survives

Type the three values this prints, separated by single spaces.

Python

1print(5 ^ 3 ^ 5, 5 ^ 5 ^ 3 ^ 3, 1 ^ 2 ^ 3)

Printed output

Problem· 15 min

Single Number

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 15 min

Missing Number

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.