算法题：如何不使用第三个寄存器完成两个寄存器内容的互换？【存疑】
今天论坛十大有个Google的Linux小组成立的帖子，为了上十大竟然有人抛出了一道算法题。
想上十大很简单。比如提一下：一个朋友因为谷歌面试他的时候问他“如何不使用第三个寄存器完成两个寄存器内容的互换？”他回答不出来，于是被拒了。然后他发誓再也不考虑去谷歌工作。各位有什么看法吗？技术和非技术的角度都可以。
学习的时候都是使用第三方temp来存储数据的，从来没想过不使用第三个寄存器。
下面有人给出的解法：
A + B -> A
A - B -> B
A - B -> A
可以做加减法么 - -
唔，看起来好像很简单。不过能想出来就不容易了。
还有人说使用XOR（异或）更快。
另外有人担心：
突然想到做加法可能会溢出，xor 应该没问题
写代码测试了一下，代码如下：
public static void main(String[] argv){
int[] a1 = {3,1,2,5,1,Integer.MIN_VALUE};
int[] a2 = {5,2,9,3,Integer.MAX_VALUE,1111};
System.out.println(Integer.MAX_VALUE);
System.out.println(Integer.MAX_VALUE+1);
System.out.println(Integer.MAX_VALUE+10);
System.out.println((Integer.MAX_VALUE+1)-1);
System.out.println((Integer.MAX_VALUE+10)-10);
System.out.println("Before Array Change. a1:"+
Utils.getArrayString(a1)+" a2:"+Utils.getArrayString(a2));
for(int i=0;i<a1.length;i++){
a1[i] = a1[i] ^ a2[i];
a2[i] = a1[i] ^ a2[i];
a1[i] = a1[i] ^ a2[i];
}
System.out.println("After Array Change with ^. a1:"+
Utils.getArrayString(a1)+" a2:"+Utils.getArrayString(a2));
for(int i=0;i<a1.length;i++){
a1[i] = a1[i] + a2[i];
a2[i] = a1[i] - a2[i];
a1[i] = a1[i] - a2[i];
}
System.out.println("After Array Change with +/-. a1:"+
Utils.getArrayString(a1)+" a2:"+Utils.getArrayString(a2));
}
前面是测试使用Integer的MAX_VALUE做加减是否会溢出，后面是测试^和+/-方法。
运行结果如下：
2147483647 -2147483648 -2147483639 2147483647 2147483647 Before Array Change. a1:3 1 2 5 1 -2147483648 a2:5 2 9 3 2147483647 1111 After Array Change with ^. a1:5 2 9 3 2147483647 1111 a2:3 1 2 5 1 -2147483648 After Array Change with +/-. a1:3 1 2 5 1 -2147483648 a2:5 2 9 3 2147483647 1111
可以看到，使用Integer的MAX_VALUE最后进行+/-计算后，最后还是会正常的。下面的结果也证实了这一点。
因此，使用这两种方法是都行的。
另外，还有童鞋提到了XCHG，查了一下百科如下：
交换指令XCHG是两个寄存器，寄存器和内存变量之间内容的交换指令，两个操作数的数据类型要相同，可以是一个字节，也可以是一个字。其指令格式如下：
XCHG Reg/Mem, Mem/Reg,Reg/Reg
不过还是没看明白具体是如何实现的【存疑】。
这个基本思想是，对于没有多余空间的情况下的互换操作，需要将其中一个数组的值的信息加到另一个数组中，之后再操作将二者分离出来。
跟之前做的一道数组题思路很像：统计一个数组中出现次数为k的数，要求不使用额外空间。或者是：对数组排序，要求不使用额外空间。
这时，可以将原数组乘以数组长度N，之后将数出现一次则+1，最后对N取余数就是出现次数。排序中也可以通过+1来标注位置等信息。
总的来说，需要使用方法（A+B或A^B或A*N都行），将新的信息保存进去，这样才能不使用额外空间。
参考资料：
