【c语言操作符系列1】^(异或操作符)讲解和多种例题详解
目录
一、^ 是什么（^称为异或）
是一种操作符，针对二进制异或而言的，两个数对应的二进制位相同，异或结果为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为3
int 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;//每组测试前一定要先初始化为0
if (n == 1)
{//只有一个数就不需要^去掉成对的了
scanf("%d", &x);
printf("%dn", x);
continue;
}
for (i = 0; i < n; i++)
{
scanf("%d", &x);
ret ^= x;
}
printf("%dn", 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=a
a = a ^ b;//a=a^ a^b=b
return 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向右移多少位的m
int m = 0;
for (i = 0; i < 32; i++)
{//x是两个只出现一次的数^后的结果
//x >> i & 1即这两个数不同的对应的一个二进制位数
//而我们现在要找这个二进制位数是几，赋给m
if ((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;
}
else
exit(-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;
}