Problem Types - Learning Module

Loading content...

0/276

Swap Without Temporary Variable

The Elegant XOR Swap

One of the most celebrated tricks in low-level programming is the ability to swap two variables without using a temporary variable. While this might seem like a parlor trick at first glance—after all, what's wrong with using a temporary?—it represents a deeper truth about the power of bitwise operations and the mathematical elegance hidden within binary representations.

The XOR swap has been a rite of passage for programmers since the early days of computing, when memory was measured in kilobytes and every saved byte mattered. Today, understanding this technique provides insight into how bitwise operations can achieve seemingly impossible transformations through careful manipulation of information at the binary level.

What You Will Master

By the end of this page, you will understand the XOR swap algorithm from first principles, prove its correctness mathematically, recognize its limitations, and understand when (and when not) to use it in production code. You'll also see how this technique relates to broader patterns in bit manipulation.

The Traditional Swap: Establishing the Baseline

Before diving into the XOR trick, let's establish what we're trying to improve upon. The canonical approach to swapping two values uses a temporary variable:

The standard three-step swap:

Store the value of a in a temporary variable temp
Assign the value of b to a
Assign the value stored in temp to b

This approach is universally understood, obviously correct, and works for any data type. It's the bread and butter of programming, appearing in sorting algorithms, data structure operations, and countless other contexts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function traditionalSwap(a: number, b: number): [number, number] {
    // Before: a = originalA, b = originalB
    
    const temp = a;  // Step 1: Save 'a' in temporary storage
                     // State: temp = originalA, a = originalA, b = originalB
    
    a = b;           // Step 2: Overwrite 'a' with 'b'
                     // State: temp = originalA, a = originalB, b = originalB
    
    b = temp;        // Step 3: Assign saved value to 'b'
                     // State: temp = originalA, a = originalB, b = originalA
    
    // After: a = originalB, b = originalA (swapped!)
    return [a, b];
}
 
// Example execution trace:
console.log(traditionalSwap(42, 17));
// Output: [17, 42]

Why does this work?

The algorithm succeeds because we preserve the original value of a before overwriting it. Without temp, the moment we execute a = b, we lose the original value of a forever—there's no way to recover it for assignment to b.

Resource analysis of the traditional swap:

Resource	Usage	Notes
Memory	O(1) extra	One temporary variable
Operations	3 assignments	temp=a, a=b, b=temp
Time	O(1)	Constant time
Applicability	Universal	Works for any assignable type

This approach has served programmers well for decades. So why look for alternatives?

Historical Context

In the early days of computing, register allocation was extremely constrained. Some architectures had only 2-4 general-purpose registers. In such environments, avoiding a temporary variable meant keeping one more register available for other computations—a significant optimization when compilers were primitive.

Enter XOR: The Binary Swiss Army Knife

The XOR (exclusive OR) operation has several remarkable properties that make it uniquely suited for the swap problem. Before examining the swap algorithm, let's deeply understand these properties because they form the mathematical foundation of the technique.

Essential XOR Properties

•Self-Inverse Property: a ⊕ a = 0 — Any number XORed with itself equals zero. Every bit cancels its twin.
•Identity Property: a ⊕ 0 = a — Any number XORed with zero remains unchanged. Zero is the identity element.
•Commutativity: a ⊕ b = b ⊕ a — Order doesn't matter. The result is the same regardless of operand position.
•Associativity: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) — Grouping doesn't matter. We can rearrange parentheses freely.
•Invertibility: If c = a ⊕ b, then a = c ⊕ b and b = c ⊕ a — XOR operations are reversible.

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
// Let's verify each property with concrete examples
const a = 42;  // Binary: 00101010
const b = 17;  // Binary: 00010001
 
// Property 1: Self-Inverse
console.log("a ⊕ a =", a ^ a);  // Output: 0
// 00101010 ⊕ 00101010 = 00000000
 
// Property 2: Identity with Zero
console.log("a ⊕ 0 =", a ^ 0);  // Output: 42
// 00101010 ⊕ 00000000 = 00101010
 
// Property 3: Commutativity
console.log("a ⊕ b =", a ^ b);  // Output: 59
console.log("b ⊕ a =", b ^ a);  // Output: 59
// Both are 00111011
 
// Property 4: Associativity
const c = 99;  // Binary: 01100011
console.log("(a ⊕ b) ⊕ c =", (a ^ b) ^ c);  // Output: 88
console.log("a ⊕ (b ⊕ c) =", a ^ (b ^ c));  // Output: 88
 
// Property 5: Invertibility
const combined = a ^ b;  // 59
console.log("combined ⊕ b =", combined ^ b);  // Output: 42 (recovers a!)
console.log("combined ⊕ a =", combined ^ a);  // Output: 17 (recovers b!)

The invertibility property is the key insight.

