为什么a =(a + b) - (b = a)是交换两个整数的不错选择？

Question

我偶然发现了这个代码,用于交换两个整数而不使用临时变量或使用按位运算符.

int main(){

    int a=2,b=3;
    printf("a=%d,b=%d",a,b);
    a=(a+b)-(b=a);
    printf("\na=%d,b=%d",a,b);
    return 0;
}

但我认为这段代码在swap语句中有未定义的行为,a = (a+b) - (b=a);因为它不包含任何序列点来确定评估的顺序.

我的问题是:这是交换两个整数的可接受的解决方案吗？

Answer 1

不,这是不可接受的.此代码调用未定义的行为.这是因为b没有定义操作.在表达中

a=(a+b)-(b=a);  

由于缺少序列点,不确定是b先修改还是在expression(a+b)中使用它的值. 看看标准的syas:

C11:6.5表达式:

如果相对于对同一标量对象的不同副作用或使用相同标量对象的值进行值计算,对标量对象的副作用未被排序,则行为未定义.如果表达式的子表达式有多个允许的排序,则如果在任何排序中发生这种未测序的副作用,则行为是不确定的.84)₁.

阅读C-faq-3.8和这个答案,了解序列点和未定义行为的更详细说明.

_{1.重点是我的.}

Answer 2

我的问题是 - 这是交换两个整数的可接受的解决方案吗？

谁可以接受？如果你问我是否可以接受,那就不会超过我所在的任何代码审查,相信我.

为什么a =(a + b) - (b = a)是交换两个整数的不错选择？

原因如下:

1)正如您所注意到的,C中无法保证它实际上是这样做的.它可以做任何事情.

2)假设为了参数,它确实交换了两个整数,就像在C#中一样.(C#保证副作用从左到右发生.)代码仍然是不可接受的,因为它的含义完全不明显!代码不应该是一堆聪明的技巧.为需要阅读和理解的人编写代码.

3)再次,假设它有效.代码仍然是不可接受的,因为这只是简单的错误:

我偶然发现了这个代码,用于交换两个整数而不使用临时变量或使用逐位运算符.

那简直是假的.这个技巧使用临时变量来存储计算a+b.该变量由编译器代表您生成,而不是名称,但它就在那里.如果目标是消除临时性,这会使情况变得更糟,而不是更好!你为什么要首先消除临时工？他们很便宜!

4)这仅适用于整数.除了整数之外,还需要交换很多东西.

简而言之,花时间专注于编写明显正确的代码,而不是试图提出实际上让事情变得更糟的聪明技巧.

Answer 3

至少有两个问题a=(a+b)-(b=a).

你自己提到的一点:缺少序列点意味着行为未定义.因此,任何事情都可能发生.例如,无法保证首先评估哪个:a+b或b=a.编译器可以选择首先为赋值生成代码,或者执行完全不同的操作.

另一个问题是签名算术的溢出是未定义的行为.如果a+b溢出则无法保证结果; 甚至可能抛出异常.

Answer 4

除了其他答案,关于未定义的行为和样式,如果你编写只使用临时变量的简单代码,编译器可能会跟踪这些值而不是在生成的代码中实际交换它们,并且稍后在某些代码中使用交换的值案例.它不能用你的代码做到这一点.在微优化方面,编译器通常比你好.

因此,您的代码可能更慢,更难理解,也可能是不可靠的未定义行为.

Answer 5

如果您使用gcc并且-Wall编译器已经警告过您

ac:3:26:警告:'b'上的操作可能未定义[-Wsequence-point]

从性能角度来看,是否使用这样的构造也存在争议.当你看

void swap1(int *a, int *b)
{
    *a = (*a + *b) - (*b = *a);
}

