大一计算机的自学总结：异或运算
前言
异或运算这个操作看上去很匪夷所思，实际上作用非常大。
一、异或运算的性质
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];
}
//性质4
cout<<"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 here
int 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即可。
总结
异或运算在解决某些问题时会有奇效，运用得当的话会非常厉害，只要能想出思路（汗）。