1.异或(^)的定义
在C语言中,异或操作符是^。异或操作符用于对两个操作数执行按位异或运算,即只有在两个操作数对应位不同时,结果为1。即 相同为0 不同为1。
2.重要结论
1.任何一个数,假定为a,0^a等于a(不进位计算求和),a^a等于0。
2.异或运算具有交换律和结合律。
3.例题(1)
已知一个数组之中有且仅有一个数字出现的次数为奇数,求这个出现次数为奇数的数字。
这个题正常做的话是很容易的,只需要便利整个数组,统计每个元素出现的次数,如果是奇数的就挑出来就完事了,但是时间和空间复杂度还是比较高的。所以我们可以利用异或运算的重要结论,即a^a=0,0^a=a与异或具有结合律和交换律。
思路:因为这个数组之中只有一个数字出现的次数是奇数次数,又如若一个数字出现偶数次,则这偶数个相同的数字异或的结果就是0,即a^a^a......^a=0。(偶数次重复,两两结合a^a=0,不会有遗留项),又如若一个数字出现奇数次a....^a=a(奇数次重复,两两结合后还会剩下一个a,即剩下0^a=a),所以整个数组经过这样的处理后就只剩下了奇数项,所以我们只需要便利整个数组,两两异或即可。
代码如下:
#include<stdio.h>
int main(void)
{
int n;
scanf("%d",&n);
int arr[n];
int i;
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
//定义一个变量,使之进行异或运算,初始化为0 最后变量的值即为奇数项
int target=0;
for(i=0;i<n;i++)
target^=arr[i];
printf("The targeting num is %d",target);
return 0;
}
4.按位与的定义
在C语言中,&
位运算符表示按位与操作。它会对两个操作数的每一位进行与操作,如果两个操作数的对应位都为1,则结果为1,否则为0。
例如,假设有两个8位的二进制数:10101010
和 11001100
,进行按位与操作后,结果如下:
1 0 1 0 1 0 1 0
&
1 1 0 0 1 1 0 0=
1 0 0 0 1 0 0 0
因此,10101010 & 11001100
的结果是 10001000
,即十进制中的 136。
5.例题(2)
已知一个数组之中有且仅有两个数字出现的次数为奇数,求这两个数字(从小到大)
与例题(1)不同的一点是,这个题目中出现了两个奇数,当然,我们仍然要将所有的偶数项都给去除掉,按照例题(1)的思路,仍然遍历整个数组,假定两个奇数次出现项分别为a和b,显然,此时的遍历结果就是 a^b 了,此时如果知道 a或者b 之中的任意一项,那么剩余一项也可以直接求出了,所以接下来的工作就是要求出这两项之中的其中一项。
此时注意到,由于a!=b,所以a^b!=0,所以根据异或运算的定义,即当对应位不同时,结果为1,所以a与b的二进制形式下,二者至少有一个位是不同的,即这个位上一个为0,一个为1。
例如 二进制下的5(二进制形式为101)与4(二进制形式为100),二者唯一的差别就在与最后一位的1 和 0。
类似地,我们可以求出任意一个两个奇数出现项所不同的位,利用这个位,可以将数组分为两大类,一类是这个位是0的(a存在),一类是这个位是1的(b存在),然后对其中的一个类进行遍历异或运算,这样去除这个类中的偶数项,就可以得到a与b其中的一个。//试着理解,确实有点拗口。
那么我们先来找出一个二者不同的位,假定EOR=a^b=1010101001(二进制形式),对其取反,
~EOR=0101010110(取反运算符,0变1,1变0),此时再让~EOR+1,结果即为0101010111,
此时利用&的性质,只有同一位置均为1时,才为1,所以EOR&(~EOR+1)=0000000001//这个公式是用来找EOR上最右侧的1的公式。(你也可以验证正确性)所以这个公式找到了a^b的最右侧的那个1,而这个1的出现,根据异或定义,就是二者不同位的所在地之一,即一个为0 一个为1。那么这个不同的位就找到了。
之后就可以根据这个位来对数组进行分类了,分成 0 1 两个大类 ,那么此时就可以让数组中的元素逐个与这个公式的结果进行比对,记作Judge。此时Judge为00000....1...0的形式,所以此时利用&的性质再好不过了,即同一位上都是1,结果才是1,所以如果arr[i]&Judge==0,则说明这一位一定为0,即可归类(注意:不要用arr[i]&Judge==1来判断,因为即使这一位为1,结果是可能大于1的,比如第二位都是1,则结果为2),经过遍历,则结果为a b之中的一个。
最后,利用a^b^a==b或者a^b^b==a,即可获得另一个值,问题就解决了!!!
代码如下:
#include<stdio.h>
int main(void)
{
int n,i;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
int eor=0;
for(i=0;i<n;i++)
eor^=arr[i];//此时结果就是 甲^乙,若知道其中一个 就可以求异或以解
//由于eor!=0 说明甲与乙之间一定有不同的位 0或者1
int eor_1=0;//定义新变量 以寻找a或者b的值
int Judge=eor&(~eor+1);//提取最右侧的1,来自甲或乙
for(i=0;i<n;i++)
if((arr[i]&Judge)==0)//结果为0 则说明相应位置一定为0
eor_1^=arr[i];//只要满足有这个1即可,结果即为a或b,再异或即可获得b或a。
printf("The Target Nums Are:\n");
printf("%d %d",eor_1,eor_1^eor);
return 0;
}
谢谢
2024/7/7
标签:奇数,int,结果,C语言,EOR,异或,按位,数组 From: https://blog.csdn.net/2301_80159044/article/details/140230879