BitsAlgorithmaka exclusive or tricks, single number, XOR swap, prefix XOR

XOR Patterns

Exploit XOR's self-cancelling property to find unpaired elements, missing numbers, swap without a temporary, and answer range-XOR queries.

▶ VisualizePattern: Prefix SumPractice (4)
Progress

Overview

XOR has four properties that make it a problem-solving tool: identity x ^ 0 = x; self-inverse x ^ x = 0; commutative a ^ b = b ^ a; associative (a ^ b) ^ c = a ^ (b ^ c). Together they mean the XOR of a multiset depends only on which values appear an odd number of times, in any order.

Single number: in an array where every value appears twice except one, XOR everything; pairs cancel and the lone value remains. Missing number in 0..n: XOR all indices 0..n with all values; every present number cancels with its index. Two single numbers: XOR all to get a ^ b, pick any set bit of it (d & -d), and split the array by that bit — each group has exactly one unpaired value.

XOR swap: a ^= b; b ^= a; a ^= b exchanges two variables without a temporary — a curiosity that breaks when both refer to the same location. Prefix XOR: px[i] = a[0] ^ … ^ a[i-1] gives any range XOR as px[r+1] ^ px[l] in O(1), the XOR analogue of Prefix Sum — see Prefix XOR. Other identities: x ^ ~x = -1 (all ones), a ^ b = 0 ⟺ a == b, and (a ^ b) & (a ^ b) - 1 style tricks build on Power-of-Two Tricks.

XORself-inversesingle numbermissing numberprefix xorO(n)

Intuition

A mental model before the formal terms.

XOR is a light switch: flipping it twice returns it to where it started. XOR-ing a whole list into an accumulator flips a bit once per occurrence of each number, so anything appearing an even number of times ends up back at "off", and only odd occurrences leave a trace. That is why pairs vanish and the singleton survives regardless of order.

Prefix XOR is a running "switch state" from the start. The state of the range [l, r] alone is the state at r with the state before l undone — and undoing is the same operation as doing.

How it works

  1. Single number: acc = 0; for x in a: acc ^= x; return acc.
  2. Missing number: acc = n; for i, x in enumerate(a): acc ^= i ^ x; return acc (n is included because indices only run to n - 1).
  3. Two singles: d = XOR of all; bit = d & -d; a = XOR of elements with (x & bit) != 0; b = d ^ a.
  4. Swap: a ^= b (a holds a ^ b); b ^= a (b holds b ^ a ^ b = a); a ^= b (a holds a ^ b ^ a = b).
  5. Prefix XOR: px[0] = 0; px[i + 1] = px[i] ^ a[i]; query l..r as px[r + 1] ^ px[l]. To count subarrays with XOR equal to k, count earlier prefixes equal to px ^ k in a hash map.

Why it works

By associativity and commutativity, x1 ^ x2 ^ … ^ xm can be regrouped so identical values sit next to each other; each pair reduces to 0 by self-inverse, and 0 is the identity, so only values with odd multiplicity contribute.

Two singles: d = a ^ b ≠ 0 because a ≠ b, so some bit differs. Splitting by that bit places a and b in different groups while every pair stays together (equal numbers have equal bits), so each group's XOR is its unpaired element.

Range XOR: px[r+1] = a[0] ^ … ^ a[r] and px[l] = a[0] ^ … ^ a[l-1]; XOR-ing them cancels the common prefix a[0..l-1], leaving a[l] ^ … ^ a[r].

Recognition

How to tell a problem wants this.

  • "Every element appears twice except one", "appears an even number of times", "find the missing/duplicate number in 0..n".
  • "O(1) extra space" plus "without sorting" plus pairs — the classic signal for XOR cancellation.
  • "XOR of subarray", "count subarrays with XOR k", "maximum XOR of two numbers" (the latter combines prefix bits with a Trie).
“sum of subarray” → Prefix Sum“parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Bitwise Operators visualization.

a
0
7
0
6
0
5
0
4
1
3
1
2
0
1
0
0
= 12
b
0
0
0
0
1
0
1
0
= 10
1/8Start with a=12 (00001100) and b=10 (00001010). Bit 0 on the right is the least significant; each operator works bit by bit.
Bits being examinedResult bit is 1Result bit is 0
PseudocodeLearn Bitwise Operators →
1a & b   # 1 only where both bits are 1
2a | b   # 1 where either bit is 1
3a ^ b   # 1 where bits differ
4~a      # flip every bit (8-bit view)
5a << 1  # shift left: doubles, drops the top bit
6a >> 1  # shift right: halves, drops the low bit
Variables
a12
b10
Complexity
best O(1)
avg O(1)
worst O(1)
space O(1)
Speed

Pseudocode

1// single number
2acc = 0
3for x in a: acc ^= x
4return acc
5// missing number in 0..n (len(a) == n)
6acc = n
7for i in 0..n-1: acc ^= i ^ a[i]
8return acc
9// prefix xor query [l, r]
10return px[r + 1] ^ px[l]

Implementations

