【c语言操作符系列1】^(异或操作符)讲解和多种例题详解 |
您所在的位置：网站首页 › c语言如何写次方 › 【c语言操作符系列1】^(异或操作符)讲解和多种例题详解 |
【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 int missingNumber(int* nums, int numsSize) { int i = 0; int x = 0; for (i = 0; i > 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; } |
【本文地址】