Swap Two Integers Without a Temporary Variable
Two integer variables $i$ and $j$ hold values. Write code that swaps their values without using any extra storage (no temporary variable, no third register, no stack).
Give at least two different methods, and discuss the pitfalls of each (overflow, aliasing, and anything else an interviewer would probe).
Hints
- You need to store two numbers' worth of information in two variables while temporarily holding a combination of both in one of them. Addition is one such combination.
- With $i \leftarrow i + j$, the variable $i$ now knows the sum; $j \leftarrow i - j$ recovers the old $i$ into $j$, and $i \leftarrow i - j$ recovers the old $j$.
- XOR is an even cleaner combination because $a \oplus a = 0$: after $i \leftarrow i \oplus j$, $j \leftarrow i \oplus j$, $i \leftarrow i \oplus j$ the values are exchanged with no overflow. Check what happens if $i$ and $j$ are the same memory location.
Worked Solution
How to Think About It: A swap needs to remember one value while the other is overwritten. Without a temporary, the memory has to come from the two variables themselves: fold both values into one variable with an invertible operation, then peel them apart one at a time.
Approach: Use addition/subtraction, or XOR. Both are three-statement sequences; verify each by tracking the invariant that the pair $(i, j)$ always determines the original values $(a, b)$.
Formal Solution:
*Step 1 -- Arithmetic swap.* Start with $i = a$, $j = b$. $$i \leftarrow i + j = a + b, \qquad j \leftarrow i - j = (a + b) - b = a, \qquad i \leftarrow i - j = (a + b) - a = b.$$ Pitfall: in a fixed-width integer type, $a + b$ can overflow. In C/C++ signed overflow is undefined behaviour; with unsigned (or two's-complement wraparound) arithmetic the method still works because addition and subtraction modulo $2^{w}$ are exact inverses. Multiplication/division variants ($i \leftarrow ij$, $j \leftarrow i/j$, $i \leftarrow i/j$) are worse: they fail when either value is $0$ and overflow far sooner.
*Step 2 -- XOR swap.* Using $x \oplus x = 0$, $x \oplus 0 = x$, associativity and commutativity: $$i \leftarrow i \oplus j = a \oplus b, \qquad j \leftarrow i \oplus j = (a \oplus b) \oplus b = a, \qquad i \leftarrow i \oplus j = (a \oplus b) \oplus a = b.$$ No overflow is possible since XOR is bitwise. Pitfall: if $i$ and $j$ alias the same location (for example swap(&arr[k], &arr[k])), the first step sets that location to $a \oplus a = 0$ and the value is destroyed; the arithmetic version survives aliasing ($2a$, then $a$, then $a$) as long as $2a$ does not overflow. Guard with if (i != j) or check the addresses.
*Step 3 -- Complexity.* Both methods run in $O(1)$ time and $O(1)$ extra space (in fact zero extra words).
*Step 4 -- Practical note.* On modern hardware a plain temporary-variable swap is at least as fast: the compiler keeps the temporary in a register, and the XOR sequence creates a dependency chain of three instructions. The trick matters for the reasoning, and occasionally in register-starved embedded code.
```python def swap_arith(i, j): i = i + j j = i - j # old i i = i - j # old j return i, j
def swap_xor(i, j): i ^= j j ^= i # old i i ^= j # old j return i, j
assert swap_arith(3, 5) == (5, 3) and swap_xor(-7, 12) == (12, -7) ```
Answer: Either i = i + j; j = i - j; i = i - j (beware overflow in fixed-width integers) or i ^= j; j ^= i; i ^= j (no overflow, but zeroes the value if both operands are the same memory location). Both are $O(1)$ with no extra storage.
Intuition
The trick is to make one variable temporarily hold information about both values, using an operation that can be undone with the other variable: addition is undone by subtraction, XOR is undone by XOR. XOR is preferred in practice because it cannot overflow and works on any bit pattern, but it has a famous trap: if the two "variables" are the same memory location, the first XOR zeroes it. Quant interviewers ask this less for the trick itself than to see whether you reason about invariants and edge cases in low-level code, the same habits that matter when writing latency-critical trading systems.