cf.completefrontend
BIT MANIPULATION · CORE

XOR tricks

Use the facts that x ^ x = 0 and x ^ 0 = x to cancel out pairs and find the value that is left over.

Time O(n)Space O(1)4 practice problemsStep-through picture

The idea

XOR, written ^, compares two numbers bit by bit and gives 1 where the bits differ. It has three properties that make it very useful: x ^ x = 0 (a number cancels itself), x ^ 0 = x (zero changes nothing), and the order doesn't matter (a ^ b ^ a equals a ^ a ^ b).

So if you XOR together a list where every value appears twice except one, every pair cancels to 0 and only the unpaired value survives. That finds it in one pass with no extra memory, while a hash map would need memory for every value.

The same idea finds a missing number. XOR together all the numbers 0 to n and all the numbers in the list. Every number that is present appears twice and cancels; the missing one appears once and remains.

An everyday example

A light switch pressed by many people

A room has a light that starts off. Every visitor who walks in presses the switch once. Each pair of visitors with the same name presses it twice, which leaves it as it was. At the end, the light is on only if some name came in an odd number of times. XOR works the same way on every bit at once, and the bits that are left on spell out the unpaired value.

How the example maps to the code
In the exampleIn the code
The light, starting offlet acc = 0
A visitor pressing the switchacc ^= num
Two presses cancel outx ^ x === 0
What's on at the endthe unpaired value in acc

From the slow way to xor tricks

  1. Start with the obvious way to find the value without a partner: count every value in a Map, then look for the count that is 1. That's O(n) time, but also O(n) memory, one entry per distinct value. Sorting and checking neighbors uses no extra memory but costs O(n log n).
  2. XOR has three facts that fit this problem exactly. A value XORed with itself is 0: x ^ x = 0. XOR with 0 changes nothing: x ^ 0 = x. And the order and grouping don't matter: a ^ b ^ a equals (a ^ a) ^ b. So a value and its copy cancel out wherever they are in the list.
  3. That means XORing the whole list together is the same as pairing every value with its copy first. Every pair becomes 0, and what's left is the one value without a partner. One running number, acc, is all the memory needed.
  4. The missing-number problem can be turned into the same shape. XOR every value that should be there, 0 to n, together with every value that is there. Present values now appear twice and cancel; the missing value appears once. The indexes 0 to n - 1 supply most of the expected values, and starting acc at n supplies the last. Those loops are the XOR tricks.

How it works

  1. Start with acc = 0.
  2. For each number in the list, set acc ^= num.
  3. Pairs cancel to 0 no matter where they appear, because XOR order doesn't matter.
  4. After the loop, acc holds the value that had no partner.
  5. For a missing number in 0 to n: start with acc = n and XOR in each index i and each value nums[i]. What remains is the missing number.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function findUnpaired(nums) {
  2. let acc = 0;
  3. for (const num of nums) {
  4. acc ^= num;
  5. }
  6. return acc;
  7. }
  9. function findMissing(nums) {
  10. let acc = nums.length;
  11. for (let i = 0; i < nums.length; i++) {
  12. acc ^= i ^ nums[i];
  13. }
  14. return acc;
  15. }

How fast it is

TimeO(n)
Extra memoryO(1)

One pass over the list with one XOR per item, and only one number is stored.

  • Best caseO(n)

    Any list: every number must be read, because the last one can still change the answer. There's no early exit.

  • Average caseO(n)

    One XOR per item for findUnpaired, and two per item for findMissing.

  • Worst caseO(n)

    The same for every list of length n, whatever the values.

Common mistakes

  • Using XOR when a value can appear three times. Three copies leave one copy behind, so the answer is wrong. Count bits per position instead.
  • Starting acc at something other than 0 (or n for the missing-number version).
  • Using XOR on numbers above 2^32. JavaScript cuts them to 32 bits first. Use BigInt for larger values.
  • Writing a ^ b to mean a power. In JavaScript ^ is XOR; powers use ** or Math.pow.

When to use it

