一、^ 是什么（^称为异或）

二、^的规律(特点)

三、可利用^秒杀的常见例题（重点）

1、消失的数字

2、不一样的人生密码

3、交换两个数（不能创建中间变量）

4、找出只出现一个的两个数字

一、^ 是什么（^称为异或）

是一种操作符，针对二进制异或而言的，两个数对应的二进制位相同，异或结果为0，不同，异或结果为1。

例如：1^2

1的二进制位：

000000000 00000000 00000000 00000001

2的二进制位：

000000000 00000000 00000000 00000010

1^2异或后:

000000000 00000000 00000000 00000011 即为3

异或它在很多题型中都会用的到，我们利用它本身的常见规律可以秒杀很多题。

二、^的规律(特点)

特点1、大小相同的数字异或为0，任何数字异或0均为本身(可以自己写两个数的二进制位进行验证)

例如：1^1=0, 2^0=2 ,3^0=3

特点2、A^B^B = A 由1可得2 因为B^B=0 0^A=A

特点3、符合结合律和交换律

三、可利用^秒杀的常见例题（重点）

1、消失的数字

题目描述：数组nums包含从0到n的所有整数(nums是不重复的无序整形数组)，但其中缺失了一个。请找出缺失的那个整数，时间复杂度最大为o(n)。

题目解释：比如n为3，那么nums数组本应包括0 1 2 3。但你现在可能就包含了0 1 3,假设丢了2( 但其中丢失哪一个你并不知道)，就让你找丢失的这个2.

思路：0到n每个数^一遍，数组中存在的每一个元素^一遍，两者再^一下就找到缺失的数字了

比如n=3(假设数组中缺失了2),则0到n每个数^一下即 0^1^2^3

再^数组中存在的每一个元素:0^1^3

两者再^一下：0^1^2^3 ^ 0^1^3 = 2

这个是根据特点一和特点三推得，因为两个相同的数^后为0,一个数^0后=本身，所以就找到这个消失的数字了

代码如下:


#include<stdio.h>
int missingNumber(int* nums, int numsSize)
{int i = 0;int x = 0;for (i = 0; i <= numsSize; i++){x ^= i;}for (i = 0; i < numsSize; i++){x ^= nums[i];}return x;
}
int main()
{	//假设n为3int nums[] = { 0,1,3 };int n = 0;scanf("%d", &n);//数组的大小就是n,因为是0~n，本来应该有0 1 2 3的// 但现在只有0 1 3所以n就是数组此时的大小//如果不缺失一个数字，数组大小是n+1的printf("%d",missingNumber(nums, n));return 0;
}

2、不一样的人生密码

题目描述：每个人都有一个人生密码，只有两个人的人生密码相同，才能走到一起，给出n个人的人生密码，n是奇数，其中只有一个人的人生密码是单独的，其他都是成对的，请你找出不成对的那一个。(时间限制400ms)

输入格式：

多组测试，每行第一个数为n(1<=n<=1000000),后面有n个正整数，表示n个人的人生密码，n值为0时表示输入结束。

输出格式：

输出那个不成对的人生密码。

输入样例：

3 8 9 8

5 120 10 120 10 85

0

输出样例:

9

85

思路：这道题跟第一题思路差不多，因为只有一个是单独的，那么把输入的所有数^一遍，得到的不就是那个单独的数字，因为两个相同的数字^后一定为0,那个单独的数再^0一定得到那个单独的数了 ,但是要考虑只有一个数字的话，就不用^了，直接找到了

代码如下：

