不使用临时变量的swap
一道经典的面试题如下:两个int型变量a和b,不使用临时变量,交换它们的值。
答案相信大家都耳熟能详了:
a = a ^ b;
b = a ^ b;
a = a ^ b;
这段程序巧妙的安排运算顺序利用仅有的两个变量实现swap,它相当于这样一段程序:
c = a ^ b;
b = c ^ b;
a = c ^ b;
可以发现它的技巧简单的说就是把本应放在临时变量c中的值放在了原有变量a中,a的值被覆盖。不过为什么a的值可以被覆盖掉呢?对这段程序一种比较technical的解释就是,它利用了 ^ (异或)运算的性质:
c = a ^ b =>
a = b ^ c
b = a ^ c
但是,大家怎么想起来使用异或呢?使用异或有什么好处呢?两个变量既然要交换,那总归是要赋值的,而在C语言中有不能像Python那样直接一句搞定:
a , b = b , a
所以有这么一个结论:两个变量的最终赋值肯定是有先后顺序的。设a、b的初始值为A、B。假设b先完成赋值,即b已经存储了a的初始值A,现在要把b的初始值B放到a里面去。这时候可用的变量只有a了。也就是说在b完成赋值之后,a一定要包含b的初始值信息B,这样就或可能由a和b得到B,那么a一定包括A和B的信息。这里就是信息论的一点应用了。
可能的解
在C/C++语言中,怎么做运算才能保证把把两段信息放到一个变量中,知道一段信息后就可以分离出另一段信息呢?
最容易想到的运算可能是位运算。
C语言中的按位逻辑运算有这四种:
&:与,仅在两个operand均为1时为1
|:或,仅在两个operand均为0时为0
^:异或,当且仅当两个操作数相同时为0
~:非,取反操作
很容易看出,与运算的一个操作数为0时,结果永远是0,另一个操作数的信息就丢失了;或运算其中一个操作数为1时也会丢失另一个操作数的信息;而非运算是单目运算符;均不符合要求。再看看上文提到的异或的性质,则发现异或运算非常符合这个要求。2000年,异或的这个性质在通信领域带来了有影响力的理论:网络编码。有兴趣可以去wiki看一下。
学过数字电路的同学肯定记得,异或是可以使用与、或实现的:
a ^ b = ( a|b ) & ( ~( a&b ) )
这样,就可以使用与或得到同样的结果。
除了异或和与或,还有其他运算符合这个要求吗?其他可用的运算符只有加减乘除了……
有的,还不少!请看:
a = a + b;
b = a;
a = a - b;
减乘除同样可以满足这个要求,这里不做赘述。不过,加减乘除都要注意溢出与精确度的问题。
上述六种方法,乘除受到的限制很多,用于float型或许还可以。而基于异或和与或的方法都是较合适的方法。
很显然,推广到任何指针,都能把指向的对象视为一个int/char数组,完成类似的swap。
不使用临时变量的swap再思考 -- 六种解法,布布扣,bubuko.com
不使用临时变量的swap再思考 -- 六种解法
原文:http://blog.csdn.net/caozhk/article/details/20175441