异或的性质及应用前言一、性质二、运用三、例题

122 阅读 0 评论 81 点赞

我是靠谱客的博主正直树叶，最近开发中收集的这篇文章主要介绍异或的性质及应用前言一、性质二、运用三、例题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

异或的性质及应用

前言
一、性质
二、运用
三、例题

前言

最近写了几道关于异或的题，在这里总结一下性质

一、性质

（定义 : 0 ^ 0 = 0 , 1 ^ 1 = 0 , 1 ^ 0 = 1 , 0 ^ 1 = 1 )
（就像不进位的加法）

交换律
结合律
对任意数x，我们有：x ^ x=0 , x ^ 0=x
自反性：a ^ b ^ b = a ^ 0 = a
故 a ^ b ^ c = d ^ e <=> d = a ^ b ^ c ^ e
a ^ b = (!a) ^ (!b)
!(a ^ b) = (!a) ^ b = a ^ (!b)

二、运用

交换两个数
好处是如交换 a 和 b可以节省一个中间变量的存储空间
a = a ^ b
b = b ^ a (b ^ a ^ b = a )
a = a ^ b (a ^ b ^ a = b )
异或前缀和，差分
排除偶次重复
例：在一个整数数组中，仅存在一个不重复的数字，其余数字均出现两次（或偶数次），找出不重复数字。
解：将所有数字异或即可得到答案
找数组中重复的数字
例：在一个整数数组中，只有一个数字重复出现了两次，其余的数字都只出现了一次，找出那个重复数字。
解：先将数组所有成员全部异或得到结果a，再将每种数字全部异或得到结果b，a ^ b 即为重复数字。
相比和式相减，能有效的防止溢出。

三、例题

Codeforces Round #717 (Div. 2)
B. AGAGA XOOORRR

Baby Ehab is known for his love for a certain operation. He has an array a of length n, and he decided to keep doing the following operation on it:

he picks 2 adjacent elements; he then removes them and places a single integer in their place: their bitwise XOR. Note that the length of the array decreases by one.
Now he asks you if he can make all elements of the array equal. Since babies like to make your life harder, he requires that you leave at least 2 elements remaining.

Input
The first line contains an integer t (1≤t≤15) — the number of test cases you need to solve.

The first line of each test case contains an integers n (2≤n≤2000) — the number of elements in the array a.

The second line contains n space-separated integers a1, a2, …, an (0≤ai<230) — the elements of the array a.

Output
If Baby Ehab can make all elements equal while leaving at least 2 elements standing, print “YES”. Otherwise, print “NO”.

Example
input
2
3
0 2 2
4
2 3 1 10
output
YES
NO

分析：
如果我们最后能得到所有元素都相同的一个数组，那么这个数组元素个数要么是奇数要么是偶数。
故直接上代码吧

法一：
#include<iostream>
#include<algorithm>
#include<cstdio>
#define N 2005
using namespace std;
int a[N];
inline int read()
{
char ch=getchar();
int flag=1,ans=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')
flag=-1;
ch=getchar();
}
while(ch>='0' && ch<= '9')
{
ans=ans*10+ch-'0';
ch=getchar();
}
return ans*flag;
}
int main()
{
int t;
t=read();
while(t--)
{
int n,sum=0,cnt=0;
n=read();
for(int i=0; i<n; i++)
{
a[i]=read();
sum ^= a[i];
}
if(sum==0)//结果为偶数直接结束，否则为奇数继续下面的判断
{
printf("YESn");
continue;
}
for(int i=0,j; i<n; i=j+1)//看每一个区间段都是否能为sum
{
j=i;
int now=a[i];
while(j < n-1 && now != sum)
{
j++;
now ^= a[j];
}
if(now==sum)
cnt++;
}
if(cnt>=3)
printf("YESn");
else
printf("NOn");
}
}

要是想用前缀和也可以

法二：
#include<iostream>
#define N 2005
using namespace std;
inline int read()
{
char ch=getchar();
int flag=1,ans=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')
flag=-1;
ch=getchar();
}
while(ch>='0' && ch<= '9')
{
ans=ans*10+ch-'0';
ch=getchar();
}
return ans*flag;
}
int a[N],sum[N];
bool ok;
int main()
{
int t,n;
t=read();
while(t--)
{
n=read();
for(int i=1; i<=n; i++)
{
a[i]=read();
sum[i]=sum[i-1]^a[i];
}
ok=false;
for(int i=1; i<n; i++)
{
if(sum[i]==(sum[i]^sum[n]))
{
ok=true;
break;
}
}
if(ok)
{
printf("YESn");
continue;
}
for(int i=1; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(sum[i]==(sum[i]^sum[j]) && sum[i]==(sum[j]^sum[n]))
{
ok=true;
break;
}
}
}
if(ok)
printf("YESn");
else
printf("NOn");
}
return 0;
}