DAY 1: C语言异或(^)以及按位与(&)的用法

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