XOR Patterns

March 2026 · 30 min read

XOR is the most versatile bitwise operator. Its unique mathematical properties enable elegant solutions to problems that seem impossible at first glance. This post catalogs every important XOR pattern you will encounter.

The Properties of XOR

a ^ 0 = a          // identity: XOR with 0 does nothing
a ^ a = 0          // self-inverse: any value XOR itself is 0
a ^ b = b ^ a      // commutative
(a ^ b) ^ c = a ^ (b ^ c)  // associative
a ^ b ^ b = a      // cancellation: XOR twice cancels out

Formally, $(\mathbb{Z}/2)^n$ under XOR is an abelian group: $a \oplus 0 = a$, $a \oplus a = 0$, $a \oplus b = b \oplus a$, $(a \oplus b) \oplus c = a \oplus (b \oplus c)$. Every element is its own inverse, which is why "XOR everything" works as a fold.

The cancellation property is the key to everything. If you XOR all elements together, duplicates cancel in pairs and only unpaired elements survive.

Pattern 1: Find the Single Unique Element

Problem: Every element appears twice except one. Find the unique element in O(n) time, O(1) space.

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int n : nums) {
        result ^= n;
    }
    return result;
}
// Example: [4, 1, 2, 1, 2]
// 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4

▶ Finding the Unique Element with XOR

Watch duplicates cancel as we XOR through the array.

Pattern 2: Find Two Unique Elements

Problem: Every element appears twice except two. Find both unique elements.

pair<int,int> twoUnique(vector<int>& nums) {
    // Step 1: XOR all → get a ^ b (the two uniques XORed)
    int xorAll = 0;
    for (int n : nums) xorAll ^= n;

    // Step 2: Find any set bit in xorAll (a and b differ here)
    int diffBit = xorAll & (-xorAll);  // lowest set bit

    // Step 3: Partition into two groups by that bit
    int a = 0, b = 0;
    for (int n : nums) {
        if (n & diffBit) a ^= n;
        else              b ^= n;
    }
    return {a, b};
}
// The diff bit separates a and b into different groups.
// Within each group, duplicates still cancel, leaving the unique.

Pattern 3: Missing Number

Problem: Given n numbers from 0 to n with one missing, find the missing number.

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int result = n;  // start with n (the last index)
    for (int i = 0; i < n; ++i) {
        result ^= i ^ nums[i];
    }
    return result;
}
// XOR all indices with all values. Paired values cancel.
// The missing number has no pair, so it survives.

// Example: nums = [3, 0, 1], missing = 2
// 3 ^ (0^3) ^ (1^0) ^ (2^1) = 3^0^3^1^0^2^1 = 2

Pattern 4: Every Element Appears Three Times Except One

int singleNumber3(vector<int>& nums) {
    int ones = 0, twos = 0;
    for (int n : nums) {
        ones = (ones ^ n) & ~twos;
        twos = (twos ^ n) & ~ones;
    }
    return ones;
}
// This circuit simulates a modulo-3 counter for each bit.
// 'ones' tracks bits seen once, 'twos' tracks bits seen twice.
// After three, both reset to 0. Only the unique element remains in 'ones'.

Alternative (bit-by-bit count mod 3). Conceptually simpler, and generalises to "appears k times except one". For each of the 32 bit positions, count how many input numbers have that bit set, then take that count mod 3. Bits where the unique element is 1 produce remainder 1; everything else cancels:

int singleNumber3_modk(vector<int>& nums) {
    int ans = 0;
    for (int b = 0; b < 32; ++b) {
        int s = 0;
        for (int n : nums) s += (n >> b) & 1;
        if (s % 3) ans |= (1 << b);
    }
    return ans;
}
// O(32 * N) time, O(1) space. Swap the 3 for any k ≥ 2.

Pattern 5: XOR Swap

void xor_swap(int& a, int& b) {
    if (&a == &b) return;  // MUST check: aliased pointers break it
    a ^= b;   // a = a_orig ^ b_orig
    b ^= a;   // b = b_orig ^ (a_orig ^ b_orig) = a_orig
    a ^= b;   // a = (a_orig ^ b_orig) ^ a_orig = b_orig
}

Pattern 6: XOR Linked List

Each node stores prev XOR next instead of two separate pointers. This halves the pointer storage, but makes the list harder to work with:

struct XORNode {
    int data;
    XORNode* both;  // prev ^ next
};
// To traverse forward: next = prev ^ current->both
// To traverse backward: prev = next ^ current->both

Pattern 7: Gray Code

A Gray code is a binary sequence where consecutive values differ by exactly one bit. Converting between binary and Gray code uses XOR:

// Binary to Gray code:
uint32_t to_gray(uint32_t n) {
    return n ^ (n >> 1);
}

// Gray code to binary:
uint32_t from_gray(uint32_t gray) {
    uint32_t n = gray;
    while (gray >>= 1) n ^= gray;
    return n;
}

// Generate all n-bit Gray codes:
vector<int> grayCode(int n) {
    vector<int> result;
    for (int i = 0; i < (1 << n); ++i) {
        result.push_back(i ^ (i >> 1));
    }
    return result;
}
// n=3: [0,1,3,2,6,7,5,4] = [000,001,011,010,110,111,101,100]

Pattern 8: XOR Prefix Array

// XOR of a range [l, r] in O(1):
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
    prefix[i + 1] = prefix[i] ^ arr[i];
}
int xor_range = prefix[r + 1] ^ prefix[l];
// Just like prefix sums, but with XOR instead of addition

Pattern 9: XOR of `1..n` in O(1)

