经典的面试题:不占用额外空间,交换两个变量a,b的值。
方法一:加减法。
实现代码:
a=a+b;
b=a-b;
a=a-b;
方法思想:用a先存下a,b二者的信息(a+b),后面的操作就可以进行分解,分解的过程中改变赋值对象就可以实现交换变量的值。
方法缺点:可能会导致溢出。可以交换整型和浮点型变量,但是因为减法的原因导致交换浮点型变量时会导致精度损失。
方法二:异或运算。(注:c语言中异或操作用^符号表示)
异或操作的特性:
1、一个数与本身异恒等于0,如5^5=0;
2、一个数与0异或恒等于本身,如5^0=5;
3、异或操作满足交换律,如1^2^3=2^1^3;
下面就利用这两个特性推导一下交换公式。
1、a=a^0=a^(b^b)=b^(a^b);
2、b=b^0=b^(a^a)=a^(a^b)=b^(a^b)^(a^b);
这样推导的原因是,后面可以利用a存下a,b二者的信息(a^b),然后与b进行异或操作后分别得到a、b,改变赋值对象就可以实现变量交换。
实现代码:(注解中的a,b均代表未交换前的a,b)
a=a^b;// =a^b
b=b^a;// =b^(a^b)=a^(b^b)=a^0
a=b^a; // =b^(a^b)^(a^b)