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
- Bitwise Operations & Trie (Binary Trie for pairwise max XOR).