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

问题描述 投票:5回答:1
void swap(int* a, int* b) {
    if (a != b)
        *a ^= *b ^= *a ^= *b;
}

由于上面的*a ^= *b ^= *a ^= *b只是*a = *a ^ (*b = *b ^ (*a = *a ^ *b))的捷径,可以(例如)在第3个*a被修改之前(由=)评估第二个*a(对于XOR)?

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

c++ c operators swap undefined-behavior
1个回答
11
投票

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(*b ^= (*a ^= *b) )修改了。因此,结果将取决于首先计算哪个值。那显然是一个U.B.

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

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

顺便说一句,在这两种情况下,*b包含*a的原始值,*b两次,这意味着*b将包含原始的*a

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

How to make the swapping for sure ?

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

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

因此,以下方法可行:

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%。

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

void modern_swap(int*a, int*b) {
    if (a!=b) 
        tie(*a,*b)=make_pair(*b,*a);
} 
© www.soinside.com 2019 - 2024. All rights reserved.