Bitwise XOR Patterns

XOR earns its own page because it has one property no other operator has, and that property solves a whole family of problems:

$x \oplus x = 0$ and $x \oplus 0 = x$.

So XOR-ing a collection cancels everything that appears an even number of times and leaves exactly what appears an odd number of times — without a hash map, in $O(1)$ space, and in any order, because XOR is commutative and associative.

Once you see XOR as a self-cancelling accumulator, “find the element that appears once among pairs” stops being a puzzle and becomes a one-liner.

What you’ll learn

• The four identities that make XOR work, and the $O(1)$-space single-number trick.
• The lowest set bit idiom x & -x, and how it splits a problem in two.
• Why “appears three times” needs a different technique entirely.
• The bitwise trie: how “prefix” can mean bit prefix, turning maximum-XOR from $O(n^2)$ into $O(32n)$.
• Three real LeetCode problems solved in the browser: 136, 260, 421.

The cue

You are looking at an XOR pattern when…

• Elements appear in pairs and you want the odd one out — 136, 268, 389.
• Two elements appear once and the rest in pairs — 260, which needs the split trick.
• The problem says $O(1)$ space where a hash map would be the obvious answer. That constraint is the hint.
• A missing or duplicated number in a known range — 268, 287, 645.
• Maximise a XOR over pairs — 421, 1707, which are bitwise-trie problems.
• An array was encoded by XOR-ing adjacent elements — 1720, 1734, where you simply XOR back.

The four identities

Identity	Consequence
$x \oplus x = 0$	duplicates cancel
$x \oplus 0 = x$	0 is the identity, so it is the right accumulator seed
$a \oplus b = b \oplus a$	order does not matter
$(a \oplus b) \oplus c = a \oplus (b \oplus c)$	grouping does not matter

Together they mean you can fold a whole array with XOR and the pairs vanish:

single_number.py

def single_number(nums):
    result = 0                    # 0 is the identity
    for n in nums:
        result ^= n               # pairs cancel to 0
    return result
 
 
print(single_number([4, 1, 2, 1, 2]))   # 4

$O(n)$ time, $O(1)$ space — which is the entire point. A Counter also solves it in $O(n)$ but needs $O(n)$ space, and LC 136 explicitly asks for constant.

A useful relative: XOR of a range

For “find the missing number in 0..n” (LC 268), XOR the indices and the values together:

python

def missing_number(nums):
    result = len(nums)                    # the index n, which has no slot
    for i, n in enumerate(nums):
        result ^= i ^ n
    return result

Every present value cancels with its index, leaving the missing one. The sum-based formula n(n+1)/2 - sum(nums) also works and is arguably clearer — but XOR cannot overflow, which is why it is preferred in fixed-width languages. Worth mentioning as the reason to reach for it.

The lowest set bit, and splitting in two

LC 260 has two singles. XOR-ing everything gives a ^ b — the two answers mixed together, and you cannot separate them from that alone.

But a ^ b is non-zero, so it has at least one set bit. Any set bit is a position where a and b differ. Pick one, partition the array by that bit, and each half now contains exactly one single — so apply LC 136 twice.

single_number_iii.py

