XOR 交换算法中运算符的未定义行为？

Question

void swap(int* a, int* b) {
    if (a != b)
        *a ^= *b ^= *a ^= *b;
}

由于上面的 *a ^= *b ^= *a ^= *b 只是 *a = *a ^ (*b = *b ^ (*a = *a ^ *b)) 的快捷方式，是否可以（例如）在第三个 [=13= 之前评估第二个 *a（对于 XOR） ]被修改（由=）？

我用C99/C11/C++98/C++11写有关系吗？

Answer 1

C++11 标准说：

5.17/1: The assignment operator (=) and the compound assignment operators all group right-to-left. (...) the assignment is sequenced after the value computation of the right and left operands, and before the value computation of the assignment expression.

1.9/15: 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.

所以*a ^= *b的顺序如下：

*a 和 *b 被计算出来。 NOT 由哪个决定订单
执行异或运算
赋值完成，即新值存储在*a
新值用作表达式 (*a ^= *b)

现在 *b ^= *a ^= *b，根据优先级规则是 *b ^= (*a ^= *b) :

*b 和 (*a ^= *b) 被计算出来。 NOT 决定的是哪个顺序。但由于 *b 未被 (*a ^= *b) 修改，所以没关系。
执行异或运算
赋值完成，即新值存储在*b

但现在 未指定排序 与 *a ^= *b ^= *a ^= *b 根据优先规则 *a ^= (*b ^= (*a ^= *b) ):

*a 和 (*b ^= (*a ^= *b) ) 被计算出来。 NOT 决定的是哪个顺序。但是因为 *a 被 (*b ^= (*a ^= *b) ) 修改了。所以结果将取决于首先计算哪个值。这显然是 U.B。

假设首先评估 *a，（即在其他任何事情之前）：
你会得到它的原始值，它将与 (*b ^= (*a ^= *b) ) 的值进行异或，即原始 *b 与原始 *a 再次与 *b 异或。这将导致 0（将存储在 *a 中）。

假设先计算(*b ^= (*a ^= *b) )，那么它的结果就是原来的*a，只是*a的内容变成了原始 *a 与原始 *b 异或。因此，这将导致原始 *b（将存储在 *a 中）

顺便说一下，在这两种情况下，*b 都包含 *a 的原始值，与 *b 进行了两次异或运算，这意味着 *b 将包含原始的 *a.

结论： 这里证明了 *b 的最终值是由该表达式唯一确定的，但 *a 的最终值不是唯一定义（可能有两个值）。所以这显然是 UNSPECIFIED/UNDEFINED 结果 ！它可能会交换，也可能会丢失 *a，具体取决于您的编译器。

如何确定交换？

我在上面已经证明前两个复合赋值是明确指定的。所以我们只需要确保最后一个复合赋值在它之后完成。这可以通过逗号运算符来保证：

5.18/1: A pair of expressions separated by a comma is evaluated left-to-right and the value of the left expression is discarded

因此，以下将起作用：

void safe_swap(int* a, int* b) {
    if (a != b)
        *b ^= *a ^= *b, *a ^= *b;
}

编辑：但为什么要进行 XOR 交换？

在一些没有更多可用内存的嵌入式设备上，在极端条件下可能不得不使用这种高级技巧。但它有缺点。

首先很难理解，而且如上所示，容易出错。那么它可能不像看起来那么有效。一些依赖于实现的实验 show less optimal code: 3 MOV and 3 XOR, compared to only 4 MOV for the classical swap using a temporary variable. Some informal benchmarks 表明它在大多数情况下可能会慢 3% 到 8%。

顺便说一句，经典的交换也可以写成一条语句：

void modern_swap(int*a, int*b) {
    if (a!=b) 
        tie(*a,*b)=make_pair(*b,*a);
}

XOR 交换算法中运算符的未定义行为？

Undefined behaviour of operators in XOR swap algorithm?

c

c++

swap

operators

undefined-behavior

如何确定交换？

编辑：但为什么要进行 XOR 交换？