连续多个数字或运算,与运算,异或运算 O(1)解决方法详解

以这道题为例

题目描述:

众所周知，位运算有与，或，异或三种。
与：相同位的两个数字都为 1，则为 1；若有一个不为 1，则为 0。
或：相同位只要一个为 1 即为 1。
异或：相同位不同则为 1，相同则为 0 。
小 Z 觉得她们非常的有趣，为了体现自己的强大，小 Z 一口气学会了三种运算，并出了一道题准备考考你。
给出 l,r 以及运算 ⨁ ，询问 [l,r] 的每一个数通过 ⨁ 运算后的值。
其中运算会给出，op = 1 运算为与，op=2 运算为或，op=3 运算为异或。
输入:
1
2 4 3
输出:
5

CF上的比赛通常充斥着各种的位运算,掌握位运算的板子感觉十分有用.偶然碰到这种连续数字位运算的题目,就准备好好分析一下

---

首先是与运算,我们观察一下我们的与运算的过程:

10101000  l
10111001  r

我们会发现$[l,r]$区间里会出现这样的一个数10110000(为了方便记为x),因为这个数的存在会使我们区间与的值直接变成了这个数.为什么呢,因为我们会发现这个x和l,r都有重合的部分,并且不重合的部分和$l$进行与运算都是0这就意味着我们除了不重合的部分显然都是0

那么我们怎么找到这个数呢,我们只要从前往后找两个数字的相同部分就行了后面的就拿0补充,不如上面的栗子,我们会发现从前往后重合部分是101,后面我们直接拿0补充就是我们最终的答案.

但是为什么这么做找到的肯定就是这个数字呢.我们想一下,我们有现在有两个二进制数字$l,r$,此时我们有一样的部分,然后从某一位(我们记为$K$)开始出现第一个不同,此时因为$r$是大于$l$,所以$r$第$K$位肯定是$1$,$l$第$K$位肯定是$0$,此时我们想一下,我们从$l$增长到$r$由于第k为刚开始是0,所以后面K位肯定会出现这种情况100...00(有k-1个0)此时由于这个值和我们的$l$进行与运算显然会将我们后面的所有数字都归$0$.然后第K位前面数字因为是重合的所以我们$[l,r]$区间的所有数字第K位之前的二进制位不可能和这个有差别.所以正确性是可以得到保证的

特殊的,我们会出现l,r二进制位长度不一样的情况,对于这种情况,我们需要将l前面补0.这样就会发现没有相同的二进制位.其实二进制长度不一样最后的答案肯定是0,但是为了写法方便,我们就和上述做法合起来了

下面是我们的与运算代码部分:

int get_AND(int l,int r) {
	int temp=r;int x=0;
	while(r) {
		if(l==r) {
			break;
		}
		l>>=1;r>>=1;
		x++;
	}
	return (temp>>x)<<x;
}

---

然后是我们的或运算部分:

我们的或运算部分,我们的或运算部分和与运算差不多.

我们的与运算因为找到了一个尾0的x导致我们所有的区间与尾数都是0,那么此时我们的或运算也是一样,我们也可以找到一个特殊的x,只不过此时这个特殊的x尾数都是1

和之前一样,我们同样找到$l,r$从前往后第一个不同的位置(我们记为K),此时显然的,我们K位置之前的所有二进制位是不变的(也可以看为是由R来决定的),然后同样的,我们会发现R的第K为肯定是1,L的第K位肯定是0,此时我们肯定能找到一个数字的后面K位二进制位是这样的,0111...111(有k-1个1),此时由于这个数字的关系,我们会发现后面K位进行或运算之后全部都是1

特殊的,我们也会出现二进制位长度不同的情况,此时我们同样采取补0的方式,就会发现显然全部最终都会变成1,与我们之前的做法并不矛盾

下面是我们的或运算代码部分:

int get_OR(int l,int r) {
	int temp=r;int x=0;
	while(r) {
		if(l==r) {
			break;
		}
		l>>=1;r>>=1;
		x++;
	}
	return temp|(((ll)1<<x)-1);
}

---

最后是我们的区间异或和

这一部分我们使用打表会很快发现规律,但是证明起来会比较麻烦,接下来我尽量的解释证明过程:

