Swapping or a circular shift without temporary storage

May 10th, 2004 admin Posted in Tidbits |

Normally, when you want to swap (exchange the values of) two variables, the most intuitive way is to store the value of one in a temporary variable. Overwriting the safely-stored variable’s value with the other one. And then overwriting the other variables value with the stored variables value. At this point since the swap is done the temporary variable may be deleted.
An interesting, thought provoking and equally symmetric way of doing the same action, without the use of a temporary storage is by using the bitwise XOR operation. The way it works is:

x = x xor y
y = x xor y
x = x xor y
How this works is seen upon a minor expansion of the above three statements, and with a faith in the associativity of the XOR operation (basically that means you can change the order of the operands being operated upon by the XOR operator).
x = x xor y
y = x xor y , but the vaule of x is now x xor y from the first statement. Therefore
= x xor y xor y
= x xor 0, since y xor y = 0
= x
x = x xor y
= (x xor y) xor x
= x xor x xor y
= 0 xor y
= y
Taking the same logic one step further, you can actually make cyclic moves of variable values. What I mean by that is, if you have A, B, C … N, then using the same principle, we can move the value of variable A into B, the original value of B into C, and so on till finally the original value of variable N moves into A. The way this would work is

A = A xor B xor C xor … xor N
B = A xor B xor C xor … xor N
C = A xor B xor C xor … xor N
.
.
.
N = A xor B xor C xor … xor N
These N+1 statements achieve the required effect. The only glitch here is that we might have been better off using one temporary variable and be done with much shorter statements that do not require all the variables in every statement. So the intuitive way might work better for example in a microprocessor where the system resources are critical and run time is dependent on the number of operands. The intuitive way is
Temp = N
N = M
.
.
.
C = B
B = A
A = Temp