Skip to content
CodeItRaw
Bit Manipulation

Lesson 2/3

Three properties of XOR make a small piece of magic together: a number XORed with itself is 0 (x ^ x == 0), XORed with 0 it is itself (x ^ 0 == x), and order does not matter. So if you XOR a pile of numbers together, everything that appears an even number of times cancels out; what is left is what appears an odd number of times.

odd_one = 0
for v in [7, 3, 7, 9, 3]:
    odd_one ^= v
# odd_one is 9
No counting with a dictionary and no extra memory: one variable and one pass. The 7s cancel each other, and so do the 3s.

The same idea solves "which one is missing?". XOR together all the numbers from 0 to n and all the numbers in the list: every number in the list has now appeared twice and is gone, and the missing one appeared once and stays. Adding and subtracting does the same job; XOR's advantage is that there is no overflow to worry about however large the numbers get.

Tasks

Tasks open in order. Solve them all and the next lesson opens.

This lesson's tasks open when the lessons before it are finished. You can read the explanation now.

  1. 01

    Lone Wolf

    Function

  2. 02

    Missing Number

    Function

If you would rather not wait for the order, every problem is open without locks: Problem list