Look for these clues in a problem:

  • Every value appears twice (or an even number of times) except one.
  • One number from a range like 0 to n is missing.
  • The problem asks for O(1) extra memory where a hash set would be the usual tool.
  • The question mentions "differs", "toggle", parity, or comparing two bit patterns.

Check yourself

Answer each one in your head first, then open it.

After XORing 12 and 7, acc is 11. What does 11 mean?

Nothing on its own. It's a mix of both values. Only after the whole list is processed does acc equal the unpaired value.

What does findUnpaired([5, 5, 5, 8]) return?

13, which is 5 ^ 8. The third 5 has no partner, so the list breaks the "pairs" promise and the result is meaningless.

Why does findMissing start acc at nums.length instead of 0?

The range of expected values is 0 to n, but the indexes only go up to n - 1. Starting at n adds the one expected value the loop doesn't cover.

Why can't the loop stop early when acc becomes 0, as it did at i = 2?

A 0 only means the values so far cancel. The next items can still add new bits, as i = 3 did, turning acc into 2.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Look at one bit position at a time. XOR of a group of bits is 1 exactly when an odd number of them are 1. A value that appears twice adds the same bit twice, either two 0s or two 1s, which never changes odd into even. So at every position, the bit of acc matches the bit of the one value that appears an odd number of times.

findUnpaired keeps a simple promise: after each step, acc is the XOR of every number seen so far. When the loop ends, acc is the XOR of the whole list. Because order doesn't matter, that equals XORing each pair first, giving 0 for each, and then the unpaired value, so acc is that value.

findMissing XORs together n, every index 0 to n - 1, and every value in nums. The first two groups together are exactly 0 to n. Every value present in nums appears once in that range and once in nums, so it cancels. The missing value appears only in the range, so it's what remains.

Going deeper

3 more ideas

Why pairs vanish

Look at one bit position. Each number either has a 1 there or not. XOR of many bits is 1 exactly when an odd number of them are 1. A value that appears twice adds two equal bits, which doesn't change odd or even. So each bit of acc ends up equal to that bit of the unpaired value.

Two unpaired values

If two values a and b appear once each, XOR of everything gives a ^ b. It isn't 0, since a !== b, so it has some bit set; take the lowest one with x & -x. That bit is on in exactly one of a and b. Split the list by that bit and XOR each group separately: each group holds one of the two values plus whole pairs.

XOR's other uses

a ^ b shows which bits differ between two masks, so counting its 1 bits gives how many flags changed. XOR with a mask flips exactly those bits, which is the toggle operation for flags. XOR is also used inside hash functions to mix bits together.

Work it by hand

Every step in a table, with why

Find the unpaired value in [12, 7, 9, 7, 12], then the missing value in [3, 0, 4, 1].

findUnpaired([12, 7, 9, 7, 12]), then findMissing([3, 0, 4, 1])

StepXOR inaccacc in binaryWhat happensWhy
1-00000findUnpaired startsacc starts at 0, which changes nothing when XORed in.
2121211000 ^ 12acc is just 12 now.
3711101112 ^ 71100 ^ 0111 = 1011. This middle value means nothing on its own; only the final value does.
492001011 ^ 91011 ^ 1001 = 0010.
57501012 ^ 7: the 7s cancelThe second 7 removes the first 7's bits. What's left is 12 ^ 9 = 5.
612910015 ^ 12: the 12s cancelThe second 12 cancels the first. Only 9 remains. findUnpaired returns 9.
7-40100findMissing starts at nums.lengthThe list has 4 numbers, so the full range is 0 to 4. The loop's indexes cover 0 to 3; starting at 4 covers the last value.
80 ^ 3 = 370111i = 0Index 0 and value 3 both go in.
91 ^ 0 = 160110i = 1Index 1 and value 0. So far 4, 0, 3, 1, 0 are in: the two 0s cancel.
102 ^ 4 = 600000i = 2The 4 from the start cancels the value 4. acc happens to be 0 now, but the loop isn't done.
113 ^ 1 = 220010i = 3The 3s and 1s cancel. Only index 2 has no matching value. findMissing returns 2.

