The Joy of
Programming
S.G. Ganesh
Traps and Pitfalls: Swapping Two Variables—Part III In May and June last year, we covered a few traps and pitfalls in trying to swap two variables without using a temporary. This month, we’ll look at swapping variables without a temporary in a single statement, and see how C and Java compilers treat them differently.
T
he following trick using three consecutive ex-or operations for swapping two variables without using a temporary is well known and particularly popular among students:
public static void main(String []s) { int i = 3, j = 6; System.out.println(“Before swap: i = “ + i + “ j = “ + j); i ^= (j ^= (i ^= j)); System.out.println(“After swap: i = “ + i + “ j = “ + j);
}
i ^= j; j ^= i; i ^= j;
}
Here, i and j are integer variables and it works well (we covered a few pitfalls earlier with this). For further optimisation, one often sees this solution combining the three statements into a single statement:
i ^= (j ^= (i ^= j));
Try this with your favourite C compiler; it usually works. This trick works based on the following assumption: the values of i and j are modified in the RHS (right-hand side) of the expression and the modified values are expected to be used in the LHS (left-hand side) of the expression. However, this solution need not work and the updated values of i and j need not get reflected when read again. This is because the compiler is free to optimise the sequence of reads and writes, using temporaries internally. This problem is covered by an intricate and difficult to understand technical issue known as ‘sequence points’ (see en.wikipedia.org/wiki/Sequence_point). For example, if the initial value of i is 0, after executing the statement i=i++, i might be 0 or 1: it is implementation defined behaviour. For the same reason, the expression i ^= (j ^= (i ^= j)) need not swap the two variables i and j correctly—it depends on the compiler as to what we’ll get as values for i and j. We’ll take a different approach in this column and cover Java to understand the implications of such statements. Unlike C, Java does not have code segments leading to implementation defined behaviour (i.e., the programs written in Java will behave the same way, irrespective of the Java compiler used). For the swap in a single statement case, let us see what happens in Java: class Swap {
102
june 2008
|
LINUX For You
|
www.openITis.com
The swap trick does not work! What happened? The Java specification (section 15.26.2) says: “The value of the left-hand side of a compound assignment is saved before the right-hand side is evaluated”. In other words, the value of i and j are remembered and used for the LHS values of i and j; so we do not get the values of i and j swapped correctly. To illustrate this, let us try the following: Precompute the result of (i ^ j) and remember it in a temporary. Now use that temporary in the LHS instead of i; you’ll get the expected (correct) output of the swapped values of two variables: class SwapTest { public static void main(String []s) { int i = 3, j = 6; int cache = (i ^ j); System.out.println(“Before swap: i = “ + i + “ j = “ + j); cache ^= (j ^= (i ^= j)); i = cache; System.out.println(“After swap: i = “ + i + “ j = “ + j); } }
It works, right? Well, don’t worry if you feel that the explanation for the Java programs is not clear. Next month, we’ll dig deeper by looking at the byte codes generated for the swap code and understand how it works. S.G. Ganesh is a research engineer in Siemens (Corporate Technology), Bangalore. His latest book is “60 Tips on Object Oriented Programming” (ISBN 978-0-07-065670-3), published by Tata McGraw-Hill, New Delhi. You can reach him at
[email protected]