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被评估(对于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) )计算.它不是以哪种顺序确定的.但是由于*aIS的修改 (*b ^= (*a ^= *b) ).因此,结果将取决于首先计算哪个值.那显然是UB

假设*a首先进行评估,(即在其他任何事情之前):
你将得到它的原始值,它将用值x,xts再次用(*b ^= (*a ^= *b) )原始*bxored进行*axored *b.这将导致0(将存储在其中*a).

假设(*b ^= (*a ^= *b) )首先进行评估,然后其结果为原始结果*a,但内容*a将更改为原始*axored *b.因此,这将导致原件*b(将存储在其中*a)

顺便说一句,在这两种情况下,*b包含*axored 的原始值两次,其*b含义*b将包含原始值*a.

结论:这里证明了最终值*b是由该表达式唯一确定的,但最终值*a并未唯一定义(可能有两个值).所以它显然是一个未知/未定的结果!*a根据您的编译器,它可能会交换或丢失.

如何进行交换肯定？

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

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

因此,以下方法可行:

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

编辑:但为什么XOR交换？

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

首先,很难理解,如上所述,容易出错.然后它可能没有看起来那么高效.一些依赖于实现的实验显示不太优化的代码:3 MOV和3 XOR,而MOV使用临时变量的经典交换只有4 .一些非正式的基准测试表明,大部分时间它可能会减慢3%到8%.

顺便说一下,经典交换也可以用一个语句写成:

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