位运算的一些常识+01tired

文章目录

• 位运算的常识
• • • 常见性质
    • 位运算例题

位运算的常识

常见性质

• 性质1： $a\oplus b<=a+b$
• 性质2： 位运算时，每位元素相互独立
• 性质3： a l ⊕ a l + 1 ⊕ … … ⊕ a r − 1 ⊕ a r = s [ r ] ⊕ s [ l − 1 ] a_l⊕a_{l+1}⊕……⊕a_{r-1}⊕a_{r}=s[r]⊕s[l-1] al​⊕al+1​⊕……⊕ar−1​⊕ar​=s[r]⊕s[l−1]

位运算例题

例题1：关于异或

例题1

• 问题描述： 将 n 个数任意分成若干组，定义每个组的权值为该组所有数的异或和，求最小权值之和
• 问题分析： 由于 $a\oplus b<=a+b$，所以任意两个数，不分组比分组更优，即所有数全在一个组时最优。

代码如下

int main(){long long n,a,ans=0;scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a);ans=ans^a;}cout<<ans;
}

例题2：关于与，或，异或

例题2

• 问题描述： 从 [0,m] 从找到一个数，使得它经过 n 次位运算后，得到的数ans最大
• 问题分析： 因为位运算时，每位元素相互独立，我们可以先预处理出每一位分别为 0 和 1 时的那一位的最后的答案，最后判断 ans 的每一位数是否为 0 或 1 ，因此我们构造两个数 int x=0，y=-1，分别为全 0 和全 1 ，并令其经过 n 次位运算。这样就可以得到每一位分别为 0 和 1 时最后那一位的答案了。

代码如下

int x=0,y=-1;
int main() {int n,m,k;string op;scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) {cin>>op>>k;if(op=="AND")x=x&k,y=y&k;if(op=="OR")x=x|k,y=y|k;if(op=="XOR")x=x^k,y=y^k;}int ans=0;for(int i=29; i>=0; i--) { //判断从右往左数第i+1位if(x>>i&1)ans+=1<<i;else if((y>>i&1)&&((1<<i)<=m))ans+=1<<i,m-=(1<<i);}cout<<ans;
}

例题3：位运算的转化

例题3

• 题目描述： 求 $mex(n\oplus 0,n\oplus 1,n\oplus 2,\dots ,n\oplus m)$，$0<=n,m<=1e9$
• 问题分析： 设 $mex()=k$，即 k 不存在于序列中，反过来思考：n xor {0,1,2……m}，均不等于k，那么 $n\oplus k>=m+1$ 。即求一个最小的 k ，使得式子成立。这个式子就简单多了，我们只需要按位一位一位异或就好。遍历考虑 n 和 m+1 的每一位即可。

int main() {long long T,n,m;cin>>T;while(T--) {cin>>n>>m;m++;long long ans=0,flag=1;for(int i=32; i>=0; i--) {if(flag==1) {if(((1ll<<i)&n)&&((1ll<<i)&m))ans=ans*2+0;if(((1ll<<i)&n)&&((1ll<<i)&m)==0)ans=ans*2+0,flag=0;if(((1ll<<i)&n)==0&&((1ll<<i)&m))ans=ans*2+1;if(((1ll<<i)&n)==0&&((1ll<<i)&m)==0)ans=ans*2+0;}else ans=ans*2;}cout<<ans<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！