def single_number_iii(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n              # == a ^ b
 
    bit = xor_all & -xor_all      # isolate the LOWEST set bit
 
    a = b = 0
    for n in nums:
        if n & bit:
            a ^= n                # group where the bit is set
        else:
            b ^= n                # group where it is not
    return [a, b]

Why x & -x isolates the lowest set bit

In two’s complement, -x is ~x + 1. Flipping all bits and adding one leaves every bit below the lowest set bit as 0, the lowest set bit itself as 1, and every bit above it inverted. AND-ing with x therefore keeps only that one bit.

Concretely, x = 12 is 1100. Then -12 is ...0100 in the low bits, and 12 & -12 = 4 = 0100 — exactly the lowest set bit.

It is a genuinely useful idiom beyond this problem: it is how a Fenwick tree walks its index structure.

Why any differing bit works: each pair contributes both its copies to the same group (equal numbers have equal bits), so pairs still cancel within a group. And a and b differ at this bit by construction, so they land in different groups. Both properties are what make the split valid.

XOR does NOT solve “appears three times”

LC 137 has one single and the rest appearing three times. XOR is useless here: three copies XOR to the value itself, not to zero, so nothing cancels.

The techniques that do work:

• Bit counting. For each of the 32 positions, count set bits across all numbers and take the count mod 3. What remains is the single. $O(32n)$, conceptually simple, and easy to generalise to “appears k times”.
• Two accumulators (ones and twos) implementing a mod-3 counter with bit tricks. Shorter, much harder to derive live.

The lesson is that XOR’s power comes specifically from pairs. When the multiplicity changes, the tool changes.

Bit prefixes and the bitwise trie

LC 421 asks for the maximum XOR over all pairs. Brute force is $O(n^2)$, too slow at $n = 2 \times 10^5$.

Two approaches, both built on the same idea — treat the numbers’ binary representations as strings and reason about prefixes:

max_xor_prefix.py

def find_maximum_xor(nums):
    best = 0
    for shift in range(31, -1, -1):          # decide the answer bit by bit
        best <<= 1
        prefixes = {n >> shift for n in nums}   # all high-bit prefixes
        candidate = best | 1                    # can we achieve a 1 here?
        if any(candidate ^ p in prefixes for p in prefixes):
            best = candidate
        # else the bit stays 0 (best already has a trailing 0 from the shift)
    return best

The reasoning is greedy from the top: higher bits dominate, so if a 1 is achievable at this position you always take it. And a ^ b = candidate implies candidate ^ a = b, so checking whether some pair achieves candidate is a set membership test.

$O(32n)$ time, $O(n)$ space.

The trie version inserts every number as a 32-step path of 0/1 children, then for each number walks down greedily taking the opposite bit wherever that child exists. Same complexity, and it generalises better to problems with extra constraints (LC 1707 adds a limit on which numbers may be used).

Visual intuition

Three properties combine into the trick: x ^ x = 0, x ^ 0 = x, and XOR is commutative. So duplicates cancel regardless of order:

bitsPairs cancel, the loner survivesLC 136 · O(1) space

0001020304050607

input

4011221324

acc0binary00000000

1def single_number(nums):2    acc = 03    for v in nums:4        acc ^= v          # pairs cancel, the loner survives5    return acc

setupXOR has three properties that combine into a trick: x ^ x = 0, x ^ 0 = x, and it is commutative. So XORing everything makes every duplicated value cancel itself out regardless of order, leaving only the value that appears once.

Play‹›1/7⟲

A hash set solves this too and is easier to explain, but costs O(n) memory — and the O(1) space requirement is the entire reason the problem is asked. Note the trick breaks if a value appears three times.

Dry run

LC 260 — nums = [1, 2, 1, 3, 2, 5], two singles (3 and 5) among pairs. Watch the running XOR: the pairs cancel as they complete, not at the end.

n	xor_all after	binary	what just happened
1	1	0001	first 1 enters
2	3	0011	first 2 enters
1	2	0010	the 1s cancel — bit 0 clears
3	1	0001	3 enters
2	3	0011	the 2s cancel, leaving 1 ⊕ 3
5	6	0110	5 enters; xor_all = 3 ^ 5 = 6

xor_all = 6 = 0110 — the two answers mixed. Now isolate the lowest set bit: 6 & -6 = 2 = 0010, and partition on it.

group	members	XOR of group
bit 1 set	2, 3, 2	3
bit 1 clear	1, 1, 5	5

Answer [3, 5].

• The intermediate values are meaningless and that is fine. After four numbers xor_all is 1, which is neither a member of the array nor part of the answer. XOR accumulates cancellation, so only the final value carries information — a reason not to try debugging these loops by eyeballing intermediates.
• Each pair lands entirely in one group. Both 2s have bit 1 set, both 1s have it clear. Equal numbers have equal bits, so no pair is ever split — which is why cancellation still works inside each group. That is the half of the argument people skip.
• 3 and 5 differ at bit 1 by construction. 3 = 011, 5 = 101: the set bits of 3 ^ 5 = 6 are exactly the positions where they differ, so partitioning on any one of them separates them. The lowest is chosen only because x & -x makes it free.
• 6 & -6 = 2, and 12 & -12 = 4. In two’s complement -x is ~x + 1, which leaves everything below the lowest set bit as 0, that bit as 1, and everything above inverted — so the AND keeps exactly one bit.

LC 268 (missing number) on [3, 0, 1], the same identity used differently: XOR the indices 0..n together with every value, and everything pairs off except the missing one — result 2. No sum, so no overflow concern in languages where that matters, and no sorting.

Complexity

Problem	Time	Space	Note
LC 136 single number (pairs)	$O(n)$	$O(1)$	one accumulator
LC 268 missing number	$O(n)$	$O(1)$	XOR indices and values together
LC 389 the difference	$O(n)$	$O(1)$	XOR both strings’ characters
LC 260 two singles	$O(n)$	$O(1)$	two passes, one accumulator each
LC 137 appears three times	$O(32n)$	$O(1)$	not XOR — bit counting mod 3
LC 421 max XOR of two numbers	$O(32n)$	$O(32n)$	bitwise trie, or prefix-set per bit
Hash-set / sorting alternatives	$O(n)$ / $O(n \log n)$	$O(n)$ / $O(1)$	correct, but the point of XOR is the $O(1)$ space

The $O(1)$ space is the entire reason these problems are asked. A hash set solves LC 136 in $O(n)$ time too — but the follow-up is always “now do it without extra memory”, and XOR is the answer to that specific question. Say the set solution first, then improve it.

Python integers are not 32-bit, and it shows up here

Every XOR identity on this page is width-independent, so LC 136/260/268 are unaffected. But the moment a problem involves negative numbers with a fixed width — LC 371 (add without +), LC 190 (reverse bits), LC 191 on a signed input — Python’s arbitrary-precision integers diverge from the 32-bit behaviour the problem assumes: ~x is -x-1 with infinitely many leading 1s, not a 32-bit complement.

The fix is to mask: keep values in x & 0xFFFFFFFF, and convert back at the end with x - (1 << 32) if x >= (1 << 31) else x. Knowing why that is needed — rather than copying it — is a common Python-specific interview follow-up.

The variant map

Variant	The technique	Canonical problem
One single among pairs	Fold with XOR	136 · 389
Missing number in a range	XOR indices with values	268
Two singles among pairs	x & -x to split, then fold each half	260
One single among triples	Bit counting mod 3 — not XOR	137
Maximum XOR pair	Greedy bit prefixes, or a bitwise trie	421 · 1707
Decode an XOR-encoded array	XOR back cumulatively	1720 · 1734
Count subarrays with XOR = k	Prefix XOR + hash map	1442-adjacent

Prefix XOR is the same trick as prefix sums

Because XOR is its own inverse, xor(i..j) = prefix[j] ^ prefix[i-1] — exactly parallel to sum(i..j) = prefix[j] - prefix[i-1].

So the whole prefix-sum-plus-hash-map pattern transfers: to count subarrays whose XOR equals k, keep a running prefix XOR and a Counter of seen prefixes, looking up running ^ k. Recognising that XOR behaves like a reversible “sum” opens up a second family of problems.

Practice — real LeetCode problems

LC 136 — Single Number · Easy

Problem. Every element appears twice except for one. Find that one. Your solution must have linear time complexity and use constant extra space.

Constraints. 1 <= len(nums) <= 3 * 10^4, -3 * 10^4 <= nums[i] <= 3 * 10^4, and exactly one element appears once.

Examples. [2,2,1] gives 1 · [4,1,2,1,2] gives 4 · [1] gives 1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

XOR every element into an accumulator seeded at 0. Each duplicated value contributes x ^ x = 0, so only the unpaired value remains.

Time $O(n)$. Space $O(1)$.

The commutativity and associativity matter: they are why you do not need the duplicates to be adjacent, or the array sorted, or the pairs identified. A single pass in any order works.

[-1,-1,5] giving 5 is worth including because XOR on negative numbers can look suspicious. Python’s integers are arbitrary-precision with conceptually infinite sign extension, so -1 ^ -1 == 0 and the identity holds exactly as for positives. In a fixed-width language the two’s-complement bits cancel the same way.

[0,1,0] giving 1 confirms that a 0 in the data is harmless — it is also the accumulator’s identity, so it changes nothing.

Follow-ups you should expect:

• “What if one element appears once and the rest three times (LC 137)?” XOR fails, because three copies do not cancel. Count set bits per position mod 3.
• “Two elements appear once (LC 260)?” Split by a differing bit — next problem.
• “Find the missing number in 0..n (LC 268)?” XOR the indices with the values; or use the sum formula, noting XOR cannot overflow.
• “Find the duplicate without modifying the array (LC 287)?” XOR does not apply — use fast and slow pointers on the index graph.
• “Without XOR at all?” Counter, or 2 * sum(set(nums)) - sum(nums); both $O(n)$ space, so they miss the stated requirement.

LC 260 — Single Number III · Medium

Problem. Exactly two elements appear once; every other element appears twice. Return the two singles in any order. Linear time, constant extra space.

Constraints. 2 <= len(nums) <= 3 * 10^4, and the answer is unique.

Examples. [1,2,1,3,2,5] gives [3,5] (or [5,3]) · [-1,0] gives [-1,0] · [0,1] gives [0,1]

Why this test sorts the output

The problem accepts the pair in any order, so the test sorts before comparing. Returning [5,3] is just as correct as [3,5].

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Folding the array gives a ^ b, which mixes the two answers. To separate them, find a bit where they differ — any set bit of a ^ b qualifies, since a set bit there means the two values disagree at that position.

Partitioning on that bit gives two groups, and both required properties hold:

• Pairs stay intact. Equal values have identical bits, so both copies land in the same group and still cancel.
• a and b separate. They differ at this bit by construction.

So each group reduces to LC 136.

Time $O(n)$ — two passes. Space $O(1)$.

Any set bit works; x & -x just picks the lowest cheaply. xor_all is guaranteed non-zero because a != b (the problem says the two singles are distinct), so there is always at least one bit to pick.

[-1, 0] is the case worth thinking about. -1 ^ 0 = -1, and -1 & 1 = 1, so the lowest set bit is 1. Then -1 has that bit set and 0 does not, so they split correctly. Negative numbers work because Python’s two’s-complement semantics make -1 conceptually all-ones.

Follow-ups you should expect: “Why any differing bit rather than specifically the lowest?” — any works; the lowest is just the cheapest to extract. “What does x & -x do?” — isolates the lowest set bit via two’s complement; be ready to explain it. “Three singles?” — much harder; a single bit no longer partitions them cleanly and you need a more elaborate scheme. “Two singles among triples?” — XOR does not apply at all; count bits with a different modulus.

LC 421 — Maximum XOR of Two Numbers in an Array · Medium

Problem. Return the maximum result of nums[i] ^ nums[j] over all pairs.

Constraints. 1 <= len(nums) <= 2 * 10^5, 0 <= nums[i] <= 2^31 - 1.

Examples. [3,10,5,25,2,8] gives 28 (5 ^ 25) · [14,70,53,83,49,91,36,80,92,51,66,70] gives 127 · [0] gives 0

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Build the answer one bit at a time, starting from the most significant. Higher bits dominate the value, so whenever a 1 is achievable at the current position you should take it — no later bit can compensate for giving it up.

To test achievability, consider only the high bits seen so far: prefixes holds n >> shift for every number. If there exist prefixes p and q with p ^ q == candidate, then candidate is reachable — and since p ^ q == candidate is equivalent to candidate ^ p == q, that is a set membership test rather than a nested loop.

Time $O(32n)$ — 32 bit positions, each doing $O(n)$ set work. Space $O(n)$.

Two details:

• best <<= 1 before testing. It shifts in a trailing 0, so if the candidate fails, best is already correct for this position with a 0 there. No else branch needed.
• 0 must work. [0] gives 0: no pair exists other than the element with itself, and 0 ^ 0 = 0. Note the problem permits i == j, so a single-element array is legal.

The bitwise trie alternative is worth describing: insert each number as a 32-level path of 0/1 children, then for each number walk down always preferring the opposite bit when that child exists, since a differing bit contributes a 1 at that position. Same $O(32n)$, and it extends to variants with extra constraints (LC 1707 restricts which numbers may be paired).

The connection worth naming: “prefix” need not mean a character prefix. Once you see numbers as bit strings, trie techniques apply to a whole family of XOR problems.

Follow-ups you should expect: “Implement it with a trie” — have the structure ready. “Why greedy from the top?” — higher bits outweigh all lower bits combined. “Maximum XOR with a limit on the second number (LC 1707)?” — sort the queries and insert into the trie incrementally. “Minimum XOR pair?” — different: sort the array, and the answer is between adjacent elements.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 137 is here as the counterexample

Single Number II looks like a sibling of 136 and is deliberately included to mark XOR’s boundary. With elements appearing three times, XOR cancels nothing — x ^ x ^ x == x.

The reliable answer is per-bit counting: for each of the 32 positions, count how many numbers have that bit set and take the count mod 3. Whatever remains belongs to the single element. $O(32n)$ time, $O(1)$ space, and it generalises immediately to “appears k times” by changing the modulus.

There is also a two-accumulator trick with ones and twos implementing a mod-3 counter in bit arithmetic. It is shorter but genuinely hard to derive under pressure — know that it exists, and reach for bit counting.

6 problems

3 easy3 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○136Single NumbereasyFold with XOR; $O(1)$ space is the requirementNeetCode 150LeetCode Top Interview 150
• ○268Missing NumbereasyXOR indices with values -- no overflow, unlike the sum formulaNeetCode 150Blind 75
• ○1720Decode XORed ArrayeasyXOR is its own inverse, so just XOR forward
• ○137Single Number IImediumTriples, so **not** XOR -- count bits mod 3LeetCode Top Interview 150
• ○260Single Number IIImedium`x & -x` to split into two LC 136 problems
• ○421Maximum XOR of Two Numbers in an ArraymediumGreedy bit prefixes, or a bitwise trie

Interview follow-ups

They ask	What they’re checking	The answer
“Why does XOR work here?”	The identities	$x \oplus x = 0$ and $x \oplus 0 = x$, plus commutativity, so pairs cancel in any order
“What does x & -x do?”	Bit fluency	Isolates the lowest set bit, via two’s complement (-x is ~x + 1)
“Why is any differing bit enough?”	Rigour	Pairs share all bits so they stay in one group and cancel; a and b differ at that bit so they separate
“What about elements appearing three times?”	Knowing the boundary	XOR fails; count set bits per position mod 3
“Why XOR over the sum formula for LC 268?”	Practical detail	XOR cannot overflow; the sum can in a fixed-width language
“Beat $O(n^2)$ for maximum XOR?”	Depth	Greedy bit prefixes with a set, or a bitwise trie — $O(32n)$
“Count subarrays with XOR = k?”	Composition	Prefix XOR + hash map, exactly like prefix sums, since XOR is its own inverse

Edge-case checklist

• Single element — [1] for LC 136; [0] for LC 421.
• Negative numbers — [-1,-1,5] and [-1,0]; two’s complement makes the identities hold, but test them.
• Zeros in the data — harmless for XOR, since 0 is the identity; [0,1,0] gives 1.
• The two singles differing only in the lowest bit (LC 260) — e.g. [0,1]; x & -x still isolates a valid split bit.
• All elements identical in pairs — the accumulator ends at 0, which is only correct if a 0 really is the single.
• Large values near $2^{31}$ (LC 421) — the loop must cover bit 31.
• i == j permitted (LC 421) — so a one-element array returns 0.
• Assuming XOR handles triples — the classic wrong reflex; it does not.

Self-check

pch.quizTag Bitwise XOR patterns — self-check

1. Which property of XOR makes the single-number problems work?

   A That it is faster than addition B That x ^ x == 0 and x ^ 0 == x, and it is commutative and associative — so pairs cancel regardless of the order they appear in C That it never overflows D That it preserves the sign bit
   pch.quizShowAnswer

   B — That x ^ x == 0 and x ^ 0 == x, and it is commutative and associative — so pairs cancel regardless of the order they appear in — Order-independence is what lets you fold the whole array in one pass. In the dry run the 1s cancel mid-stream, long before the array ends.

2. In LC 260 (two singles), why partition on a set bit of `a ^ b`?

   A To sort the array B Because the set bits of a ^ b are exactly the positions where a and b differ, so partitioning on any one of them puts them in different groups — while equal numbers have equal bits, so no pair is ever split C Because the lowest bit is always 1 D To reduce the array size by half
   pch.quizShowAnswer

   B — Because the set bits of a ^ b are exactly the positions where a and b differ, so partitioning on any one of them puts them in different groups — while equal numbers have equal bits, so no pair is ever split — Both halves of that argument are needed: the singles separate, AND the pairs stay together so cancellation still works inside each group. The second half is the one people omit.

3. Why does `x & -x` isolate the lowest set bit?

   A Because negation reverses the bit order B Because in two's complement -x is ~x + 1, which leaves every bit below the lowest set bit as 0, that bit as 1, and everything above inverted — so the AND keeps exactly one bit C Because -x is always a power of two D It does not; it clears the lowest set bit
   pch.quizShowAnswer

   B — Because in two's complement -x is ~x + 1, which leaves every bit below the lowest set bit as 0, that bit as 1, and everything above inverted — so the AND keeps exactly one bit — 12 & -12 = 4 (1100 → 0100). The same idiom is how a Fenwick tree walks its index structure, so it is worth owning rather than memorising.

4. The array has one single and everything else appears THREE times (LC 137). Does XOR still work?

   A Yes, unchanged B No — three copies XOR to the value itself rather than to zero, so nothing cancels. Count set bits per position mod 3, or use the two-accumulator mod-3 counter C Yes, if you XOR three times D Yes, after sorting
   pch.quizShowAnswer

   B — No — three copies XOR to the value itself rather than to zero, so nothing cancels. Count set bits per position mod 3, or use the two-accumulator mod-3 counter — XOR's power comes specifically from pairs. When the multiplicity changes, the tool changes — knowing the boundary is more useful than the trick itself.

5. A hash set also solves LC 136 in O(n) time. Why is XOR the expected answer?

   A It is asymptotically faster B Because it uses O(1) space, which is exactly what the standard follow-up asks for — mention the set solution first, then improve it C Because sets cannot hold duplicates D Because XOR handles negative numbers and sets do not
   pch.quizShowAnswer

   B — Because it uses O(1) space, which is exactly what the standard follow-up asks for — mention the set solution first, then improve it — Both are O(n) time. The problem is really testing whether you can get to constant space, so leading with the set and then improving reads better than jumping straight to the trick.

6. You port an XOR bit-manipulation solution to Python and it loops or returns huge numbers. Why?

   A Python's XOR operator differs from C's B Python integers have arbitrary precision, so `~x` is -x-1 with infinitely many leading 1s rather than a 32-bit complement — mask with `x & 0xFFFFFFFF` and convert back if the result exceeds 2^31 C Because Python has no unsigned ints, XOR is undefined D Because the input contains negative numbers
   pch.quizShowAnswer

   B — Python integers have arbitrary precision, so `~x` is -x-1 with infinitely many leading 1s rather than a 32-bit complement — mask with `x & 0xFFFFFFFF` and convert back if the result exceeds 2^31 — The identities themselves are width-independent, so LC 136/260/268 are fine. It bites on LC 371, LC 190 and signed inputs — a Python-specific follow-up worth pre-empting.

Recall card

• Cue — “every element appears twice except…”, “find the missing/duplicate number”, “the extra character”, or a problem asking for $O(1)$ space where a hash set would be the obvious answer.
• The four identities — x ^ x = 0, x ^ 0 = x, commutative, associative. Pairs cancel regardless of order, which is why one accumulator and one pass suffice.
• LC 136 — fold the whole array with ^.
• LC 268 — XOR the indices 0..n and the values; everything pairs off but the missing one.
• LC 260 (two singles) — XOR everything to get a ^ b, isolate any differing bit with x & -x, partition on it, then XOR each group. Pairs stay intact because equal numbers have equal bits.
• x & -x isolates the lowest set bit (two’s complement: ~x + 1). Also how a Fenwick tree walks.
• Boundary — three-of-a-kind (LC 137) is not XOR: count bits per position mod 3.
• Cost — $O(n)$ time, $O(1)$ space; that space bound is the reason the problem is asked.
• Python — mask with 0xFFFFFFFF when a problem assumes 32-bit signed wrap (LC 371, LC 190).

Recap

• XOR is a self-cancelling accumulator: $x \oplus x = 0$, $x \oplus 0 = x$, and it is commutative and associative. Folding an array leaves exactly what appears an odd number of times, in $O(1)$ space.
• For two singles, XOR everything to get a ^ b, isolate any set bit with x & -x, and partition — pairs stay together and cancel, while a and b separate. Then it is LC 136 twice.
• x & -x isolates the lowest set bit through two’s complement; it also drives Fenwick trees.
• XOR’s power comes from pairs. For triples, count set bits mod 3 instead.
• Prefer XOR over sum formulas when overflow is a concern.
• “Prefix” can mean bit prefix: greedy top-down bit construction or a bitwise trie turns maximum-XOR from $O(n^2)$ into $O(32n)$.
• Because XOR is its own inverse, prefix XOR behaves like prefix sums, and the prefix-plus-hash-map pattern transfers directly.

Next: Number Theory for Competitive Programming — primes, modular arithmetic, and the identities worth having memorised.