AntInLoop

XOR Properties, Tricks & Linear Basis

Bitwise XOR is self-inverse (x ^ x = 0), associative, and commutative—solving single/two unique number detection, missing number, prefix-XOR queries, and maximum subset XOR (XOR basis) in linear time.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

XOR Properties, Tricks & Linear Basis

Bitwise XOR (^) satisfies four algebraic laws that make it a superpower in algorithms:

1. Self-Inverse: $x \oplus x = 0$

2. Identity: $x \oplus 0 = x$

3. Commutative & Associative: order doesn't matter!

4. Range Invertibility: $\text{XOR}(l, r) = \text{pref}[r + 1] \oplus \text{pref}[l]$!

Practice Problems

Easy

1. Single Number III — Two Unique Numbers in $O(n)$ Time and $O(1)$ Space (LeetCode 260)

Every number in nums appears twice except two unique numbers a and b. Find a and b in $O(n)$ time and $O(1)$ space!

Approach: XOR all elements to get diff = a ^ b. Isolate any set bit lsb = diff & -diff (where a and b differ!), partition all elements into two groups by x & lsb, and XOR each group separately to recover a and b!

<details>

<summary>Show C++ Solution</summary>

#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

std::pair<int, int> singleNumberIII(const std::vector<int>& nums) {
    uint32_t diff = 0;
    for (int x : nums) diff ^= static_cast<uint32_t>(x);
    uint32_t lsb = diff & (~diff + 1); // safe unsigned lowest set bit
    int a = 0, b = 0;
    for (int x : nums) {
        if (static_cast<uint32_t>(x) & lsb) a ^= x;
        else b ^= x;
    }
    return {a, b};
}

int main() {
    auto [a, b] = singleNumberIII({1, 2, 1, 3, 2, 5});
    std::cout << a << " " << b << "\n"; // 3 5 (or 5 3)
    return 0;
}

</details>

Hard

2. Maximum Subset XOR via XOR Linear Basis (Gaussian Elimination over $\mathbb{F}_2$)

Given an array of non-negative integers, find the maximum possible XOR of any subset of elements in $O(31 \cdot n)$ time!

Approach: Maintain a 31-element basis[0..30] where basis[b] has MSB at bit b. Insert each x by reducing it against existing basis vectors from bit 30 down to 0. Finally, greedily XOR ans with basis[b] whenever (ans ^ basis[b]) > ans! Time: $O(n \log(\max))$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

int maxSubsetXOR(const std::vector<int>& nums) {
    std::array<int, 31> basis{};
    for (int x : nums) {
        for (int b = 30; b >= 0; --b) {
            if (!((x >> b) & 1)) continue;
            if (!basis[b]) { basis[b] = x; break; }
            x ^= basis[b];
        }
    }
    int ans = 0;
    for (int b = 30; b >= 0; --b) ans = std::max(ans, ans ^ basis[b]);
    return ans;
}

int main() {
    std::cout << maxSubsetXOR({9, 8, 5}) << " " << maxSubsetXOR({2, 4, 5}) << "\n"; // 13 7
    return 0;
}

</details>

---

Related Algorithms