The XOR of $1 \oplus 2 \oplus \cdots \oplus n$ has a neat closed form because XORs of four consecutive integers starting from a multiple of 4 always cancel:

uint32_t xor_1_to_n(uint32_t n) {
    switch (n % 4) {
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        case 3: return 0;
    }
    return 0;
}
// Range [l..r]: xor_1_to_n(r) ^ xor_1_to_n(l - 1).
// Why: 4k ^ (4k+1) ^ (4k+2) ^ (4k+3) = 0 for any k ≥ 0.

Pattern 10: Maximum XOR Pair via Trie (LC 421)

Given an array, find $\max_{i,j} a_i \oplus a_j$. A binary trie over the 32-bit representations lets us answer each query greedily in O(32) by walking from the most-significant bit and preferring the opposite child whenever it exists:

struct Trie {
    Trie* nxt[2] = {nullptr, nullptr};
};
void insert(Trie* root, int x) {
    Trie* c = root;
    for (int b = 30; b >= 0; --b) {
        int bit = (x >> b) & 1;
        if (!c->nxt[bit]) c->nxt[bit] = new Trie();
        c = c->nxt[bit];
    }
}
int queryMax(Trie* root, int x) {
    Trie* c = root; int best = 0;
    for (int b = 30; b >= 0; --b) {
        int bit = (x >> b) & 1, want = bit ^ 1;
        if (c->nxt[want]) { best |= (1 << b); c = c->nxt[want]; }
        else                c = c->nxt[bit];
    }
    return best;
}
// findMaximumXOR: insert all, then query each → O(N · 32). Same trick
// powers LC 1707 (offline + sort + Trie) and LC 1803 (count XOR in range).

Pattern 11: Symmetric Difference of Bitmask Sets

If two sets of integers in [0, 63] are encoded as uint64_t bitmasks, then:

uint64_t A, B;
uint64_t intersect = A & B;          // A ∩ B
uint64_t unite     = A | B;          // A ∪ B
uint64_t sym_diff  = A ^ B;          // A △ B  (in exactly one)
uint64_t a_minus_b = A & ~B;         // A \ B
// Counting cardinalities is just __builtin_popcountll on the result.
// This is the bedrock trick of every "subset DP over up to 20 items" CP problem.

Pattern 12: XOR Linear Basis (CP)

To answer queries like "max subset XOR" or "is value x expressible as a XOR of a subset?", maintain a Gaussian basis over $\mathbb{F}_2^{64}$. Each new number is reduced against existing basis vectors by their highest set bit; if anything is left, it joins the basis. The size of the basis is at most 64, so all operations are O(64) per insert/query.

struct Basis {
    uint64_t b[64] = {};
    void insert(uint64_t x) {
        for (int i = 63; i >= 0; --i) if ((x >> i) & 1) {
            if (!b[i]) { b[i] = x; return; }
            x ^= b[i];
        }
    }
    uint64_t maxXor() const {
        uint64_t r = 0;
        for (int i = 63; i >= 0; --i)
            if ((r ^ b[i]) > r) r ^= b[i];
        return r;
    }
};
// Used in Codeforces problems like 845G, 724G, and the classic "max subset XOR"
// (GeeksforGeeks). Combine with offline DSU/segment tree for harder variants.

Summary

XOR cancellation (a ^ a = 0) is the foundation of all XOR tricks.
Single unique: XOR all elements. Duplicates cancel.
Two unique: XOR all to get a^b, then partition by a differing bit.
Missing number: XOR indices with values. The missing one survives.
Three times unique: Simulate a mod-3 counter per bit.
Gray code: n ^ (n >> 1). Consecutive values differ by one bit.
XOR prefix: Enables O(1) range XOR queries.
XOR of 1..n: closed-form by n % 4: n, 1, n+1, 0.
Max XOR pair: binary Trie + greedy MSB-first walk (LC 421).
Linear basis: Gaussian elimination over $\mathbb{F}_2$ for max-subset-XOR queries.
Bitmask sets: & = ∩, | = ∪, ^ = △, & ~ = setminus.

Practice Problems

Worked roughly easy → hard. The last two are the standard XOR-Trie capstones.

LC 136 · Single Number Easy — classic XOR fold.
LC 137 · Single Number II Medium — bit-count mod 3 (or the ones/twos circuit).
LC 260 · Single Number III Medium — split mask via lowest set bit.
LC 268 · Missing Number Easy — XOR identities and indices.
LC 421 · Maximum XOR of Two Numbers in an Array Medium — binary Trie / bit-greedy.
LC 1310 · XOR Queries of a Subarray Medium — XOR prefix array.
LC 1442 · Count Triplets That Can Form Two Arrays of Equal XOR Medium — XOR prefix + counting prefix[i] == prefix[k+1].
LC 1707 · Maximum XOR With an Element From Array Hard — offline by query limit + persistent / sorted-insert Trie.

XOR Patterns

The Properties of XOR

Pattern 1: Find the Single Unique Element

▶ Finding the Unique Element with XOR

Pattern 2: Find Two Unique Elements

Pattern 3: Missing Number

Pattern 4: Every Element Appears Three Times Except One

Pattern 5: XOR Swap

Pattern 6: XOR Linked List

Pattern 7: Gray Code

Pattern 8: XOR Prefix Array

Pattern 9: XOR of 1..n in O(1)

Pattern 10: Maximum XOR Pair via Trie (LC 421)

Pattern 11: Symmetric Difference of Bitmask Sets

Pattern 12: XOR Linear Basis (CP)

Summary

Practice Problems

Pattern 9: XOR of `1..n` in O(1)