为了叙述方便,我们使用$F[l,r]$来表示区间$[l,r]$的异或和.那么根据我们亦或的性质,我们会发现显然有$F[l,r]=F[0,l-1]$^$F[0,r]$,所以此时我们只需要考虑$F[0,n]$怎么快速算出来即可

我们考虑$F[2^k,2^{k+1}-1]$,此时我们的数字大致成一下状态

100000000  k-1个0
111111111  k-1个1

我们发现我们的首位二进制位出现了$2^{k+1}-1-2^k+1$也就是$2^{k+1}-2^k$这是一个偶数,这说明了什么,也就是我们的首位的1异或到最后肯定是0,也就是不起效果的,也就是说我们此时的异或和靠的是后面的数字.所以我们有

$F[2^k,2^{k+1}-1]$$=F[0,2^{k+1}-2^k-1]=F[0,2^k-1]$(当k>=1时)

然后我们就有:
$F[0,2^{k+1}-1]=F[0,2^k-1]$^$F[2^k,2^{k+1}-1]$

$F[0,2^k-1]$^$F[2^k,2^{k+1}-1]=F[0,2^k-1]$ ^ $F[0,2^k-1]=0$

所以我们有$F[0,2^k-1]=0$ 当K>=2时

此时我们设存在一个k满足$2^k<=n<2^{k+1}$,也就是此时的K为n俄日进制位中最高的1的位置

此时我们有$F[0,n]=F[0,2^k-1]$^$F[2^k,n]=F[2^k,n]$

此时如果我们的n是奇数的话,也就是说区间$[2^k,n]$所有数字的最高位的1出现次数是偶数,也就是说这个1异或偶数次之后为0,我们最终的异或和和这个二进制位没有关系

我们有$F[2^k,n]=F[0,n-2^k]$,我们此时又会发现$n-2^k$和n奇偶性是一样的

所以我们可以不断重复上述过程(只要我们的k大于等于2),所以最终我们会发现我们这个区间的异或和是看我们的n的最后两位2进制位的情况(因为前面所有都是0)

所以我们有

$n\%4==1$时,$F[0,n]=$ 0^1=1

$n\%4==3$时,$F[0,n]=$ 0 ^ 1 ^ 2 ^ 3=0

然后是n为偶数的时候,此时我们的做法和奇数的时候做法是一样的,不同的是我们会发现现在的最高位的1出现的次数是奇数次的了,此时我们的所有位置的1都是保留的了(当然0肯定是保留的),所以此时虽然我们还是需要看末尾2位的情况,但是前面所有的二进制位和我们的n都是相同的

所以我们有

$n\%4==0$时, $F[0,n]=$ n-0+0=n

$n\%4==2$时, $F[0,n]=$ n-2+0 ^ 1 ^2=n+1

至此我们就解决了区间异或和的问题

下面是我们的代码部分:

int get_XOR(int l,int r) {
	l--;int x,y;
	if(l%4==1) x=1;
	else if(l%4==3) x=0;
	else if(l%4==0) x=l;
	else x=l+1;
	if(r%4==1) y=1;
	else if(r%4==3) y=0;
	else if(r%4==0) y=r;
	else y=r+1;
	return (x^y);
}

---

接下来是这道题的总代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int n,l,r,opt;
int get_AND(int l,int r) {
	int temp=r;int x=0;
	while(r) {
		if(l==r) {
			break;
		}
		l>>=1;r>>=1;
		x++;
	}
	return (temp>>x)<<x;
}
int get_OR(int l,int r) {
	int temp=r;int x=0;
	while(r) {
		if(l==r) {
			break;
		}
		l>>=1;r>>=1;
		x++;
	}
	return temp|(((ll)1<<x)-1);
}
int get_XOR(int l,int r) {
	l--;int x,y;
	if(l%4==1) x=1;
	else if(l%4==3) x=0;
	else if(l%4==0) x=l;
	else x=l+1;
	if(r%4==1) y=1;
	else if(r%4==3) y=0;
	else if(r%4==0) y=r;
	else y=r+1;
	return (x^y);
}
signed main() {
	n=read();
	while(n--) {
		l=read();r=read();opt=read();
		if(opt==1) {
			cout<<get_AND(l,r)<<endl;
		}else if(opt==2) {
			cout<<get_OR(l,r)<<endl;
		}else{
			cout<<get_XOR(l,r)<<endl;
		}
		
	}
	return 0;
}