Loading learning content...
In the realm of bitwise operations, XOR (Exclusive OR) stands apart as perhaps the most elegant and powerful operator. While AND, OR, and NOT have intuitive logical interpretations, XOR possesses a mathematical property so profound that it enables solutions to problems that seem to require extra memory—with no memory at all.
Imagine this challenge: Given an array of numbers where every number appears exactly twice except for one number that appears only once, find that single number. The naive solution uses a hash set and O(n) extra space. But with XOR, you can solve this in O(1) space—using a single integer variable.
This isn't magic; it's the self-cancellation property of XOR, and understanding it deeply will unlock an entire category of algorithmic techniques.
By the end of this page, you will understand the mathematical foundations of XOR, grasp the self-cancellation property at an intuitive level, and recognize why XOR enables constant-space solutions for detection problems that traditionally require hash tables or sorting.
Before diving into the self-cancellation property, let's establish a rock-solid understanding of what XOR actually does at the bit level. XOR compares two bits and returns 1 if and only if exactly one of the bits is 1.
The XOR Truth Table:
| A | B | A ⊕ B | Interpretation |
|---|---|---|---|
| 0 | 0 | 0 | Both bits are the same (both off) |
| 0 | 1 | 1 | Bits are different |
| 1 | 0 | 1 | Bits are different |
| 1 | 1 | 0 | Both bits are the same (both on) |
The key insight: XOR returns 1 when the inputs differ and 0 when they are the same. This is fundamentally a difference detector. In contrast:
This difference-detection property is what gives XOR its unique characteristics.
A useful mental model: XOR is like asking "Are these two bits different?" If yes, the result is 1. If no, the result is 0. This perspective helps when reasoning about XOR chains and cancellation.
XOR has several mathematical properties that make it uniquely suited for algorithmic applications. Understanding these properties deeply is essential for recognizing when XOR can solve a problem elegantly.
Property 1: Commutativity
A ⊕ B = B ⊕ A
The order of operands doesn't matter. Just like addition, you can swap the operands freely.
Property 2: Associativity
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
Grouping doesn't matter. This means we can XOR a sequence of values in any order and get the same result.
Property 3: Identity Element
A ⊕ 0 = A
XORing with 0 leaves the value unchanged. Zero is the identity element, just as it is for addition.
Property 4: Self-Inverse (The Star Property)
A ⊕ A = 0
This is the critical property. XORing any value with itself produces 0. This is the self-cancellation property that unlocks everything.
12345678910111213141516171819202122232425262728
# Demonstrating XOR properties # Property 1: Commutativity (A ⊕ B = B ⊕ A)a, b = 5, 3print(f"Commutativity: {a} ^ {b} = {a ^ b}, {b} ^ {a} = {b ^ a}")# Output: 5 ^ 3 = 6, 3 ^ 5 = 6 # Property 2: Associativity ((A ⊕ B) ⊕ C = A ⊕ (B ⊕ C))a, b, c = 5, 3, 7print(f"Associativity: ({a} ^ {b}) ^ {c} = {(a ^ b) ^ c}")print(f"Associativity: {a} ^ ({b} ^ {c}) = {a ^ (b ^ c)}")# Both produce 1 # Property 3: Identity (A ⊕ 0 = A)a = 42print(f"Identity: {a} ^ 0 = {a ^ 0}")# Output: 42 ^ 0 = 42 # Property 4: Self-Inverse (A ⊕ A = 0)a = 42print(f"Self-Inverse: {a} ^ {a} = {a ^ a}")# Output: 42 ^ 42 = 0 # The magic: Combining properties# A ⊕ B ⊕ A = B (because A ⊕ A = 0, and B ⊕ 0 = B)a, b = 17, 99result = a ^ b ^ aprint(f"Combined: {a} ^ {b} ^ {a} = {result}") # Output: 99The self-cancellation property (A ⊕ A = 0) is where XOR's power truly shines. Let's understand this at a deep level.
Why does A ⊕ A = 0?
Think about it bit by bit. For any bit position:
Every bit, regardless of its value, produces 0 when XORed with itself. This is because XOR asks "are these different?" and a bit is never different from itself.
The Chain Reaction
Combining self-cancellation with associativity creates a powerful chain reaction. Consider XORing a sequence where some values appear twice:
1234567891011121314151617181920212223242526
# The Chain Reaction: XOR cancels duplicates # Example array: [2, 3, 2, 4, 3]# 2 appears twice, 3 appears twice, 4 appears once # Let's XOR all elements step by steparr = [2, 3, 2, 4, 3] result = 0print("Step-by-step XOR:")for num in arr: old_result = result result ^= num print(f" {old_result:3} ^ {num} = {result:3} (binary: {bin(old_result)} ^ {bin(num)} = {bin(result)})") print(f"\nFinal result: {result}") # Let's trace what happened mathematically:# result = 2 ^ 3 ^ 2 ^ 4 ^ 3## By commutativity and associativity, we can rearrange:# result = (2 ^ 2) ^ (3 ^ 3) ^ 4# result = 0 ^ 0 ^ 4# result = 4## The duplicates cancelled out, leaving only the unique element!The Mathematical Proof:
Given a sequence where every element appears an even number of times except one element that appears an odd number of times:
Therefore, only the element(s) appearing an odd number of times survive the XOR chain.
More generally: when XORing a sequence, any element that appears an even number of times will completely cancel out (contribute 0 to the result). Any element appearing an odd number of times will remain in the result. This is because A ⊕ A ⊕ A = A (XOR an odd number of times leaves the value).
Let's visualize the self-cancellation property at the bit level. Consider XORing the sequence [5, 3, 5] where 5 appears twice and 3 appears once.
Binary Representations:
| Step | Operation | Bit 2 (4's place) | Bit 1 (2's place) | Bit 0 (1's place) | Decimal |
|---|---|---|---|---|---|
| Start | result = 0 | 0 | 0 | 0 | 0 |
| Step 1 | 0 ⊕ 5 | 0⊕1=1 | 0⊕0=0 | 0⊕1=1 | 5 |
| Step 2 | 5 ⊕ 3 | 1⊕0=1 | 0⊕1=1 | 1⊕1=0 | 6 |
| Step 3 | 6 ⊕ 5 | 1⊕1=0 | 1⊕0=1 | 0⊕1=1 | 3 |
Observation: The final result is 3, which is the only number that appeared once. The two 5's canceled each other out.
Alternative View — Regrouping:
We can also view this as:
5 ⊕ 3 ⊕ 5 = (5 ⊕ 5) ⊕ 3 [by commutativity & associativity]
= 0 ⊕ 3 [by self-cancellation]
= 3 [by identity]
This regrouping perspective is powerful. It means the order in which we encounter elements doesn't matter—the duplicates will always find each other and cancel.
Traditional approaches to finding unique elements require either:
The XOR approach achieves O(n) time with O(1) space—the best of both worlds. We need only a single integer variable regardless of input size.
Another perspective on XOR's self-cancellation is to view XOR as a parity tracker. At each bit position, XOR keeps track of whether an odd or even number of 1's have been seen.
The Parity Interpretation:
This is why duplicates cancel: each duplicate contributes the same 1's at the same positions. After an even number of contributions, all those positions flip back to 0 (where they started, assuming we start with 0).
123456789101112131415161718192021222324252627282930313233
# Visualizing XOR as a parity tracker def visualize_xor_parity(numbers: list[int], bit_width: int = 8): """ Visualize how XOR tracks parity at each bit position. """ result = 0 print("XOR Parity Tracking:") print("=" * 50) for i, num in enumerate(numbers): prev_result = result result ^= num # Count 1's at each position so far print(f"\nStep {i+1}: XOR with {num}") print(f" Previous: {prev_result:0{bit_width}b} ({prev_result})") print(f" Number: {num:0{bit_width}b} ({num})") print(f" Result: {result:0{bit_width}b} ({result})") print(f"\n{'=' * 50}") print(f"Final result: {result}") print(f"Binary: {result:0{bit_width}b}") print() print("At each bit position, 1 means an odd count of 1's was seen.") print("If a number appeared twice, its 1-bits were seen an even number") print("of times, so they contribute 0 to the final result.") # Example: [7, 3, 7, 3, 5] - 7 and 3 appear twice, 5 appears oncevisualize_xor_parity([7, 3, 7, 3, 5]) # Output will show that the final result is 5, as 7 and 3 cancel outWhy Parity Tracking is Useful:
The parity perspective helps us understand XOR's limitations and capabilities:
Why duplicates must be exact: For cancellation to work, the duplicates must be identical. Different values have different bit patterns and won't cancel.
Why we can handle large numbers: XOR works bit by bit, so the size of numbers doesn't fundamentally change the approach. A 32-bit integer is just 32 independent parity trackers.
Why multiple unique elements don't work simply: If two elements appear once each, their 1-bits at the same positions interfere with each other in the parity count, making it impossible to recover either one from the XOR alone.
XOR has a remarkable property: it is its own inverse. This means XOR is reversible in a way that AND and OR are not.
The Reversibility Property:
If A ⊕ B = C, then:
C ⊕ B = AC ⊕ A = BIn other words, XOR can be "undone" by XORing again with the same value. This is the foundation of many cryptographic techniques and the famous "swap without temporary variable" trick.
1234567891011121314151617181920212223242526272829303132333435363738394041
# XOR Reversibility Demonstration # Basic reversibilityA = 42B = 17C = A ^ B print("XOR Reversibility:")print(f"A = {A}, B = {B}")print(f"C = A ^ B = {C}")print(f"C ^ B = {C ^ B} (should equal A = {A})")print(f"C ^ A = {C ^ A} (should equal B = {B})")print() # This leads to the famous swap trickprint("Swap without temporary variable:")x = 100y = 200print(f"Before: x = {x}, y = {y}") x = x ^ y # x now contains x ^ yy = x ^ y # y = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = xx = x ^ y # x = (x ^ y) ^ x = (x ^ x) ^ y = 0 ^ y = y print(f"After: x = {x}, y = {y}")print() # Why this works:# Step 1: x = x ^ y -> x has "encoded" both values# Step 2: y = x ^ y = x -> y recovers original x (y cancels)# Step 3: x = x ^ y = y -> x recovers original y (x cancels) # Comparison with AND and OR (not reversible)print("AND and OR are NOT reversible:")A, B = 12, 10and_result = A & Bor_result = A | Bprint(f"A = {A} ({bin(A)}), B = {B} ({bin(B)})")print(f"A & B = {and_result} ({bin(and_result)})")print(f"A | B = {or_result} ({bin(or_result)})")print("Cannot recover A or B from AND or OR result alone!")While the XOR swap is a classic interview curiosity, in production code you should use standard swap techniques (temporary variable or language-provided swap). The XOR swap is harder to read, doesn't work when swapping a variable with itself (x ^= x becomes 0), and modern compilers optimize standard swaps better.
To appreciate XOR's elegance, let's compare it with alternative approaches for finding a single unique element in an array where all others appear twice.
Problem: Find the element that appears exactly once when all other elements appear exactly twice.
| Approach | Time | Space | Modifies Input? | Single Pass? |
|---|---|---|---|---|
| Hash Map | O(n) | O(n) | No | Yes |
| Sorting | O(n log n) | O(1)-O(n) | Yes (usually) | No |
| XOR | O(n) | O(1) | No | Yes |
The XOR approach is clearly optimal for this specific problem. It's not just a clever trick—it's the mathematically perfect tool for the job.
While XOR is powerful, it has specific limitations that determine when it can and cannot be applied.
Limitation 1: Exact Duplicates Required
For cancellation to occur, duplicates must be exactly identical. Near-duplicates or similar values won't cancel:
5 ^ 6 ^ 5 = 6 (5's cancel)
5 ^ 6 ^ 4 = 7 (no cancellation, result is meaningless for detection)
Limitation 2: Cannot Distinguish Multiple Unique Elements Directly
If two elements each appear once, XOR gives us their combined XOR, not the individual values:
[1, 2, 3, 1] → 2 ^ 3 = 1 (can't tell if result is one element or XOR of two)
We'll see techniques to handle this case in upcoming pages.
Limitation 3: Cannot Count Occurrences
XOR only tells us about parity (odd vs even). We can't determine if an element appeared 3 times vs 5 times vs 7 times—they all look the same (remaining in the result).
Limitation 4: Order Information Lost
XOR is commutative and associative, so all order information is lost. We know what the unique element is, but nothing about where it was in the array.
XOR is not a universal solution—it's optimal for specific problem constraints. Recognizing when XOR applies (exact duplicates, finding the odd-one-out, constant space requirement) is as important as knowing the technique itself.
We've built a comprehensive understanding of XOR's self-cancellation property, the foundation for an entire class of elegant algorithms.
What's Next:
Now that we understand why XOR's self-cancellation works, we'll apply it to concrete problems. The next page covers the classic problem: Find the Single Non-Duplicate Number—the quintessential XOR application that appears in interviews and competitive programming alike.
You now have a deep, rigorous understanding of XOR's self-cancellation property. This mathematical foundation will serve you throughout the remaining pages as we tackle progressively more sophisticated XOR-based problems.