异或运算又称XOR或EOR 二进制中为对应位进行运算,若相同则为0,不同则为1.
简单性质:
- 0与x(任何数)异或运算得x
- 可以使用交换律和结合律
应用1:判断两个数是否相等
根据异或运算的定义,当两个数相同时,运算结果为0
应用2:通过异或运算将重复的两个数去除。
例:https://leetcode.com/problems/single-number/
应用3:交换两个变量的值without额外空间
a^=b
b^=a
a^=b
应用4:异或加密
异或运算
1、ab值相同 结果为1 不相同结果为0
2、不进位的加法
重要性质:1、同一个值异或两次结果为原数 2、满足交换律
应用:找出现奇数次的字符或数字#include <bits/stdc++.h> using namespace std; int main() { int n; int k=1; while(cin>>n) { char name[50]= {0},na[50]; for(int i=0; i<2*n-1; i++) { scanf("%s",na); for(int j=0; j<50; j++) name[j]=name[j]^na[j];//交换律 } printf("Scenario #%d\n",k); k++; printf("%s\n\n",name); } return 0; }
二进制运算
与&:0为空集,1为为空集,求交集 或 |:0为空集,1为为空集,求并集 取反~:1变0,0变1
二进制枚举
核心代码(题目特点是n的值较小,例如20左右)
for(int i=0; i<(1<<n); i++)//数位的移动,能取到范围内所有二进制数 { sum=0; for(int j=0; j<n; j++) { if((i&(1<<j))!=0)//判断数位上是否有数,只有一位1在向左移动 //if(i&(1<<j))也可 { sum=sum+x[j];//注意本处下标 } }
#include <bits/stdc++.h> using namespace std; int main() { int a; while(scanf("%d",&a)!=-1) { for(int u=0; u<a; u++) { int n; int sumx=0,sum=0; scanf("%d",&n); int x[25],res[25]= {0}; for(int i=0; i<n; i++) { scanf("%d",&x[i]); sum=sum+x[i]; } for(int i=0; i<(1<<n); i++) { sumx=0; int mark[25]={0}; for(int j=0; j<n; j++) { if((i&(1<<j))!=0) { sumx=sumx+x[j]; mark[j]=1; } } if(sumx<=(sum/2)) { for(int k=0; k<n; k++) { if(sumx+x[k]>(sum/2)&&mark[k]==0) res[k]++; } } } for(int i=0; i<n-1; i++) printf("%d ",res[i]); printf("%d\n",res[n-1]); } } return 0; }
#include <bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n) { for(int a=0; a<n; a++) { int m,jl; cin>>m; double x[25]= {0},y[25]= {0},z[25]= {0},ac[25]= {0},num=0,p,res=0; for(int i=0; i<m; i++) cin>>x[i]; for(int i=0; i<m; i++) cin>>y[i]; for(int i=0; i<m; i++) cin>>z[i]; cin>>jl; res=0; for(int i=0; i<m; i++) ac[i]=1-((1-x[i])*(1-y[i])*(1-z[i])); for(int i=0; i<(1<<m); i++) { num=0,p=1.0; for(int j=0; j<m; j++) { if(i&(1<<j)) { num++; p=p*ac[j]; } else p=p*(1-ac[j]); } if(num==jl) res=res+p; } printf("%.4lf\n",res); } } return 0; }
#include <bits/stdc++.h> using namespace std; int main() { int t1,res=0; scanf("%d",&t1); for(int i=0; i<(1<<15); i++) { int you=0,kou=0,t2; t2=t1; for(int j=0; j<15; j++) { if((i&(1<<j))!=0) { you++; t2=t2*2; } else { kou++; t2=t2-1; if(t2==0) break; } } if(t2==0&&you==5&&kou==10) res++; } cout<<res<<endl; return 0; }
此类题均是对模板的运用,明确取数是怎么取,根据题意套模板即可。
& 按位与 | 按位或 ^ 按位异或 1. 按位与运算 按位与运算符"&"是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时,结果位才为1 ,否则为0。参与运算的数以补码方式出现。 例如:9&5可写算式如下: 00001001 (9的二进制补码)&00000101 (5的二进制补码) 00000001 (1的二进制补码)可见9&5=1。 按位与运算通常用来对某些位清0或保留某些位。例如把a 的高八位清 0 , 保留低八位, 可作 a&255 运算 ( 255 的二进制数为0000000011111111)。 main(){ int a=9,b=5,c; c=a&b; printf("a=%d\nb=%d\nc=%d\n",a,b,c); } 2. 按位或运算 按位或运算符“|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1时,结果位就为1。参与运算的两个数均以补码出现。 例如:9|5可写算式如下: 00001001|00000101 00001101 (十进制为13)可见9|5=13 main(){ int a=9,b=5,c; c=a|b; printf("a=%d\nb=%d\nc=%d\n",a,b,c); } 3. 按位异或运算 按位异或运算符“^”是双目运算符。其功能是参与运算的两数各对应的二进位相异或,当两对应的二进位相异时,结果为1。参与运算数仍以补码出现,例如9^5可写成算式如下: 00001001^00000101 00001100 (十进制为12) main(){ int a=9; a=a^15; printf("a=%d\n",a); }
异或运算又称XOR或EOR 二进制中为对应位进行运算,若相同则为0,不同则为1.
简单性质:
- 0与x(任何数)异或运算得x
- 可以使用交换律和结合律
应用1:判断两个数是否相等
根据异或运算的定义,当两个数相同时,运算结果为0
应用2:通过异或运算将重复的两个数去除。
例:https://leetcode.com/problems/single-number/
应用3:交换两个变量的值without额外空间
a^=b
b^=a
a^=b
应用4:异或加密
转载于:https://www.cnblogs.com/aksdenjoy/p/5997526.html
异或运算可以理解为,两个数相同为0,不同为1。
负数以正数的补码表示二进制中负数的计算
原码:一个整数按照绝对值的大小转化成二进制的数
反码:将二进制数按位取反
补码:反码加 1
求负数的二进制数
以-14 举例原码:14 即 00000000 00000000 00000000 00001110
反码: 11111111 11111111 11111111 11110001
补码: 11111111 11111111 11111111 11110010
所以-14 的二进制是 11111111 11111111 11111111 11110010
已知二进制负数求原十进制数
(注意:java中 整数位 32位)
如二进制是 11111111 11111111 11111111 11110010得到反码减1 11111111 11111111 11111111 11110001
原码: 00000000 00000000 00000000 00001110
即 1110 = 14 所以取反 就是-14
<<左移运算符
1.将一个运算对象的各二进制位全部左移若干位(左边的二进制丢弃,右边补0)
11 << 2 = 44
-14 <<2 =-56
-14的二进制(11111111 11111111 11111111 11110010)左移2位 为
11111111 11111111 11111111 11001000 结果为(-56)
【补充】:对于左移,直观的理解为,对于正数来说,左移相当于乘以2(但效率比乘法高);对于负数来说,没有直观的理解。>>右移运算
将一个运算对象的各二进制位全部右移若干位,正数左补0,负数左补1.
4 >> 2 = 1;
-14 >> 2 = -4;
【补充】:对于右移,直观的理解为,对于正数来说,右1移相当于除以2(但效率比除法高);对于负数来说,没有直观的理解。