c++ - 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))，可以(例如)在第三个 *a 之前对第二个 *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 的顺序如下:

1. *a 和*b 被计算。它NOT确定在哪个 订单
2. 执行了异或操作
3. 赋值完成，即新值存储在*a
4. 新值用作表达式 (*a ^= *b)
的结果

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

1. *b 和(*a ^= *b) 是计算出来的。它NOT 确定的顺序。但是因为 *b 没有被 (*a ^= *b) 修改，所以没关系。
2. 执行了异或操作
3. 赋值完成，即新值存储在*b

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

1. *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 RESULT!它可能会交换，也可能会丢失 *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 和 3 个 XOR，而使用临时变量的经典交换只有 4 个 MOV。一些informal benchmarks建议大多数时候它可能会慢 3% 到 8%。

顺便说一句，经典的swap也可以写成一条语句:

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