XOR Tricks

Two Unique Numbers

If TWO numbers are unique (all others appear twice), XOR all to get their combined XOR. Find any set bit in the result — that bit differs between the two numbers. Split all elements into two groups by that bit and XOR each group.

O(n)

O(1)

How It Works

When exactly two values appear once and everything else appears twice, XORing the whole array yields x ^ y — the two uniques combined, with all pairs cancelled. That result must be nonzero, so it has at least one set bit, and any set bit marks a position where x and y differ. Isolate the lowest such bit with diff & (-diff).

Now partition: XOR together all elements that have that bit set, and separately all elements that do not. Each duplicate pair lands entirely in one group and cancels there, while x and y are guaranteed to fall into different groups. Each group's XOR therefore collapses to one of the two answers. Two linear passes (or one, with two accumulators), O(n) time, O(1) space — matching Single Number's efficiency where a hash map would spend O(n) memory.

Step-by-Step Visualization

Two unique numbers in [1,2,1,3,2,5]

XOR all3 ⊕ 5 = 6 (110)

1/3

Code

Java

static int[] singleNumberIII(int[] nums) {
  int xor = 0;
  for (int n : nums) xor ^= n;

  int bit = xor & (-xor); // Lowest set bit
  int a = 0, b = 0;
  for (int n : nums) {
    if ((n & bit) != 0) a ^= n;
    else b ^= n;
  }
  return new int[]{a, b};
}

Tips & Gotchas

1XOR all to get a⊕b. Find a set bit to split numbers into two groups

2Each group XORed separately gives one unique number

3The set bit means a and b differ at that position

Practice Problems

1Single Number III
2Maximum XOR of Two Numbers in an Array
3Decode XORed Array

About the XOR Tricks Pattern

XOR has a magical property: a ⊕ a = 0 and a ⊕ 0 = a. So if you XOR all elements in a list where every element appears twice except one, all pairs cancel out and the unique element survives.

Key insight

Key tricks: n & (n−1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.

Common Bit Manipulation Interview Problems

Single Number
Number of 1 Bits
Counting Bits
Missing Number
Reverse Bits
Power of Two

Frequently Asked Questions

Why are the two unique numbers guaranteed to end up in different groups?

The partition bit is chosen from x ^ y, meaning x and y disagree at that exact position — one has the bit set and the other does not. Splitting on that bit therefore separates them by construction, while every duplicate pair shares identical bits and stays together.

What does diff & (-diff) compute and why use it?

In two's complement, ANDing a number with its negation isolates its lowest set bit. Any set bit of the combined XOR would work as the partition key; the lowest one is simply the cheapest to extract in a single expression without a loop.