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

Question

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

6

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在被修改（通过等号=）之前是否会被计算（进行异或操作）？是否与程序使用C99/C11/C++98/C++11有关？

- Alexander Aleksandrovič Klimov

我记得在这里有一个关于C11是否允许使用新的顺序规则的讨论。在C99中，这显然是未定义的（*a在没有顺序点的情况下被修改了两次）。 - mafso

1

我记得C++在其赋值运算符上做了一些额外的顺序保证，这是因为C的赋值运算符返回值，但C++的赋值运算符返回lvalue，并且后续的lvalue-to-rvalue转换应该具有良好定义的行为。结果可能是在C++中有效，但我不确定。 - user743382

@hvd：C11采用了C++的序列化模型，因为它可以实现线程标准化。现在，赋值语句左侧的修改将在对左侧和右侧进行评估之后进行序列化。 - mafso

我只使用XOR hack来编写宏（因为我不需要知道类型就可以声明一个临时变量，并且可以将相同的“SWAP”宏用于所有整数类型）。如果这应该扩展为表达式，则#define SWAP(p, q) (*(p) ^= *(q), *(q) ^= *(p), *(p) = *(q))对于所有标准都是明确定义的，并且还具有更新后的*p值（作为问题中的表达式）。是否有任何用例可以使用此功能？ - mafso

4

在 C11 中，对赋值操作符左侧的修改在对左右两侧的求值之后进行排序，但它不能保证对右侧操作数的修改在对左侧操作数的修改之前进行排序，这一点与 C++11 不同。 - haccks

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christophe · Accepted Answer

C++11标准规定：

5.17/1: 赋值运算符（=）和复合赋值运算符从右向左结合. (...) 赋值在左右操作数的值计算之后顺序执行，在赋值表达式的值计算之前执行。

1.9/15: 如果对标量对象的副作用与同一标量对象的另一个副作用或使用相同标量对象的值计算无序，那么行为未定义。

因此，*a ^= *b 的顺序如下：

计算 *a 和 *b。不确定计算顺序
xor 操作执行
进行赋值，即将新值存储在 *a 中
将新值用作表达式 (*a ^= *b) 的结果

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

计算 *b 和 (*a ^= *b)。不确定计算顺序。但由于 (*a ^= *b) 不会修改 *b，因此无关紧要。
xor 操作执行
进行赋值，即将新值存储在 *b 中

但现在是有未指定的排序 *a ^= *b ^= *a ^= *b，根据优先级规则为 *a ^= (*b ^= (*a ^= *b))：

计算 *a 和 (*b ^= (*a ^= *b))。不确定计算顺序。但由于 (*b ^= (*a ^= *b)) 修改了 *a，所以结果将取决于首先计算哪个值。这显然是一个 U.B.

假设首先评估 *a（即在任何其他操作之前）：
您将获得它的原始值，它将与 (*b ^= (*a ^= *b)) 的值异或，即原始的 *b 再次异或上原始的 *a 再次异或上 *b。这将导致 0（将存储在 *a 中）。

假设首先评估 (*b ^= (*a ^= *b))，那么它的结果是原始的 *a，但是 *a 的内容已更改为原始的 *a 异或上原始的 *b。因此，这将导致原始的 *b（将存储在 *a 中）

顺便说一句，在两种情况下，*b 包含两个异或 *b 的原始值，这意味着 *b 将包含原始的 *a。

结论：这里证明了该表达式的最终值唯一确定为 *b，但是 *a 的最终值未唯一定义（可能有两个值）。因此，它显然是一个未指

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

编辑：为什么要使用异或交换？

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

首先，它很难理解，并且容易出错，正如上面看到的那样。然后，它可能并不像看起来那样高效。一些实现相关的实验显示出不太优化的代码：3个 MOV 和 3 个XOR，而传统的使用临时变量进行交换只需4个MOV。一些非正式基准测试表明，它大多数时间可能会慢3到8%。

顺便说一句，传统的交换还可以写成一条语句：
void modern_swap(int*a, int*b) { if (a!=b) tie(*a,*b)=make_pair(*b,*a); }