异或操作

^

异或操作基本的性质：

1 ^ 1 = 0

1 ^ 0 = 1

0 ^ 0 = 0

0 ^ 1 = 1

不同才为1；

具体如下：

1011010 ^ 1101100 = 0110110

而这个操作，可以看做：无进位加法

即上述异或操作按位相加不进位：1+1=0；0+0=0；1+0=1；0+1=1；

且异或操作满足交换律和结合律：

1. a ^ b = b ^ a
2. ( a ^ b ) ^ c = a ^ ( b ^ c )
3. a ^ a = 0
4. a ^ 0 = a

由此可以得出，一大坨数进行异或操作，不论谁先异或谁，其最后的结果都是一样的。

在这个交换2个数的Java代码中：

public static void Swap(int[] a,int i,int j){
//		int temp;
//		temp = a[i];
//		a[i] = a[MinIndex];
//		a[MinIndex] = temp;
		a[i] = a[i] ^ a[j];
		a[j] = a[i] ^ a[j];
		a[i] = a[i] ^ a[j];
	}

原写法是定义一个临时变量temp，来进行交换。（很常规）

下面的写法是利用了3个异或操作完成了交换，且没有额外分配空间。

1. a[i] = a[i] ^ a[j],此时a[i]结果为异或后的值
2. a[j] = a[i] ^ a[j],即a[j] = a[i] ^ a[j] ^ a[j],因为a[j] ^ a[j] 为0，所以此时a[j] = a[i]；此a[i]为初始传入值，而现在的a[i]还为：a[i] ^ a[j]
3. a[i] = a[i] ^ a[j]，即a[i] = a[i] ^ a[j] ^ a[i],所以a[i] = a[j]，完成了交换。