- 程序有所改变。发帖如还有问题请报告
- 【征集】西西河的经济学，及清流措施，需要主动参与者，『稷下学宫』新认证方式，24年网站打算和努力目标
主题：【原创】继续关于swap的讨论 -- 不锈钢破锣
家园 【原创】继续关于swap的讨论 都知道程序设计里的swap()吧。一般是这么写的：
temp=a;
a=b;
b=temp.
如果不用临时变量，只用a,b这两个变量和算术运算该怎么办呢？再推广到逻辑门运算又该怎么办呢？
答案不是唯一的，楼下的朋友给的回答可以算其中之一，但还可以简化到三步：
a = a+b; (a:a+b, b:b)
b = a-b; (a:a+b, b:a)
a = a-b; (a:b, b:a)
推而广之，如果用一个实数域上的可交换运算符，比如*，来替换+，再用它的逆运算符，比如/，替代-， 结果同样成立。
但是，当应用于计算机时，答案中给出的交换方式有两个问题，一个问题是临时结果可能溢出(如果用*和/，会发生除0)，另一个问题是精度可能降低。所以这样的方法不适用于传统计算机结构。
如果把一个变量看成一个二进制数组A(1)，A(2)，...，A(i)，...，A(n), 现在再来看逻辑运算符XOR：
A(i) = A(i) XOR B(i);
B(i) = A(i) XOR B(i);
A(i) = A(i) XOR B(i);
这个表达方式很有意思，同样可以起到交换的作用，而且解决了上面的溢出和精度问题。
那为什么现在比较常用的方法还是使用临时变量呢？两个原因，一个是赋值运算比逻辑运算的速度更快；另一个是在编程方面，使用临时变量可读性更高。
从题目一开始就可以知道，新的运算方式节省了一个临时变量。这在传统计算机结构下是无足轻重的，但是，如果应用到新的计算机机构，比如量子机或者神经网络机，就需要重新衡量不同方法的效率。
从上面的例子可以看出，哪怕最简单的计算机问题，都未必是单一最优解的，原因主要在於问题的解决域不是单一的，从而导致最优解的衡量方式不同。也就是说，计算机科学所研究的往往不是地球围绕太阳转这一类普适性问题，而是条件约束问题。这也是计算机科学与物理之类自然科学在方法论上的主要区别。很可惜的是，当自然科学的方法论已经系统化时，计算机科学的方法论研究还不太成熟。关于这个问题，以后慢慢再谈。
本帖一共被 1 帖 引用 (帖内工具实现)家园 有意思的问题 应该在计算机结构(computer architecture)的范围内讨论比较有意义。否则编译软件的优化很可能把你的各种办法都优化成相同的代码了。
事实上如果我们假设a,b都是寄存器变量的话，不少处理器都可以直接提供交换指令。例如x86处理器的
"xchg ax,bx;"
就是交换两个16位寄存器的内容。
通常情况是，在使用临时变量作显式交换时，编译软件较容易判断出程序员的目的，从而直接使用交换指令。
家园 呵呵，这个答案有问题 a和b可能是同一个地址的引用，例如在选择排序或是洗牌算法中调用swap(a[i], a[j])时可能i与j相等。
如果我没记错的话，TAOCP里的题目是有所不同的，所以我不是说K大的答案有问题。
如果是支持赋值表达式的语言，可以有如下的答案：
a = a + b - (b = a);
但这个方法和“经典答案”一样，如同楼下有人提到的，从编译器偷了临时变量。
这种题和IOCCC一样，作为趣味智力题就很好，但并不适合在实际中使用。
另外，我认为仅这个题目是上纲不到“计算机科学”的，对照自然科学的说法，说是属于“计算机工程”或“应用计算机学”比较合适。
家园 【原创】补充一点 那为什么现在比较常用的方法还是使用临时变量呢？两个原因，一个是赋值运算比逻辑运算的速度更快；另一个是在编程方面，使用临时变量可读性更高。
更重要的原因，如果a,b是一个复杂的object，后两种做法很可能就不work，因为一般class的design，通常都会实现operator=()，而不一定会实现operator+, operator-，几乎很少会实现XOR operator。
因此第一种做法是上面唯一一个能handle generic case的，同时您也提到了，可读性好，效率也不差（实际上如果a,b是object，效率应该比后两种更好）。
严格说来，后两种做法（不使用临时变量），是违反软件工程的基本原则，因为会使code reusability大幅度降低，也不容易维护。
除了在interview中刻意为难一下Interviewee，实际编程工作中，一般不会用后两种做法。
家园 有重大问题请教----- (1)
temp=a;
a=b;
b=temp;
固然要用一个临时变量,但是
(2)
a=a+b;
b=a-b;
a=a-b;
是不是只是在表面上不用临时变量?
拿 "a=a+b;"打个比方:变量 a 在assignment的两边都出现,那么一个compiler是
如何编译这个a=a+b的? 除了暗中用一个临时变量,还有其它办法吗?
即这样:
temp=a+b; a=temp;
也就是说 a 不能同时被用来做加法,而在这个过程中又改变它的值.
更有甚者,(2)中的三行,每行都有一个变量同时出现在assignment的两边,那是不是
compiler要在暗中使用三个临时变量? 如果是这样,岂不是比在程序中明着使用
一个临时变量更糟糕吗?
家园 放到寄存器呀。。。 家园 不管放到什么地方， 都需要一个与临时变量相同大小的内存啊。
所以，不用临时变量的意义又在何处呢？
家园 是这样的，首先寄存器的读取速度远远快于内存。 寄存器在CPU内部，这样就不需要完成内存送到reg和reg存回内存这个步骤了，运算速度提高的不是一点半点，特别是复杂的算术运算。直接内存读取当然可以，但是人家编译器多半不肯那，
。其次，编译器在生成中间代码的时候，会采用线性优化的方法来分配寄存器，是否会多分配出一个Reg取决于最后优化的结果。所以对于使用临时变量的那段代码，这里的temp是占有一个内存空间还是寄存器很难说。
可能的一个结果就是给a或者b一个reg，其余在内存中完成操作。
---------------
LOAD a R0;
MOV b a;
MOV R0 b;
---------------
不使用temp的情况下，编译器多半就照着代码翻，加法和赋值的开销基本是一样的，所以代码可能不变。同样的，分配寄存器按照上面说的来进行。
家园 你说什么？你知道什么是寄存器吧？ 他只是举个例子。。。就如你没钱，一分钱你都要珍惜。。。如果你有一百万，随便请我几次客，可能你都会同意。。。搁浪财除外。。。
家园 不就是register吗？我的意思是--- 一个有optimzation功能的compiler，
对于
temp =a;
a = b;
b = temp;
这样的简单指令，也可以把temp的值放到register里（放一次），
而并不真正使用一个临时变量。
而对
a=a+b;
b=a-b;
a=a-b;
要放三次。
所以我还是不明白， 不使用临时变量有什么更好处呢？
家园 没什么大好处。。。 他只是假设其他不变，也不作什么OPTIMAZATION(那个功能有没有都是疑问，放正我不知道)，如此这般，就可以省点内存（其实现在内存这便宜，没人干这事，当年贵时都没人干）。。。
他只是用这个做例子，讲其他东西。。。你别老钻在这里出不来。。。
家园 这该至少讲到cache里去吧 楼主的东东是在机器语言才可比较
机器语言里（说错了的只管扔鸡蛋上来，俺有篮子接）
temp=a;
a=b;
b=temp.
是这样做的
控制器控制寄存器a放a
控制器控制寄存器b放b
控制器控制寄存器a取a给寄存器c放a
控制器控制寄存器b取b给寄存器a放b
控制器控制寄存器c取a给寄存器b放a
a = a+b;
b = a-b;
a = a-b;
是这样走
控制器控制寄存器a放a
控制器控制寄存器b放b
控制器控制寄存器a取a 寄存器b取b 给计算器计算a+b
控制器控制 计算器把a+b=A送寄存器a放A
控制器控制 寄存器a取A 寄存器b取b 给计算器计算A-b a+b-b
控制器控制 计算器把A-b=a送寄存器b放a
控制器控制 寄存器a取A 寄存器b取a 给计算器计算A-a a+b-a
控制器控制 计算器把A-b=b送寄存器a放b
所以牺牲空间换时间，牺牲时间换空间
家园 谢谢。 btw,一个没有optimization的compiler对于
a=a+b这样一个指令的处理，一般就是把它
编译成temp=a+b; a=temp; 就是暗中用临时变量。
类似这种问题在写一些C++的operators时常常遇到。
也有人写文章，教人怎么尽量避免这种暗中
临时变量。倒不是为了省内存，主要是速度问题。
扯远了，呵呵。谢谢讨论。