微信微网站是什么格式,代理网页地址,建筑网官网登录,网络运维工程师证书有用吗前言
异或运算这个操作看上去很匪夷所思#xff0c;实际上作用非常大。
一、异或运算的性质
1.异或运算就是无进位相加。
2.满足交换律、结合律。
3.0^nn#xff0c;n^n0。
4.若集合B为集合A子集#xff0c;集合A异或和为x#xff0c;集合B异或和为y#xff0c;则集…前言
异或运算这个操作看上去很匪夷所思实际上作用非常大。
一、异或运算的性质
1.异或运算就是无进位相加。
2.满足交换律、结合律。
3.0^nnn^n0。
4.若集合B为集合A子集集合A异或和为x集合B异或和为y则集合A-B异或和为x^y。
#includebits/stdc.h
using namespace std;//打印二进制
void printBinary(int n)
{for(int i15;i0;i--){cout((n(1i))0?0:1);}coutendl;
}int sumOfEor(vectorintarr,int l,int r)
{int sumarr[l];for(int il1;ir;i){sum^arr[i];}return sum;
}int main()
{int n78;coutn in binary:;printBinary(n);//性质cout0^n:;printBinary(0^n);coutn^n:;printBinary(n^n);vectorintarr(10);for(int i0;i10;i){cinarr[i];}//性质4coutsum of eor in 0~7:;coutsumOfEor(arr,0,7)endl;coutsum of eor in 8~9:;coutsumOfEor(arr,8,9)endl;coutsum of eor in 0~9:;coutsumOfEor(arr,0,9)endl;int resultsumOfEor(arr,0,7)^sumOfEor(arr,8,9);coutresultendl;//交换两数int a,b;couta,b:endl;cinab; aa^b;ba^b;aa^b;couta,b:endl;couta b;return 0;
}
二、相关题目
1.获取最大值
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 获取最大值* param a int整型 * param b int整型 * return int整型*/int sign(int n){return (n31)1^1;}int getMax(int a, int b) {// write code hereint ca-b;int signAsign(a);int signBsign(b);int signCsign(c);int diffABsignA^signB;//判断符号是否一样int sameABdiffAB^1;int returnAdiffAB*signAsameAB*signC;int returnBreturnA^1;return a*returnAb*returnB;}
}; 为了防止a-b这一步发生数据溢出可以做以下操作
首先不管三七二十一先算出a-b然后分别取abc的符号。这里取符号函数是让该数右移31位后1取此时最后一位即第31位符号位的数然后^1若负数返回0正数返回0。
之后判断ab符号是否不相同并用变量记住信息若不同则为1然后^1就是符号是否相同。
然后进行分类讨论。若ab符号不同且a为负数则b为正数是最大值returnA为0或者若ab符号相同且c为负数则此时b也为最大值否则a为最大值。
最后按照returnA和returnB的信息来确定返回值。
这里的重点是用变量存储信息的思路
2.丢失的数字
class Solution {
public:int missingNumber(vectorint nums) {int sum0;for(int i1;inums.size();i){sum^i;}int sumNums0;for(int i0;inums.size();i){sumNums^nums[i];}return sum^sumNums;}
}; 根据上述性质4若已知整体0~n的异或和和数组异或和只要将两者异或和求异或即为缺失数。
3.只出现一次的数字
class Solution {
public:int singleNumber(vectorint nums) {int num0;for(int i0;inums.size();i){num^nums[i];}return num;}
}; 如果只有一个数字出现一次其他数字出现两次根据上述性质3两相同数的异或结果为0所以只需要求数组异或和即为只出现一次的数。
4.只出现一次的数字 III
class Solution {
public:vectorint singleNumber(vectorint nums) {vectorintarr(2);long eor10;for(int i0;inums.size();i){eor1^nums[i];}int rightOneeor1(-eor1);int eor20;for(int i0;inums.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的数求异或和即为两数中其中一位根据性质3eor1^eor2即为另一个数。
这个题已经有点考验思路了思考的部分比较难想了。 5.只出现一次的数字 II
推广数组中只有一个数出现少于m次其他m次返回这个数。
class Solution {
public:int singleNumber(vectorint nums) {vectorintcnts(32,0);for(int i0;inums.size();i){for(int j0;j32;j){cnts[j](nums[i]j)1;}}int ans0;for(int i0;i32;i){if(cnts[i]%3!0){ans|1i;}}return ans;}
};
这个题就更考验思维了从二进制每个数位来考虑统计每个数位上1出现的次数之和若为m的倍数则说明这个数在这位上为0若%m!0则说明这个数在这位上为1。
之后开个32大小的数组存次数最后根据次数是否为m的倍数往ans里填1即可。
总结
异或运算在解决某些问题时会有奇效运用得当的话会非常厉害只要能想出思路汗。
END