findUnpaired returns 9 and findMissing returns 2. Each did one XOR per item and kept one number, and neither could stop early: the last item can always change the answer.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
XOR tricksO(n)O(1)Values come in pairs except one, or one value of a known range is missing, and memory matters.
Count with a MapO(n)O(n)Values can appear any number of times, or you need the counts themselves.
Sort, then check neighborsO(n log n)O(1)You may reorder the list and also need it sorted for something else.
Sum formula for the missing numberO(n)O(1)Equally good for the missing number: n × (n + 1) / 2 minus the sum. In JavaScript it's exact up to 2^53, far past any list that fits in memory.

Extra memory: O(1): one number, acc, compared with O(n) for a Map of counts.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for XOR tricks and the other approaches, on a scale where each line up is 10 times more steps.
  • XOR tricks, Count with a Map, Sum formula for the missing number O(n)
  • Sort, then check neighbors O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
XOR tricks101,0001 million
Count with a Map101,0001 million
Sort, then check neighbors339,96620 million
Sum formula for the missing number101,0001 million

Inputs that need care

5 tricky inputs
An empty list: findUnpaired([])
Returns 0, which can't be told apart from a real unpaired 0. Only use it when the problem promises exactly one unpaired value. findMissing([]) returns 0, which is right: the range is just 0.
The unpaired value is 0: [0, 4, 4]
Returns 0, correctly, but it looks the same as "nothing was left". That's fine as long as the input is guaranteed to have one unpaired value.
A value three times: [5, 5, 5, 8]
Three 5s leave one 5 behind, so it returns 5 ^ 8 = 13, a number that isn't in the list. XOR only cancels pairs; for "every value appears three times", count each bit position modulo 3 instead.
Negative numbers: [-3, 8, 8]
Works: XOR acts on the 32-bit two's complement bits, and the 8s cancel, leaving -3.
Values above 2^32: [2 ** 32 + 5]
Returns 5: the high bits are cut off before XOR runs. Use BigInt values and ^ on them for numbers this large.

Variations and follow-ups

Twists interviewers add

Two unpaired values

XOR of everything gives a ^ b, which isn't 0. Take its lowest set bit with x & -x: a and b differ there. Split the list by that bit and XOR each group. For [12, 7, 9, 7, 12, 20], the total is 29, the lowest bit is 1, and the groups give 9 and 20.

Every value three times except one

For each of the 32 bit positions, count how many numbers have a 1 there. Counts from tripled values are multiples of 3, so count % 3 at each position is the bit of the single value.

Range XOR with prefixes

Store prefix[i], the XOR of the first i items. The XOR of items l to r is prefix[r + 1] ^ prefix[l], because the shared part cancels. It's like prefix sums, with XOR as both adding and subtracting.

Swapping without a temporary

a ^= b; b ^= a; a ^= b; swaps two numbers. It's a fun fact more than a tool: [a, b] = [b, a] is clearer, and the XOR swap sets both to 0 if a and b are the same variable.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "every element appears twice except one", "one number from 0 to n is missing", "find the duplicate", or "use constant extra space".
  • Explain it with the three facts: "x ^ x is 0, x ^ 0 is x, and order doesn't matter, so all the pairs cancel and the single value is left."
  • Test a list of one item, an unpaired value at the start and at the end, and a negative number. Also say what happens if the promise is broken, such as a value appearing three times.
  • The usual follow-up is "two values appear once". Explain the split on the lowest set bit of a ^ b, and why that bit separates a from b.

Where frontend code uses it

The same idea in real UI code
  • Toggling a flag in a bit mask, such as a selected state or a theme option, is flags ^= FLAG.
  • Comparing two permission masks with before ^ after gives exactly the permissions that changed, which an audit log can list.
  • Hash functions used for cache keys, such as FNV-1a, mix each byte into the hash with XOR before multiplying.

Related algorithms