你知道多少个不用中间变量就能交换a和b的算法?(限整形)
在这个问题中,不考虑临时变量的问题!
我先说两个:
第一个,最简洁,好记,几个小时前刚想到的:
- C/C++ code
a^=b^=a^=b;
就是这样的一句,就可以交换a和b了。
这一句等价于:
- C/C++ code
a = a ^ b;b = a^ b;a = a^ b;
其实用的是a^b^b=a,a^b^a=b这两条异或的性质
然后是第二个,比较复杂,而且有溢出的可能性:
- C/C++ code
a-=b=((a+=b)-b);
等价于
- C/C++ code
a = a + b;b = a - b;a = a - b;
用的是a+b-b=a 和 a+b-(a+b-b)=b这两条。
还有人知道其他的算法吗?
在此征求更好的方法。
[解决办法]
楼主所谓的“等价于”其实都不是等价于……
- C/C++ code
a^=b^=a^=b;
[解决办法]
- C/C++ code
#include <stdio.h>int main(void){ int a, b;// 方法一: a=1, b=-2; _asm { push a push b pop a pop b } printf("a=%d, b=%d\n", a, b);// 方法二: a=1, b=-2; _asm { mov eax, a xchg b, eax mov a, eax } printf("a=%d, b=%d\n", a, b);// 方法三: a=1, b=-2; _asm push a a=b; _asm pop b printf("a=%d, b=%d\n", a, b);// 方法四: a=1, b=-2; _asm mov eax, a a=b; _asm mov b, eax printf("a=%d, b=%d\n", a, b); return 0;}
[解决办法]
a = a - b;
b = a + b;
a = b - a;
这个好像不会溢出,楼主那个先加是会溢出的,另外异或的也不会溢出,不过他们说依赖编译器
[解决办法]
那两个算法,学到老谭的书位移就有说
如果不考虑有0的情况,纯表达式:
- C/C++ code
a = a * b;b = a / b;a = a / b;
[解决办法]
不用中间变量其实提高不了多少效率,反而使你的代码复杂,难懂
int t = a;
a = b;
b = t;
这个最好,因为编译器会选择一个通用寄存器存放t,上面的代码只需要三条汇编,类似于:
mov eax, a
xchg b, eax
mov a, eax
[解决办法]
a-=b=((a+=b)-b);
a = a + b;
b = a - b;
a = a - b;
赋值时序列点, 两者应该完全等价. 对无符号数还行, 对于有符号数, 两者都是未定义行为. 完全符合标准的某些编译器将在运算溢出时触发异常, 详见 C99 文档 5.1.2.3 - 14 条文...
[解决办法]
push pop是用了堆栈作为中间变量的
xchg是用了eax作为中间变量的
a^=b^=a^=b;是用了eax作为中间变量的
a-=b=((a+=b)-b);是用了eax作为中间变量的
没有不用中间变量的算法
[解决办法]
_asm
{
push a;
push b;
pop a;
pop b;
}