void swap2(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

并检查汇编代码

swap1:
.LFB0:
    .cfi_startproc
    movl    (%rdi), %edx
    movl    (%rsi), %eax
    movl    %edx, (%rsi)
    movl    %eax, (%rdi)
    ret
    .cfi_endproc

swap2:
.LFB1:
    .cfi_startproc
    movl    (%rdi), %eax
    movl    (%rsi), %edx
    movl    %edx, (%rdi)
    movl    %eax, (%rsi)
    ret
    .cfi_endproc

你可以看到混淆代码没有任何好处.

看看C++(g ++)代码,它基本上是一样的,但考虑move到了

#include <algorithm>

void swap3(int *a, int *b)
{
    std::swap(*a, *b);
}

给出相同的装配输出

_Z5swap3PiS_:
.LFB417:
    .cfi_startproc
    movl    (%rdi), %eax
    movl    (%rsi), %edx
    movl    %edx, (%rdi)
    movl    %eax, (%rsi)
    ret
    .cfi_endproc

考虑到gcc的警告并且看不到任何技术收益,我会说,坚持使用标准技术.如果这成为瓶颈,您仍然可以调查,如何改进或避免这一小段代码.

Answer 6

该声明:

a=(a+b)-(b=a);

调用未定义的行为.第二段应在引用的段落中被违反:

(C99,6.5p2)"在前一个和下一个序列点之间,一个对象的存储值最多只能通过表达式的计算来修改一次.此外,先前的值应该是只读的,以确定要存储的值. "

Answer 7

一个问题是在2010年以相同的例子发布的.

a = (a+b) - (b=a);

Steve Jessop警告说:

顺便说一下,该代码的行为是不确定的.读取和写入a和b都没有插入序列点.首先,在评估a + b之前,编译器完全有权评估b = a.

以下是2012年发布的问题的解释.请注意,由于缺少括号,样本不完全相同,但答案仍然是相关的.

在C++中,算术表达式中的子表达式没有时间排序.

a = x + y;

是x首先评估,还是y？编译器可以选择其中之一,也可以选择完全不同的东西.评估顺序与运算符优先级不同:严格定义运算符优先级,评估顺序仅定义为程序具有序列点的粒度.

实际上,在某些体系结构上,可以发出同时评估x和y的代码 - 例如,VLIW体系结构.

现在来自N1570的C11标准报价:

附件J.1/1

在以下情况下,这是未指定的行为:

-在其中的子表达式的计算顺序,并且其中的副作用发生,除了作为函数调用中指定的顺序(),&&, ||,? :,和逗号运算符(6.5).

- 评估赋值运算符的操作数的顺序(6.5.16).

附件J.2/1

在以下情况下是未定义的行为:

- 相对于相同标量对象的不同副作用或使用相同标量对象的值计算值(6.5),标量对象的副作用未被排序.

6.5/1

表达式是操作符和操作数的序列,其指定值的计算,或指定对象或函数,或者生成副作用,或执行其组合.在运算符的结果的值计算之前,对运算符的操作数的值计算进行排序.

6.5/2

如果相对于对同一标量对象的不同副作用或使用相同标量对象的值进行值计算,对标量对象的副作用未被排序,则行为未定义.如果表达式的子表达式有多个允许的排序,则如果在任何排序中发生这种未测序的副作用,则行为是不确定的.84)

6.5/3

运算符和操作数的分组由语法表示.85)除了后面指出的,子表达式的副作用和值计算是未被排序的.86)

您不应该依赖未定义的行为.

一些替代方案:在C++中你可以使用

  std::swap(a, b);

XOR交换:

  a = a^b;
  b = a^b;
  a = a^b;

Answer 8

您可以使用XOR交换算法来防止任何溢出问题,并且仍然具有单线程.

但是,既然你有一个c++标签,我更喜欢一个简单的方法std::swap(a, b),使它更易于阅读.

Answer 9

问题是根据C++标准

除非另有说明,否则对单个运算符的操作数和单个表达式的子表达式的评估是不确定的.

所以这个表达

a=(a+b)-(b=a);

有未定义的行为.