什么是异或运算?就是不一样的位得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最下边小字。
