XOR交换算法中运算符的未定义行为？ [英] Undefined behaviour of operators in XOR swap algorithm?

问题描述

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

如上 * a ^ = * b ^ = * a ^ = * b 只是 * a = * a ^（* a = * a ^ * b） / code>，可以（例如）第三个 * a * a 是否修改（通过=）？

As the above *a ^= *b ^= *a ^= *b is just a shortcut for *a = *a ^ (*b = *b ^ (*a = *a ^ *b)), could (e.g.) the 2nd *a be evaluated (for the XOR) just before the 3rd *a is modified (by the =)?

是否写入C99 / C11 / C ++ 98 / C ++ 11？ / p>

Does it matter whether I write it in C99/C11/C++98/C++11?

推荐答案

C ++ 11标准说：

The C++11 standard says:

5.17 / 1：赋值运算符（=）和复合赋值运算符从右到左分组。 （...）在右和左操作数
的值计算之后，在赋值表达式的值计算之前，赋值为
。

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：如果对标量对象的副作用相对于同一标量对象上的另一个副作用或值
计算使用相同标量的值对象，行为是
未定义。

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 。确定
> 新值存储在 * a

2. 新值用于表达式（* a ^ = * b）

1. *a and *b are calculated. It's NOT determined in which order
2. the xor operation is performed
3. the assignment is done, i.e. the new value is stored in *a
4. the new value is used as result of the expression (*a ^= *b)

现在 * b ^ = * a ^ = * b ，根据优先级规则 * b ^ =（* a ^ = * b）：

Now *b ^= *a ^= *b, which according to priority rule is *b ^= (*a ^= *b) :

1. * b 和（* a ^ = * b）。它是不确定在哪个顺序。但由于 * b 未被（* a ^ = * b）修改， li>
   
2. 执行xor操作


3. 完成分配，即新值存储在 * b

1. *b and (*a ^= *b) are calculated. It's NOT determined in which order. But as *b is not modified by (*a ^= *b) it doesn't matter.
2. the xor operation is performed
3. the assignment is done, i.e. the new value is stored in *b

但现在未指定顺序 b ^ = * a ^ = * b 这是根据优先级规则 * a ^ =（* b ^ =（* a ^ = * b））：

But now to the unspecified sequencing with *a ^= *b ^= *a ^= *b which is according to priority rules *a ^= (*b ^= (*a ^= *b) ):

1. * a b ^ =（* a ^ = * b））。它是不确定在哪个顺序。但由（* b ^ =（* a ^ = * b））修改 * a 因此，结果将取决于首先计算哪个值。这显然是一个U.B.

1. *a and (*b ^= (*a ^= *b) ) are calculated. It's NOT determined in which order. But as *a IS modified by (*b ^= (*a ^= *b) ). So the result will depend on which value is calculated first. That's clearly an U.B.

假设 * a （即在其他任何东西之前）：

你会得到它的原始值，它将被（* b ^ =（* a ^ = * b） ），即原始 * b 与原始 * a code> * b 。这将导致0（它将存储在 * a ）。

Suppose *a is evaluated first, (i.e. before anything else):
you would get the original value of it, which will be xored with the value of (*b ^= (*a ^= *b) ), that is the original *b xored with original *a xored again with *b. This will result in 0 (which will be stored in *a).

假设（* b ^ =（* a ^ = * b）） / strong>，则其结果是原始 * a ，但是 * a 的内容更改为原始 * a 与原始 * b 保存。因此，这将导致原始 * b （将存储在 * a ）

Suppose (*b ^= (*a ^= *b) ) is evaluated first, then its result is the original *a, but the content of *a is changed to the original *a xored with the original *b. Thus this will result in the original *b (which will be stored in *a)

顺便说一下，在这两种情况下， * b 包含 * a 两次 * b 意味着 * b 将包含原始 * a 。

By the way, in both cases, *b contains the original value of *a xored twice with *b meaning that *b will contain the original *a.

结论：这表明 * b 的最终值是唯一确定的，但是 * a 的最终值不是唯一定义的（可能有两个值）。因此，这显然是未确定/未定义的结果！根据你的编译器，它可能会交换或可能会丢失 * a 。

CONCLUSION: Here is demonstrated that the final value of *b is uniquely determined by this expression, but that the final value of *a is not uniquely defined (two values possible). So it's clearly an UNSPECIFIED/UNDEFINED RESULT ! It may swap or it might lose *a depending on your compiler.

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

I've demonstrated above that first two compound assignments are well specified. So we just have to make sure that the last compound assignment is done after it. This can be guaranteed by a comma operator:

5.18 / 1：

因此，以下内容将起作用：

Hence, the following would work:

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

这篇关于XOR交换算法中运算符的未定义行为？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！