1from typing import List, Tuple
2 
3 
41 · Single unpaired number
5def single_number(nums: List[int]) -> int:
6    acc = 0
7    for x in nums:
8        acc ^= x  # pairs cancel: a ^ a == 0, order irrelevant
9    return acc
10 
11 
122 · Missing number in 0..n
13def missing_number(nums: List[int]) -> int:
14    acc = len(nums)  # seed with the one index the loop skips
15    for i, x in enumerate(nums):
16        acc ^= i ^ x
17    return acc
18 
19 
203 · Swap without a temporary
21def xor_swap(a: int, b: int) -> Tuple[int, int]:
22    # Included for the pattern; idiomatic Python is simply a, b = b, a
23    if a == b:
24        return a, b
25    a ^= b
26    b ^= a
27    a ^= b
28    return a, b
29 
30 
314 · Prefix XOR for range queries
32class XorRange:
33    def __init__(self, a: List[int]) -> None:
34        self.prefix = [0] * (len(a) + 1)  # prefix[i] = a[0] ^ ... ^ a[i-1]
35        for i, x in enumerate(a):
36            self.prefix[i + 1] = self.prefix[i] ^ x
37 
38    def query(self, l: int, r: int) -> int:
39        return self.prefix[r + 1] ^ self.prefix[l]  # xor of a[l..r]
40 
41 
425 · Demo
43if __name__ == "__main__":
44    assert single_number([4, 1, 2, 1, 2]) == 4
45    assert missing_number([3, 0, 1]) == 2
46    assert xor_swap(5, 9) == (9, 5)
47    assert XorRange([1, 3, 4, 8]).query(1, 2) == 3 ^ 4
Walkthrough
  1. Python ints are unbounded, so the XOR folds are exact for any size — no 32-bit ceiling to think about.
  2. missing_number uses enumerate to XOR each index with its value; the seed len(nums) supplies the final index.
  3. xor_swap is shown for the pattern; a, b = b, a is the idiomatic swap and the aliasing hazard cannot arise with immutable ints.
  4. XorRange.prefix is a plain list of exclusive prefixes; query XORs two entries.
Complexity (this implementation)
time O(n) build / fold, O(1) query · space O(1) folds, O(n) prefix table
Language notes
  • functools.reduce(operator.xor, nums, 0) is the stdlib fold.
  • XOR of negative ints follows infinite two's complement: -1 ^ 1 == -2; results are exact, just mind the sign.
  • Since ints are immutable, xor_swap returns a tuple — it cannot swap the caller's variables in place.
Common mistakes in this language
  • Using sum(range(n + 1)) - sum(nums) and calling it equivalent — it is, in Python, but the XOR form is the transferable pattern (no bignum crutch elsewhere).
  • Expecting xor_swap to mutate its arguments like the C++ reference version.
  • Rebuilding the prefix list on every query.
Language differences that matter here
  • Value range: C++ XOR is exact per type width (use long long for 64-bit); JS/TS truncate to 32-bit signed (BigInt beyond); Python is unbounded.
  • In-place swap: C++ swaps through references (aliasing guard required); JS/TS/Python cannot rebind caller variables — use destructuring / tuple assignment, which is also the idiomatic swap.
  • The sum-formula alternative for missing-number can overflow C++ int and lose precision past 2^53 in JS/TS; the XOR version is exact in every language.
  • Fold spelling: std::accumulate + std::bit_xor<> (C++), reduce((a, x) => a ^ x, 0) (JS/TS), functools.reduce(operator.xor, ...) (Python).

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Single/missing/two-singles are one or two linear passes with O(1) memory. Prefix XOR is O(n) build, O(1) per query, O(n) space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Finding elements with odd multiplicity in O(n) time and O(1) space, where sorting or hashing would cost more.
  • Range XOR queries on a static array, or counting subarrays by XOR value with a hash map of prefix values.
  • Verifying equality of two multisets cheaply as a first filter (equal XOR is necessary, not sufficient).
Avoid it when
  • When the odd element appears three times or a different odd count and others appear twice — plain XOR does not distinguish; use per-bit counting mod 3 (Single Number II) or a hash map.
  • XOR swap in real code: it is slower than a temporary on modern CPUs and silently zeroes a variable swapped with itself.
  • When the array may contain the same value with different multiplicities that are both even — XOR yields 0 and tells you nothing about which values were present.

Alternatives

Hash MapPrefix XORCounting Sort

Common mistakes

  • Missing number: forgetting to XOR n itself (the index range is 0..n-1 but the value range is 0..n).
  • Two singles: splitting on an arbitrary bit rather than a bit that is set in a ^ b; the bit must differ between the two.
  • XOR swap of an element with itself (swap(a[i], a[i])) — the first step sets it to 0.
  • Prefix XOR queries off by one: the query is px[r + 1] ^ px[l], not px[r] ^ px[l].
  • Assuming XOR of a range equals the sum; it is not additive and cannot be used to compute sums.

Interview patterns

  • Single Number I (XOR all), II (count bits mod 3), III (split by differing bit).
  • Missing Number, Find the Duplicate (with a bit-counting variant), Find the Difference between two strings.
  • XOR Queries of a Subarray via prefix XOR; count subarrays with XOR k via hash map of prefixes.
  • Maximum XOR of two numbers in an array: greedy bit by bit with a binary Trie of prefixes.
Interview questions on this
Mock interviews

Example problems

Find the Duplicate NumbermediumSingle NumbereasyBit Counting TrickseasyRange XOR Queries with Updatesmedium