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

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被评估（对于XOR）就在第三个*a被修改之前（由=）？

我是否用C99 / C11 / C ++ 98 / C ++ 11编写它是否重要？

Answer 1

C ++ 11标准说：

5.17 / 1：赋值运算符（=）和复合赋值运算符从右到左分组 。 （…）在右和左操作数的值计算之后，以及在赋值表达式的值计算之前，对赋值进行排序。

1.9 / 15：如果对标量对象的副作用相对于同一标量对象的另一个副作用或使用相同标量对象的值进行的值计算未被排序，则行为未定义。

所以*a ^= *b按如下方式排序：

1. 计算*a和*b 。 它不是以哪种顺序确定的
2. 执行xor操作
3. 分配完成，即新值存储在*a
4. 新值用作表达式的结果(*a ^= *b)

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

1. *b和(*a ^= *b) 。 它不是以哪种顺序确定的。 但由于*b未被(*a ^= *b)修改，因此无关紧要。
2. 执行xor操作
3. 分配完成，即新值存储在*b

但现在使用*a ^= *b ^= *a ^= *b进行未指定的排序 ，这是根据优先级规则*a ^= (*b ^= (*a ^= *b) ) ：

1. *a和(*b ^= (*a ^= *b) ) 。 它不是以哪种顺序确定的。 但是*a由*a IS修改(*b ^= (*a ^= *b) ) 。 因此，结果将取决于首先计算哪个值。 那显然是UB

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

假设首先评估(*b ^= (*a ^= *b) ) ，然后其结果是原始*a ，但*a的内容改变为原始*a与原始*b 。 因此，这将导致原始*b （将存储在*a ）

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

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

如何进行交换肯定？

我已经在上面certificate了前两个复合赋值已经明确指出。 所以我们必须确保在它之后完成最后的复合赋值。 这可以通过逗号运算符来保证：

5.18 / 1：用逗号分隔的一对表达式从左到右计算，左表达式的值被丢弃

因此，以下将起作用：

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

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

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

首先，很难理解，如上所述，容易出错。 然后它可能没有看起来那么高效。 一些依赖于实现的实验显示不太理想的代码 ：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); }