When we compute a ⊕ b, we create a value that encodes the difference between a and b in a reversible way. This combined value acts like a cryptographic one-time pad—it contains enough information to recover either original value when combined with the other.

Bit-level intuition:

Think of XOR as a "toggle tracker." For each bit position:

If the bits are the same (both 0 or both 1), the result is 0 ("no toggle needed")
If the bits differ, the result is 1 ("toggle required")

The XOR result is essentially a map of all the bit positions where a and b differ. Given this map and either original number, we can reconstruct the other by applying the toggles.

XOR as a Toggle Tracker
Bit Position	a (42)	b (17)	a ⊕ b	Interpretation
Bit 0	0	1	1	Toggle required
Bit 1	1	0	1	Toggle required
Bit 2	0	0	0	No toggle
Bit 3	1	0	1	Toggle required
Bit 4	0	1	1	Toggle required
Bit 5	1	0	1	Toggle required
Bit 6	0	0	0	No toggle
Bit 7	0	0	0	No toggle

The XOR Swap Algorithm: Step by Step

Now we're ready to understand the XOR swap. The algorithm performs the swap in three XOR operations, requiring no temporary storage beyond the variables themselves.

The three magical steps:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function xorSwap(a: number, b: number): [number, number] {
    // Initial state: a = A, b = B (using capitals for original values)
    
    a = a ^ b;  // Step 1: a now holds A ⊕ B
                // State: a = A⊕B, b = B
    
    b = b ^ a;  // Step 2: b = B ⊕ (A⊕B) = A
                // State: a = A⊕B, b = A
    
    a = a ^ b;  // Step 3: a = (A⊕B) ⊕ A = B
                // State: a = B, b = A
    
    // After: a = B, b = A (swapped!)
    return [a, b];
}
 
// Example execution:
console.log(xorSwap(42, 17));  // Output: [17, 42]

Let's trace through with concrete values:

Using a = 42 (binary: 00101010) and b = 17 (binary: 00010001):

XOR Swap Execution Trace
Step	Operation	a (decimal)	a (binary)	b (decimal)	b (binary)
Initial	—	42	00101010	17	00010001
Step 1	a = a ⊕ b	59	00111011	17	00010001
Step 2	b = b ⊕ a	59	00111011	42	00101010
Step 3	a = a ⊕ b	17	00010001	42	00101010

No Temporary Variable Used!

Notice that we never created a separate storage location. The 'temporary' value (A⊕B) was stored in one of the original variables. After Step 1, variable 'a' serves dual purpose: it holds the XOR combination while 'b' still holds its original value.

Mathematical proof of correctness:

Let's denote the original values as A and B. We'll prove that after the three steps, the values are swapped.

Initial state: a = A, b = B

After Step 1: a = a ⊕ b

a = A ⊕ B
b = B (unchanged)

After Step 2: b = b ⊕ a

a = A ⊕ B (unchanged)
b = B ⊕ (A ⊕ B)
Using associativity: b = B ⊕ A ⊕ B
Using commutativity: b = A ⊕ B ⊕ B
Using self-inverse (B ⊕ B = 0): b = A ⊕ 0
Using identity (A ⊕ 0 = A): b = A ✓

After Step 3: a = a ⊕ b

a = (A ⊕ B) ⊕ A
Using associativity and commutativity: a = A ⊕ A ⊕ B
Using self-inverse: a = 0 ⊕ B
Using identity: a = B ✓

Final state: a = B, b = A — Swap complete! Q.E.D.

The Crucial Pitfall: Self-Swap Bug

The XOR swap has a notorious bug that catches many programmers: it fails catastrophically when swapping a variable with itself. This isn't just a theoretical concern—it can happen easily when swapping array elements and happens to reference the same memory location.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function xorSwapInPlace(arr: number[], i: number, j: number): void {
    // Dangerous! What if i === j?
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}
 
// Normal case: works correctly
const arr1 = [10, 20, 30, 40, 50];
console.log("Before:", arr1);  // [10, 20, 30, 40, 50]
xorSwapInPlace(arr1, 1, 3);
console.log("After:", arr1);   // [10, 40, 30, 20, 50] ✓
 
// Bug case: self-swap destroys data!
const arr2 = [10, 20, 30, 40, 50];
console.log("Before:", arr2);  // [10, 20, 30, 40, 50]
xorSwapInPlace(arr2, 2, 2);    // Swapping index 2 with itself
console.log("After:", arr2);   // [10, 20, 0, 40, 50] ✗ Data lost!

Why does this happen?

When i === j, both arr[i] and arr[j] refer to the same memory location. Let's trace through:

Initial state: Both arr[i] and arr[j] point to value X at location L

Step 1: arr[i] = arr[i] ^ arr[j]

This is X ^ X = 0
Location L now contains 0
Both arr[i] and arr[j] read as 0

