用异或运算进行两个值的交换

什么是异或运算?就是不一样的位得1，一样的位得0。

交换两个数的值可以有这骚操作

#include <stdio.h>

int main()
{
    int a = 1;
    int b = 2;
    a^=b^=a^=b;
    printf("%d %d",a,b);
    return 0;
}

它是如何做到的呢？

先来看这样一个例子：

#include <stdio.h>

int main()
{
    int a = 1;
    int b = 2;
    a = a + b;
    b = a - b;
    a = a - b;
    printf("%d %d",a,b);
    return 0;
}

原理就是相加后减己得他。

再来看异或交换如何做到的

• 首先明确一点，异或的位运算各位之间不会相互干扰，所以单独拿出一位来研究就行了。
  *先看两数相同的情况，即都为1或都为0，异或运算完的值为零，分别与0异或运算得他本身。
  • 两数不相同，一个1一个0的话。异或运算完是1，0与1异或得另一个数1，1与1异或得另一个数0。
  • 因为每一位都是如此，所以两个任意正整数都可以如此交换
• 与刚刚上边加减法交换的例子有什么关系吗？我们加两条新规定
  • 因为不存在进位所以我们定义1+1=0。
  • 定义1与0的减法只能大减小。
  • 再看上边的例子是不是就明白了。

效率如何

#include <stdio.h>
#include <time.h>

int main()
{

    int n=2000000000;
    while(n--){
        int a = 12345678;
        int b = 23456789;
//        int t=a;
//        a=b;
//        b=t;

        a^=b^=a^=b;
    }
    printf("%f\n",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}

加入第三个变量快一点点，以上数据分别为平均10s和平均12s。

那么问题来了含有负数的运算为什么也适用呢？

下次研究一下反码补码

---

参考《算法竞赛入门经典（第二版）》P9最下边小字。