#include<stdio.h>int main()
{int ret = 0, n = 0,i = 0,x = 0;while (~scanf("%d", &n) && n != 0){//判断这么写是因为&&具有左结合性ret = 0;//每组测试前一定要先初始化为0if (n == 1){//只有一个数就不需要^去掉成对的了scanf("%d", &x);printf("%d\n", x);continue;}for (i = 0; i < n; i++){scanf("%d", &x);ret ^= x;}printf("%d\n", ret);}return 0;
}

3、交换两个数（不能创建中间变量）

题目要求：不能创建中间变量交换两个数

思路：运用特点二A^B^B=A和特点三的交换律即可求解

#include<stdio.h>
int main()
{int a = 0, b = 0;a = a ^ b;b = b ^ a;//b=b^ a^b=aa = a ^ b;//a=a^ a^b=breturn 0;
}

4、找出只出现一个的两个数字

题目描述：一个整形数组arr里除了两个数字只出现一次外，其他数字都出现了两次。请你找出这两个只出现一次的数字。要求时间复杂度：o(n),空间复杂度:o(1)。

如 int arr[] = {1,1,2,2,3,3,4,5,5,6,7,7,8,8,9,9}

则这两个你要找的数字为4,6

思路：要返回两个值，可以返回一个储存这两个值的数组，即指针。那么这道题其实就是在第二题不一样的人生密码上加了一点难度，第二题是找一个（找一个就很好处理了），而这道题是找两个。难就难在两个怎么处理，我们可以试试把这两个数字分离，转换成两组，每一组都是一道"不一样的人生数字"的题，即这两组，第一组包含了第一个只出现1次的数字，第二组包含了第二个只出现1次的数字。（因为只出现一次，说明这两个数肯定不相同，所以可以分离)。重点是如何分离

———— 分离这两个数的过程 ————

我们只需找到这两个数不同的一个二进制位就可以，怎么找？两个数^后的结果中二进制位为1的，就说明两个数原来的这个位置的二进制位不同（肯定一个是0，一个是1），我们只需找到一个两者^后为1的二进制位即可。只要数组中元素对应的这个二进制位为1的数值分到一组，为0的分到另一组。我们就可以把这两个只出现一次的数区分为两组。那么这两组就变成：第一组有第一个数和其他n组成对的数，第二组有第二个数和其他m组成对的数。这下是不是就变成两个“不一样的人生密码”的例题2了吧？求两次是不是就可以了！

代码如下：

注：详细的代码理解全在代码中！

#include<stdio.h>
#include<stdlib.h>int* Find(int* arr, int numSize)
{
//1、得到两个只出现一次的数^后的结果int x = 0, i = 0;for (i = 0; i < numSize; i++){x ^= arr[i];//得到两个只出现一次的数的^后的结果}
//2、定位这个结果中一个二进制位为1时,需要x向右移多少位的mint m = 0;for (i = 0; i < 32; i++){//x是两个只出现一次的数^后的结果//x >> i & 1即这两个数不同的对应的一个二进制位数//而我们现在要找这个二进制位数是几，赋给mif ((x >> i & 1) == 1)//别忘了要加(),因为&优先级比==优先级低{//x>>i是遍历x的32位二进制位的意思，而我们要的是//x向右多少位的二进制才为1，我们找到一个二进制为1的即可m = i;break;}}
//3、将这两个只出现一次的数分为两组int x1 = 0, x2 = 0;for (i = 0; i < numSize; i++){if ((arr[i] >> m & 1) == 1){x1 ^= arr[i];//这一组中成对的数^后会变为0//所以x1最后的结果为两个出现一次的数的其中一个}if ((arr[i] >> m & 1) == 0){x2 ^= arr[i];//这一组中成对的数^后会变为0//所以x2最后的结果为两个出现一次的数的另一个}}
//4、创建数组返回这两个值int* a = (int*)malloc(sizeof(int)*2);//动态开辟，出了函数不会销毁//如果是静态开辟，出了函数，虽然原来a的地址还在，但是他的内容已经不属于a了//典型的返回栈空间地址带来的危害if (a != NULL){a[0] = x1;a[1] = x2;}elseexit(-1);return a;
}
int main()
{int arr[] = { 1,1,2,2,3,3,4,5,5,6,7,7,8,8,9,9 };int size = sizeof(arr) / sizeof(arr[0]);int* ptr = Find(arr, size);printf("%d %d", ptr[0], ptr[1]);free(ptr);ptr = NULL;return 0;
}