[英] 不使用临时变量交换两个变量的值（2013）

I wrote this as a comment on Hacker News before polishing it up to put it here – see original .

The question “How do you swap two variables without using a temporary variable?” is a favorite of unimaginative interviewers everywhere. If you haven’t seen it, the typical solution is three bitwise exclusive or (xor) operations in succession:

var a = 10, b = 20;  a = a ^ b; b = a ^ b; a = a ^ b;  console.log("a = " + a + ", b = " + b); // a = 20, b = 10 

As you can imagine, this is extremely useful in situations where you just can’t spare even one byte of memory to hold a temporary variable.

This is known as the ‘xor trick’. But it’s not the only solution. Here’s another way:

var a = 10, b = 20;  a = a + b; b = a - b; a = a - b;  console.log("a = " + a + ", b = " + b); // a = 20, b = 10 

That looks a bit different - instead of performing the same operation three times, we performed an addition followed by two subtractions.

Can we describe all possible solutions? Sure - you just need the concept of a mathematical group . A group is a set of values G together with a binary operation (traditionally written as a filled dot · ) that satisfy four axioms:

1. Closure– for all values a and b in G their multiplication a · b is also in G .

2. Associativity– for all a , b and c in G you have ( a · b ) · c = a · ( b · c ).

3. Identity– there is a value e in G such that for every a in G , the equation e · a = a · e = a holds.

4. Inverses– for every a in G there is an inverse a ^{- 1} such that the equations a ^{- 1} · a = e = a · a ^{- 1} hold.

If the types of a and b form a group, then we can pull off the ‘xor trick’ like this (using the left arrow for assignment)

$$ /begin{align} a & /leftarrow a /cdot b // b & /leftarrow a /cdot b^{-1} // a & /leftarrow b^{-1} /cdot a /end{align} $$

The values of a and b as we perform each assignment can be shown in a table. Initially we’ve set a = c and b = d .

$$ /begin{array}{l|c|c} & a & b // /hline /textrm{} & c & d // a /leftarrow a/cdot b & c/cdot d & d // b /leftarrow a/cdot b^{-1} & c/cdot d & (c/cdot d)/cdot d^{-1} = c /cdot (d/cdot d^{-1}) = c // a /leftarrow b^{-1} /cdot a & c^{-1}/cdot(c/cdot d) = (c^{-1}/cdot c)/cdot d = d & c // /end{array} $$

Note that it’s important that we write b ^{- 1} · a in the last assignment and not a · b ^{- 1} since you can’t in general assume that the group you’re working with is commutative.

Groups come up a lot in programming, so there are many ways to pull off the variable swapping trick:

It works when a and b are integers, since integers form a group where the operation is addition, the identity is 0 and the inverse of n is -n . Remarkably we don’t have to worry about integer overflow when adding two machine ints, since integers also form a group under addition modulo N .

It works when a and b have fixed-length binary representations, since bitstrings form a group where the operation is bitwise xor (the ^ operator), the identity is a string of 0s and every string is its own inverse (this last property is why when you do this variable swap trick with xor, you end up repeating the same operation three times).

It almost works when a and b are nonzero floats – it’s nearly (but not quite) true that nonzero floats form a group where the operation is multiplication, the identity is 1 and the inverse of x is 1/ x . It’s not quite a group, because of issues like over- and underflow, NaN values and non-associativity of floating point multiplication.

It works when a and b are matrices of fixed dimensions, which form a group where the operation is addition, the identity is the zero matrix and the inverse is given by elementwise negation.

It almost works when a and b are square, nonsingular matrices of the same dimension, which form a group where the operation is matrix multiplication, the identity is the identity matrix and inverses are given by the matrix inverse (again, this only works modulo floating point weirdness).

It works when a and b are permutations, which are a group under composition, with identity given by the null permutation and inverses are ‘undo all the swaps’.

So there you go - a multitude of ways to swap two variables without using a temporary variable. With math!

Edit:It was pointed out to me by a commenter on Reddit that you don’t need the full properties of a group. A quasigroup is a set Q with three binary operations: multiplication * , left division / and right division / which satisfy the following axioms:

$$ /begin{align} x /backslash (x * y) & = y // x * (x /backslash y) & = y // (x * y) / y & = x // (x / y) * y & = x /end{align} $$

Every group is automatically a quasigroup if we define a * b = a · b , a / b = a · b ^{- 1} and a / b = a ^{- 1} · b . So quasigroups are a generalization of groups. If we have a quasigroup then the xor trick can be expressed as

$$ /begin{align} a & /leftarrow a * b // b & /leftarrow a / b // a & /leftarrow b /backslash a /end{align} $$

You can follow through the assignments using the quasigroup axioms where appropriate to prove that this really doe swap the two variables.

It’s exciting that every Latin square defines a quasigroup, and complete solutions to Sudoku are examples of Latin squares. Therefore every problem of the type “swap two variables without using a temp variable” can be solved using a sufficiently large Sudoku.