Step 2: arr[j] = arr[j] ^ arr[i]

This is 0 ^ 0 = 0
Location L still contains 0

Step 3: arr[i] = arr[i] ^ arr[j]

This is 0 ^ 0 = 0
Location L still contains 0

Final state: The original value X is lost forever, replaced with 0.

Production Bug Alert

This bug is particularly insidious because it only manifests in specific conditions (when indices happen to be equal). It may pass all your test cases and only appear in production when a sorting algorithm encounters an already-sorted element or when random indices happen to collide. Always guard against this!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function safeXorSwapInPlace(arr: number[], i: number, j: number): void {
    // Guard clause prevents the self-swap bug
    if (i === j) {
        return;  // Nothing to swap; early exit preserves value
    }
    
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}
 
// Now both cases work correctly
const arr = [10, 20, 30, 40, 50];
safeXorSwapInPlace(arr, 1, 3);
console.log(arr);  // [10, 40, 30, 20, 50] ✓
 
safeXorSwapInPlace(arr, 2, 2);
console.log(arr);  // [10, 40, 30, 20, 50] ✓ (unchanged, as expected)

When can this bug occur in practice?

Scenario	Risk Level	Example
Sorting algorithms	High	Fisher-Yates shuffle when `i === j`
Partition operations	Medium	Quicksort when pivot equals scan index
Ring buffer operations	Medium	Head and tail indices collide
Random element selection	High	`swap(arr, random(), random())`
User-provided indices	High	No validation of user input

Alternative No-Temporary Swaps

XOR swap isn't the only way to swap without a temporary. Let's examine other approaches and understand their tradeoffs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function arithmeticSwap(a: number, b: number): [number, number] {
    // Using addition and subtraction
    a = a + b;  // a now holds sum
    b = a - b;  // b = sum - oldB = oldA
    a = a - b;  // a = sum - newB = sum - oldA = oldB
    
    return [a, b];
}
 
console.log(arithmeticSwap(42, 17));  // [17, 42]
 
// Warning: This has overflow issues for large numbers!
// For 32-bit signed integers:
// MAX_INT = 2,147,483,647
// If a = 2,000,000,000 and b = 1,000,000,000
// a + b = 3,000,000,000 > MAX_INT → overflow!

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
function multiplicativeSwap(a: number, b: number): [number, number] {
    // Only works when b !== 0!
    if (b === 0 && a !== 0) {
        throw new Error("Cannot swap when b=0 and a≠0 using multiplication");
    }
    
    if (a === 0 || b === 0) {
        // Special case: one is zero
        return [b, a];  // Just return swapped values
    }
    
    a = a * b;  // a now holds product
    b = a / b;  // b = product / oldB = oldA
    a = a / b;  // a = product / newB = product / oldA = oldB
    
    return [a, b];
}
 
// Works for non-zero values
console.log(multiplicativeSwap(42, 17));  // [17, 42]
 
// But has division issues:
// - Division by zero if b = 0
// - Floating point precision loss for non-integer results
// - Overflow for large numbers

Comparison of Swap Methods
Method	Self-Swap Safe	Overflow Safe	Works with Zero	Works with Floats	Operations
Temporary Variable	✓ Yes	✓ Yes	✓ Yes	✓ Yes	3 assignments
XOR Swap	✗ No (requires guard)	✓ Yes	✓ Yes	✗ No (integers only)	3 XORs
Addition Swap	✓ Yes	✗ No (can overflow)	✓ Yes	⚠ Precision loss	2 additions, 1 subtraction
Multiplication Swap	✓ Yes	✗ No (can overflow)	✗ No (division by zero)	⚠ Precision loss	1 multiplication, 2 divisions

Modern Language Features

Many modern languages provide elegant swap syntax that compiles to optimal code:

• Python: a, b = b, a • Go: a, b = b, a • JavaScript/TypeScript: [a, b] = [b, a] (destructuring) • Rust: std::mem::swap(&mut a, &mut b) • C++: std::swap(a, b)

These are clearer, safer, and often just as efficient due to compiler optimizations.

When to Use XOR Swap (And When Not To)

Despite its elegance, XOR swap is rarely the right choice in modern software development. Let's be honest about its practical applicability.

When XOR Swap Makes Sense

•Embedded systems with extremely limited memory (rare today)
•Register-starved assembly programming where every register matters
•Competitive programming where code brevity is valued (debatable benefit)
•Interview demonstrations to show bit manipulation knowledge
•Understanding XOR as a learning exercise in properties and invariants

When to Avoid XOR Swap

•Production code where clarity matters more than cleverness
•Any situation where indices might be equal (without guards)
•Floating point values which don't support bitwise XOR
•Object references where XOR of pointers is meaningless
•Teams with mixed experience where the trick might confuse others

