【c语言操作符系列1】^(异或操作符)讲解和多种例题详解

目录

一、^ 是什么(^称为异或)

二、^的规律(特点)

三、可利用^秒杀的常见例题(重点)

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为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;
}