【原】357，交换两个数字的值

1，临时变量实现

一般情况下交换两个数字的值，我们都会使用一个临时变量，像下面这样

1private void swap(int[] array, int i, int j) {
2    int temp = array[i];
3    array[i] = array[j];
4    array[j] = temp;
5}

当然这段代码非常简单，哪怕是刚接触过编程的同学也都能看的懂，我们今天要讲的肯定不是上面这段代码这么简单。那么除了上面这种方法还有没有其他的方法呢，在前面我们大致提到过3种实现方式，但具体细节没有详细讲解，今天我们就来一起看下，首先我们来看加法的实现

2，加法实现

1private void swap2(int[] array, int i, int j) {
2    if (i != j) {
3        array[i] = array[i] + array[j];
4        array[j] = array[i] - array[j];
5        array[i] = array[i] - array[j];
6    }
7}

1，第3行相当于把array[i]和array[j]的和存放到了array[i]中，这里用粗体表示。

2，第4行array[j]=array[i]-array[j]；相当于array[j]=(array[i]+array[j])-array[j]；也就是array[j]=array[i]，相当于把array[i]的值赋值给了array[j]。

3，第5行array[i]=array[i]-array[j]；因为上一步已经把array[i]赋值给了array[j]，所以这里相当于array[i]=(array[i]+array[j])-array[i]；也就是array[i]=array[j]；所以最终实现了array[i]和array[j]的数值交换。

上面其实很好理解，不需要再过多的讨论，下面我们来分析一下当array[i]和array[j]都非常大，相加的时候出现了数字溢出，该怎么办，其实这个不用担心的，因为如果出现了溢出，最多也只能溢出一位，而int类型的最高位是符号位，是1表示的是负数，0表示的是非负数，而这个符号位是可以参与加减运算的。

我们要明白一点，在计算机中所有的加减法其实都是加法，首先是把我们要计算的数转换为二进制，然后再进行运算，负数会以补码的形式存在，当然正数的补码和原码相同。我们先来看一段非常简单的代码

1public static void main(String[] args) {
2    int a = -3;
3    int b = -5;
4    int c = a - b;//其实相当于a+(-b)；
5    System.out.println("a的值是:" + a + "-->二进制：" + Util.bitInt32(a));
6    System.out.println("-b的值是:" + -b + "-->二进制：" + Util.bitInt32(-b));
7    System.out.println("c的值是:" + c + "--> 二进制：" + Util.bitInt32(c));
8}

看一下执行的结果

我们看到a+（-b）最高位其实已经出现了溢出，但这并不影响最终的结果。

3，减法实现

上面我们使用了加法交换两个数字的值，那么能不能使用减法呢，当然也是可以的，我们来看下代码

1private void swap3(int[] array, int i, int j) {
2    if (i != j) {
3        array[i] = array[i] - array[j];
4        array[j] = array[i] + array[j];
5        array[i] = array[j] - array[i];
6    }
7}

其实原理都是一样的。

4，乘法实现

那我们能不能使用乘法呢，我们知道加法最多往前进一位，而乘法就不一样了，他可能会往前进好多位。这个能不能使用就要看数字大小了，还有一些特殊数字，比如0。如果两个数字比较小且相乘的结果不会出现数字溢出，并且乘数中又没有0，那么是可以的，我们看下代码

1private void swap4(int[] array, int i, int j) {
2    if (i != j) {
3        array[i] = array[i] * array[j];
4        array[j] = array[i] / array[j];
5        array[i] = array[i] / array[j];
6    }
7}

但一般情况下我们不要写出这种代码，因为这样很可能就会出现数字溢出导致结果错误。如果是除法呢，那么这种就更不用再讨论了。

5，逻辑运算符实现

那么除了以上还有没有其他可能呢，比如使用&(与)和|(或)运算符能不能实现，当然也是可以的，我们看下代码

1private void swap5(int[] array, int i, int j) {
2    int temp = (array[i] & array[j]) ^ (array[i] | array[j]);
3    array[i] = temp ^ array[i];
4    array[j] = temp ^ array[j];
5}

这种实现很鸡肋，因为第2行其实就是int temp =array[i]^array[j] ，我故意写绕了，只是看大家能不能看的懂，虽然也能实现两个数字的交换，也不用考虑数字溢出问题，但对算法不好的同学来说也不是很好理解，原理就不在说了，我们可以随便找几个数据测试一下

1    int[] array = {15, 8, 7, -9, Integer.MAX_VALUE - 3, Integer.MAX_VALUE - 5};
2    System.out.println("数据交换之前的值");
3    Util.printIntArrays(array);
4    System.out.println();
5    new Swap().swap5(array, 0, 1);
6    new Swap().swap5(array, 2, 3);
7    new Swap().swap5(array, 4, 5);
8    System.out.println("两两交换之后的值");
9    Util.printIntArrays(array);

运行结果如下

每两个两个的交换，最终也是实现了数值的交换。

6，异或运算符实现

看了上面的代码我们是不是有点启发，因为异或运算其实还是很强大的，比如0^a=a，a^a=0，同时他还满足交换律，比如a^b^c=a^c^b，^(异或运算)不像&(与)和|(或)那么傻，^(异或运算)有记忆功能，他和+，-，*，÷这些符号一样，如果知道结果和其中的一个值就可以确定另外一个值了，而&(与)和|(或)就不能完全确定了。比如a&1=1或者a&1=0，我们可以确定a的值，但如果a&0=0，我们就无法确定a究竟是0还是1了。那我们这里就仿照+运算符来写一个，代码很简单

1private void swap6(int[] array, int i, int j) {
2    if (i != j) {
3        array[i] ^= array[j];
4        array[j] ^= array[i];
5        array[i] ^= array[j];
6    }
7}

所以交换两个数字的值并不是必须要有一个临时变量，写法也不仅仅局限于一种，只要我们多思考，还是有很多种写法的。