如何不使用任何额外空间实现两数相互交换

这个是Cracking the code interview的题目，如一般的交换函数我们都知道：

void mySwap(int &a, int &b)
{
	int t = b;
	b = a;
	a = t;
}

但是如何实现这个函数，不使用t呢？

有两种方法，第一种方法，利用减法实现：

void swapWithoutTemp(int &a, int &b)
{
	a = a-b;
	b = a+b;
	a = b-a;
}

这很好理解，难理解的是第二种方法，利用异或运算^位操作实现:

void swapBitOp(int &a, int &b)
{
	a = a^b;
	b = a^b;
	a = a^b;
}

理解起来还是有点难度。

那是利用了异或运算的特征，就是：

任何数与1异或都相当于取反操作，例如1^1=0; 0^1=1

任何数与0异或都相当于保留操作：1^0 = 1; 0^0 = 0;

理解方法：

由特殊推导一般，就是假设两个数都是一位二进制数，那么就算他们是多位二进制数的情况也是一样的。

假如b为1，就是对a做取反操作

a = a^b;就是对a取反了a = !a;

b = a^b; 就相当于!!a对a作了两次取反操作，那么就肯定等于a了。

a = a^b；就是 !a ^ a，那么就肯定等于1了.因为b=1的所以就是a = b了。

假如b为0，就是对a做保留操作

a = a^b;就是对a保留操作a = a;

b = a^b; 再次对a作保留操作，那么就肯定等于a了。

a = a^b；就是a ^ a，那么就肯定等于0了.因为b=0的所以就是a = b了。

两个关键点：

1 知道异或运算的特征

2 从一般推导到特殊