XOR Properties — Self-Cancellation - XOR Patterns — Finding Missing & Duplicate Numbers | OneNoughtOne

0/361

Data Structures & AlgorithmsXOR Patterns — Finding Missing/Duplicate

XOR Patterns — Finding Missing & Duplicate Numbers

LevelIntermediate

Duration60 mins

TopicXOR Patterns — Finding Missing/Duplicate

1 / 4

XOR Properties — Self-Cancellation

The Magical Operator That Remembers and Forgets

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.

What You Will Learn

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.

XOR Fundamentals Revisited

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:

XOR Truth Table — The Foundation
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:

AND is an intersection detector (both must be 1)
OR is a union detector (at least one must be 1)
XOR is a difference detector (exactly one must be 1)

This difference-detection property is what gives XOR its unique characteristics.

Thinking About XOR

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.

Mathematical Properties of XOR

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.

xor_properties.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Demonstrating XOR properties
 
# Property 1: Commutativity (A ⊕ B = B ⊕ A)
a, b = 5, 3
print(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, 7
print(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 = 42
print(f"Identity: {a} ^ 0 = {a ^ 0}")
# Output: 42 ^ 0 = 42
 
# Property 4: Self-Inverse (A ⊕ A = 0)
a = 42
print(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, 99
result = a ^ b ^ a
print(f"Combined: {a} ^ {b} ^ {a} = {result}")  # Output: 99

The Self-Cancellation Property Deep Dive

The 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:

If the bit in A is 0, then 0 ⊕ 0 = 0
If the bit in A is 1, then 1 ⊕ 1 = 0

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:

self_cancellation_chain.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 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 step
arr = [2, 3, 2, 4, 3]
 
result = 0
print("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"
Final 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:

XOR is commutative: we can group identical elements together
XOR is associative: we can compute (A ⊕ A) first
A ⊕ A = 0: pairs cancel out
Result ⊕ 0 = Result: zeros don't affect the final result

Therefore, only the element(s) appearing an odd number of times survive the XOR chain.

The Generalization

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).

Visual Understanding of XOR Cancellation

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:

5 = 101 in binary
3 = 011 in binary
5 = 101 in binary

Bit-by-Bit XOR Process: [5, 3, 5]
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.

Why This Matters for Space Complexity

Traditional approaches to finding unique elements require either:

Sorting: O(n log n) time and O(1) or O(n) space
Hash Set: O(n) time but O(n) space

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.

XOR as a Parity Tracker

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:

If an even number of 1's have been seen at a bit position, that bit is 0
If an odd number of 1's have been seen at a bit position, that bit is 1

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).

parity_tracking.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 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"
Step {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"
{'=' * 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 once
visualize_xor_parity([7, 3, 7, 3, 5])
 
# Output will show that the final result is 5, as 7 and 3 cancel out

Why 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.

Algebraic Properties and Reversibility

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 = A
C ⊕ A = B

In 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.

xor_reversibility.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# XOR Reversibility Demonstration
 
# Basic reversibility
A = 42
B = 17
C = 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 trick
print("Swap without temporary variable:")
x = 100
y = 200
print(f"Before: x = {x}, y = {y}")
 
x = x ^ y  # x now contains x ^ y
y = x ^ y  # y = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x
x = 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, 10
and_result = A & B
or_result = A | B
print(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!")

The Swap Trick in Practice

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.

XOR vs Other Approaches for Detection Problems

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 1: Hash Map

•Count occurrences of each element
•Find element with count = 1
•Time: O(n)
•Space: O(n) — hash map stores all unique elements
•Extra overhead for hash computations

Approach 2: Sorting

•Sort the array
•Scan for element not equal to neighbors
•Time: O(n log n)
•Space: O(1) or O(n) depending on sort
•Modifies input (or requires copy)

Approach 3: XOR

•XOR all elements together
•Duplicates cancel; unique remains
•Time: O(n)
•Space: O(1) — single integer variable
•No hash overhead, no modification
•Works in a single pass

Comparison Summary
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.

Understanding XOR's Limitations

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.

Right Tool for the Right Problem

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.

Summary: The Power of Self-Cancellation

We've built a comprehensive understanding of XOR's self-cancellation property, the foundation for an entire class of elegant algorithms.

Key Takeaways

•XOR detects difference: Returns 1 when inputs differ, 0 when they're the same
•Four key properties: Commutativity, associativity, identity (0), self-inverse (A ⊕ A = 0)
•Self-cancellation: Any value XORed with itself becomes 0, eliminating duplicates
•Parity tracking: XOR tracks whether an odd or even count of 1's exist at each bit position
•Reversibility: XOR is its own inverse—C = A ⊕ B implies A = C ⊕ B
•O(1) space detection: Enables constant-space solutions for finding unique elements
•Limitations: Requires exact duplicates, can't distinguish multiple unique elements directly

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.

Page Complete

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.