大一计算机的自学总结：异或运算

前言

异或运算这个操作看上去很匪夷所思，实际上作用非常大。

一、异或运算的性质

1.异或运算就是无进位相加。

2.满足交换律、结合律。

3.0^n=n，n^n=0。

4.若集合B为集合A子集，集合A异或和为x，集合B异或和为y，则集合A-B异或和为x^y。

#include<bits/stdc++.h>
using namespace std;//打印二进制
void printBinary(int n)
{for(int i=15;i>=0;i--){cout<<((n&(1<<i))==0?"0":"1");}cout<<endl;
}int sumOfEor(vector<int>arr,int l,int r)
{int sum=arr[l];for(int i=l+1;i<=r;i++){sum^=arr[i];}return sum;
}int main()
{int n=78;cout<<"n in binary:";printBinary(n);//性质cout<<"0^n:";printBinary(0^n);cout<<"n^n:";printBinary(n^n);vector<int>arr(10);for(int i=0;i<10;i++){cin>>arr[i];}//性质4cout<<"sum of eor in 0~7:";cout<<sumOfEor(arr,0,7)<<endl;cout<<"sum of eor in 8~9:";cout<<sumOfEor(arr,8,9)<<endl;cout<<"sum of eor in 0~9:";cout<<sumOfEor(arr,0,9)<<endl;int result=sumOfEor(arr,0,7)^sumOfEor(arr,8,9);cout<<result<<endl;//交换两数int a,b;cout<<"a,b:"<<endl;cin>>a>>b; a=a^b;b=a^b;a=a^b;cout<<"a,b:"<<endl;cout<<a<<" "<<b;return 0;	
}

二、相关题目

1.获取最大值

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 获取最大值* @param a int整型 * @param b int整型 * @return int整型*/int sign(int n){return (n>>31)&1^1;}int getMax(int a, int b) {// write code hereint c=a-b;int signA=sign(a);int signB=sign(b);int signC=sign(c);int diffAB=signA^signB;//判断符号是否一样int sameAB=diffAB^1;int returnA=diffAB*signA+sameAB*signC;int returnB=returnA^1;return a*returnA+b*returnB;}
};

为了防止a-b这一步发生数据溢出，可以做以下操作：

首先不管三七二十一先算出a-b，然后分别取a，b，c的符号。这里取符号函数是让该数右移31位后，&1取此时最后一位，即第31位符号位的数，然后^1，若负数返回0，正数返回0。

之后判断a，b符号是否不相同并用变量记住信息，若不同则为1，然后^1就是符号是否相同。

然后，进行分类讨论。若a，b符号不同且a为负数，则b为正数，是最大值，returnA为0；或者若a，b符号相同且c为负数，则此时b也为最大值，否则a为最大值。

最后，按照returnA和returnB的信息来确定返回值。

这里的重点是用变量存储信息的思路！！！

2.丢失的数字

class Solution {
public:int missingNumber(vector<int>& nums) {int sum=0;for(int i=1;i<=nums.size();i++){sum^=i;}int sumNums=0;for(int i=0;i<nums.size();i++){sumNums^=nums[i];}return sum^sumNums;}
};

根据上述性质4，若已知整体0~n的异或和和数组异或和，只要将两者异或和求异或即为缺失数。

3.只出现一次的数字

class Solution {
public:int singleNumber(vector<int>& nums) {int num=0;for(int i=0;i<nums.size();i++){num^=nums[i];}return num;}
};

如果只有一个数字出现一次，其他数字出现两次，根据上述性质3，两相同数的异或结果为0，所以只需要求数组异或和即为只出现一次的数。

4.只出现一次的数字 III

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {vector<int>arr(2);long eor1=0;for(int i=0;i<nums.size();i++){eor1^=nums[i];}int rightOne=eor1&(-eor1);int eor2=0;for(int i=0;i<nums.size();i++){if((nums[i]&rightOne)==0){eor2^=nums[i];}}arr={(int)eor2,(int)eor1^eor2};return arr;}
};

若有两种数出现一次，思考此时两数的二进制以及数组异或和的二进制特征，可以发现（雾），因为两数不同，所以两数至少有一位的二进制状态不同，则数组异或和的二进制必存在一个1。

Brian-Kernighan算法：取一个数二进制最右侧1的状态——n&(-n)

根据这一位是否是1，可以将数组划分成两部分，所以只出现一次的这两种数必分别位于这两部分，又因为其他数都出现两次，所以将这一位为0的数求异或和即为两数中其中一位，根据性质3，eor1^eor2即为另一个数。

这个题已经有点考验思路了，思考的部分比较难想了。

5.只出现一次的数字 II

推广：数组中只有一个数出现少于m次，其他m次，返回这个数。

class Solution {
public:int singleNumber(vector<int>& nums) {vector<int>cnts(32,0);for(int i=0;i<nums.size();i++){for(int j=0;j<32;j++){cnts[j]+=(nums[i]>>j)&1;}}int ans=0;for(int i=0;i<32;i++){if(cnts[i]%3!=0){ans|=1<<i;}}return ans;}
};

这个题就更考验思维了，从二进制每个数位来考虑，统计每个数位上1出现的次数之和，若为m的倍数，则说明这个数在这位上为0；若%m!=0，则说明这个数在这位上为1。

之后开个32大小的数组存次数，最后根据次数是否为m的倍数往ans里填1即可。