The Performance Myth

A common misconception is that XOR swap is faster than temporary-variable swap. On modern CPUs, this is usually false. Modern compilers often optimize temporary-variable swaps to use registers efficiently, and XOR swap can actually be slower due to data dependencies between the three operations (each depends on the previous result). Profile before assuming XOR is faster!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// On modern out-of-order CPUs:
 
// Traditional swap (can be parallelized by CPU):
// These are independent operations that can use rename registers
temp = a;  // Can execute in parallel with next line
a = b;     // Can execute in parallel with previous line
b = temp;  // Depends only on temp, not on the new 'a'
 
// XOR swap (serialized due to dependencies):
a = a ^ b;  // Must complete first
b = b ^ a;  // Must wait for new 'a' — data dependency
a = a ^ b;  // Must wait for new 'b' — data dependency
 
// The XOR swap creates a chain of dependencies that prevents
// instruction-level parallelism that modern CPUs rely on for speed.

Deeper Applications: Beyond Simple Swapping

The XOR swap teaches us patterns that extend far beyond swapping. Understanding why it works unlocks insights applicable to many domains.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function xorCipher(data: number[], key: number): number[] {
    // XOR encryption: same operation encrypts and decrypts!
    // This is the basis of one-time pad encryption
    return data.map(byte => byte ^ key);
}
 
const original = [72, 101, 108, 108, 111];  // "Hello" as ASCII
const key = 42;
 
const encrypted = xorCipher(original, key);
console.log("Encrypted:", encrypted);  // [114, 79, 70, 70, 69]
 
const decrypted = xorCipher(encrypted, key);  // Same operation!
console.log("Decrypted:", decrypted);  // [72, 101, 108, 108, 111]
console.log("As string:", String.fromCharCode(...decrypted));  // "Hello"
 
// This works because: (data ⊕ key) ⊕ key = data
// The self-inverse property makes XOR ideal for symmetric operations

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
// A memory-efficient doubly-linked list using XOR!
// Each node stores: npx = prev_address ⊕ next_address
// This halves the pointer storage compared to standard doubly-linked lists
 
interface XorNode {
    data: number;
    npx: number;  // XOR of next and previous node addresses
}
 
// Conceptual traversal (in a language with raw pointers):
// 
// To go forward from node A to node B:
//   next_addr = prev_addr ^ current.npx
//
// To go backward from node B to node A:  
//   prev_addr = next_addr ^ current.npx
//
// Example:
// Nodes at addresses: [100] <-> [200] <-> [300]
//
// Node at 100: npx = 0 ^ 200 = 200 (prev is NULL/0)
// Node at 200: npx = 100 ^ 300 = 400
// Node at 300: npx = 200 ^ 0 = 200 (next is NULL/0)
//
// Traversing forward from 100 to 200:
//   prev = 0 (start), current = 100
//   next = prev ^ current.npx = 0 ^ 200 = 200 ✓
//
// Traversing forward from 200 to 300:
//   prev = 100, current = 200
//   next = prev ^ current.npx = 100 ^ 400 = 300 ✓
 
console.log("XOR Linked List reduces memory by eliminating one pointer per node");

The Principle Behind It All

XOR's power comes from its ability to encode information reversibly. Unlike AND (which loses information about 0s) or OR (which loses information about 1s), XOR preserves all information and can perfectly reconstruct either operand given the other. This makes it invaluable for:

• Error detection (checksums, CRCs) • Error correction (parity bits, RAID) • Cryptography (stream ciphers, LFSR) • Data compression (XOR of blocks) • Hash functions (combining hash values)

Summary: The XOR Swap Mastered

We've thoroughly explored the XOR swap—from its mathematical foundations to its practical limitations. Let's consolidate what we've learned:

Key Takeaways

•XOR swap works via three magical properties: self-inverse (a⊕a=0), identity (a⊕0=a), and invertibility
•The algorithm is elegant: a^=b; b^=a; a^=b; swaps a and b without temporary storage
•The self-swap bug is critical: always guard against i === j when swapping array elements
•Arithmetic alternatives exist but have their own pitfalls (overflow, division by zero, precision loss)
•Modern CPUs may execute temp-swap faster due to better instruction-level parallelism
•The real value is understanding XOR deeply—its applications extend far beyond swapping
•In production code, prefer clarity: use language-provided swap mechanisms or simple temp variables

What's next:

With XOR swap mastered, we'll explore another classic bit manipulation problem: reversing the bits of an integer. This problem requires understanding bit positions, shifting operations, and building results bit-by-bit—skills that compound throughout your bit manipulation journey.

Page Complete

You now understand the XOR swap deeply—its mechanism, proof, pitfalls, and when to use it. More importantly, you've gained insight into XOR's fundamental properties that power countless algorithms in cryptography, error correction, and data structures.