Java Reference
In-Depth Information
// Swaps variables without a temporary - Don't do this!
x = x ^ y;
y = y ^ x;
x = y ^ x;
Even back in those days, this technique was seldom justified. Now that CPUs have many registers,
it is never justified. Like most "clever" code, it is far less clear than its naive counterpart and far
slower. Still, some programmers persist in using it. Worse, they complicate matters by using the
idiom illustrated in this puzzle, which combines the three exclusive OR operations into a single
statement.
This idiom was used in the C programming language and from there made its way into C++ but is
not guaranteed to work in either of these languages. It is guaranteed
not
to work in Java. The Java
language specification says that
operands of operators are evaluated from left to right
[JLS
15.7]. To evaluate the expression
x ^=
expr
, the value of
x
is sampled before
expr
is evaluated, and
the exclusive OR of these two values is assigned to the variable
x
[JLS 15.26.2]. In the
CleverSwap
program, the variable
x
is sampled twice— once for each appearance in the expression— but both
samplings occur before any assignments.
The following code snippet describes the behavior of the broken swap idiom in more detail and
explains the output that we observed:
// The actual behavior of x ^= y ^= x ^= y in Java
int tmp1 = x; // First appearance of x in the expression
int tmp2 = y; // First appearance of y
int tmp3 = x ^ y; // Compute x ^ y
x = tmp3; // Last assignment: Store x ^ y in x
y = tmp2 ^ tmp3; // 2nd assignment: Store original x value in y
x = tmp1 ^ y; // First assignment: Store 0 in x
In C and C++, the order of expression evaluation is not specified. When compiling the expression
x
^=
expr
, many C and C++ compilers sample the value of
x
after evaluating
expr
, which makes the
idiom work. Although it may work, it runs afoul of the C/C++ rule that you must not modify a
variable repeatedly between successive sequence points
[ISO-C]
. Therefore, the behavior of this
Search WWH ::
Custom Search