Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Swap integers via XOR in single line. Is it really allowed in c++11?

I still could not clearly understand whether the expression x ^= y ^= x ^= y; valid in C++11 (as they say in this thread) or it leads to undefined behavior?

The reasons given by the link seem convincing, but clang throws a warning:

warning: unsequenced modification and access to 'x' [-Wunsequenced]

Moreover, if both versions:

x ^= y ^= x ^= y; // (1) 
x = x ^ (y = y ^ (x = (x ^ y))); // (2)

considered equivalent (and well-defined in C++11), why it gives different results (first, second)?

Additionally, it should be noted that the gcc gives a warning about sequence point only on the second version of code.

like image 218
αλεχολυτ Avatar asked Mar 28 '15 08:03

αλεχολυτ


People also ask

How to swap two integers using XOR operator in JavaScript?

Here, we are using XOR ( ^) operator to swap two integers. If you don't get confused the XOR operator returns the second number if the result of two XOR-ed numbers is again XOR-ed with first original number, and returns the first number if the result of two XOR-ed numbers is again XOR-ed with second original number.

Is it possible to use XOR-swap in C?

If xor-swapping was faster on some hypothetical machine, a good compiler would use it for you when optimizing tmp = a; a = b; b = tmp; So you don't need to write it explicitly. This is why you're using C, not writing by hand in asm. Also, xor-swap works for integers only. What if you want to swap floating-point numbers? Strings?

What is XOR swapping?

Swapping two numbers using bitwise operator XOR is a programming trick that is usually asked in technical interviews. It does not use a third temp variable for swapping values between two variables.

Should I Write XOR-swap in ASM?

If xor-swapping was faster on some hypothetical machine, a good compiler would use it for you when optimizing tmp = a; a = b; b = tmp; So you don't need to write it explicitly. This is why you're using C, not writing by hand in asm. Also, xor-swap works for integers only.


1 Answers

The assignment operator (=) and the compound assignment operators all group right-to-left. [..]
The behavior of an expression of the form E1 op = E2 is equivalent to E1 = E1 op E2 except that E1 is evaluated only once.

Thus your code is equivalent to

x = x ^ (y ^= (x ^= y)));

... with x evaluated only once in x = x .... Unfortunately, for xor's, the evaluation of the operands is unsequenced. I.e.

Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced.

applies. But now we have a problem:

   x = x ^ (y ^= (x ^= y)));
//     *          ******
//     |            |
//     |            Side effect
//     Value computation

The value computation (which is implied in the singular evaluation of x for the two leftmost x) and the side effect are unsequenced wrt each other, hence we induce UB:

If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined.

like image 198
Columbo Avatar answered Sep 27 '22 19:09

Columbo