Know this before you start: “x ^ x = 0 and other handy tricks”

XOR and other bit tricks

x ^ x = 0 and x ^ 0 = x, so XOR-ing everything cancels pairs. n & (n − 1) drops the lowest 1-bit. These solve a family of interview problems in O(1) space.

The idea

XOR cancels equal values in any order: a ^ b ^ a = b. XOR every number in the list and the pairs vanish, leaving the one that appears once.

n & (n − 1) clears the lowest set bit, so a power of two (exactly one 1-bit) gives 0. Repeating it counts the 1-bits.

XOR also finds a missing number: XOR all indexes 0..n with all values; everything present cancels.

See it step by step

The single number in [4, 1, 2, 1, 2]

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0
= 4.

In code (Python)

from functools import reduce
from operator import xor

def single_number(nums):
    return reduce(xor, nums)

def missing_number(nums):
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result

def is_power_of_two(n):
    return n > 0 and n & (n - 1) == 0

print(single_number([4, 1, 2, 1, 2]))      # 4
print(missing_number([3, 0, 1]))           # 2
print(is_power_of_two(16), is_power_of_two(18))   # True False

O(n) time, O(1) space.

When you'll use it

Single number, missing number, power of two, counting bits, swapping without a temp.

Common mistakes

Using XOR when values appear an odd number of times other than once.
Forgetting n > 0 in the power-of-two check.