C++||与或非异或二进制枚举

1. 与或非
2. 异或
3. 二进制枚举&&二进制移位符

1.与或非

                                      **|以下内容均在二进制下操作|**

1.1 与

符号 ：&
性质 ：每一位比较，相同为1，不同为0 //只取相同位次的相同数
例：
A=60（11 1100）
B=13（00 1101） //如果没有没有就补0，让他们位次对上
A&B =（00 1100）=12 //除了1 1才是1，其他都是0

1.2 或

符号：|
性质：每一位比较，相同为0，不同为1 //对照着 与 来理解
例：
A= 60（11 1100）
B= 13（00 1101）
A|B =（11 0001）=61 //注意是相同的1，0和0也是相同的，但结果是0，0和1结果是1

1.3 非 (按位取反)

符号：~
性质：取相反的数
例：
A= 60（11 1100）//我对不齐，有笔就笔划笔划就清楚多了
~A=195 （00 0011） //对着取就行了
//看到这，单个知识没啥用，组合起来用处就大了。下面有用

2.异或

符号：^ //很重要
性质：上图

//个人理解：相同为0，不同为一（注意和上面的 与 或 区别开）
例：
A=60（11 1100）
B=13（00 1101）
A^B=（11 0001）=49 //相同都取0（无论是 1 相同，还是 0 相同），不同取1

注 ”负负得正“，一个道理
异或是不进位的加法（0+0=0，1+0=1，1+1=0（应该进位，但是没有））
想深入了解的同学，附上一个知乎的回答
如何理解「异或」的含义？：：排异外
—》有啥用呢？用处可大了，用来找不同

异或例题1

见例题 林大oj1172
**这题的意思就是找数，只出现一次的数
上码

#include <bits/stdc++.h>  //万能开头
using namespace std;
int main()
{int n,x,ans;while(scanf("%d",&n)!=-1){ans=0;//用下面的数据cin>>ans;//假设第一个数是 3n=n-1;//第二个数开始while(n--)//（这里是个数递减）{scanf("%d",&x);//读下一个数 2ans=ans^x;/*3和2进行异或运算——>   2(010)^3(011)=1(001)读取下一个数 7（111），7（111）^1(001)=6(110)读取下一个数 2（010），2（010）^6(110)=4(100)读取下一个数 1（001），1（001）^4(100)=5(101)读取下一个数 7（111），7（111）^5(101)=2(010)读取下一个数 3（011），3（011）^2(010)=1(001)我们换个理解，把二进制的限制丢开（二进制很蒙人），如果两个数相同，消灭，不同，留下（这个是终极理解，也就是目的。过程我们用二进制实现）*/}printf("%d\n",ans);}return 0;
}
/* 
样例输入
7
3 2 7 2 1 7 3
样例输出
1
*/

异或 能把不同的那个找出来
Over.

异或例题2

*****找字符串的不同
上题
林大oj643 找名字//还是要学点英语好。。
士兵们，上码！
//理解：点名，第一份是完整名单，第二份是现场签到的名单。异或消掉相同的就知道谁没到了

#include <bits/stdc++.h>
using namespace std;
int n,i,t,j;
string na,ne;
int main()
{t=0;while(scanf("%d",&n)!=-1){cin>>na;for(int i=0; i<n*2-2; i++)//第一个数已经被读走，因为有一个人没到所以要减1，共减2{cin>>ne;for(j=0; j<max(na.length(),ne.length()); j++)/*c++里的max很香。.length()的意思是这个字符串长度多少。从大的数开始，因为其二进制位数长，如果从小的开始就会丢（大数就会被迫变小来和小数比较）*/na[j]=ne[j]^na[j];//因为在表里都对应了一个数字，还是回到了找数字是否相同问题}t++;printf("Scenario #%d\n",t);printf("%s\n\n",na.c_str());/*这个 .c_str()的意思是把字符串中的东西给你原封不动输出来。我也不是很懂，好像和string配套用。反正挺香，先记住它*/}return 0;/*3ABCBC*/
}

————异或完了，就这么用。找不同。
需要另外学习的有 .length()，.c_str()，max()

3.二进制枚举

3.1移位

符号： >> 右移（减） <<左移（加）
性质： 两种形式：

1. A=5(0101) A<<1 -----左移一位 A=10(1010) //就是把这个数乘2,为啥不直接乘。因为二进制是亲儿子（更快）
2. A=5(0101) 1<<A -------左移A位 A=32（100000）。这个很重要，一会用题说明。
   循环二进制的数，原来用for循环十进制，现在变成循环二进制
   右移同上。

直接用题理解吧。

二进制枚举例题1

林大 oj 1205 和为k
这里开始会用到上面说过的 与

#include <bits/stdc++.h>
using namespace std;
int n,k,i,j,a[21],sum;
int main()
{while(cin>>n>>k){for(i=0; i<n; i++)cin>>a[i];int f=0;//还是枚举的思想。看有几层循环for(i=0; i<(1<<n); i++)//上面说的，用二进制循环{sum=0;for(j=0; j<n; j++)if(i&(1<<j))//这里有 与 和 移位。如果 i 和 j 相同，& 出来就是0.这样就不会重复加了sum=sum+a[j];/*用 if 判断“真”、“假”分为两种，一种是数值是否为零， 另一种是表达式是否成立。*/if(sum==k){printf("Yes\n");f=1;break;}}if(f==0)printf("No\n");}return 0;/*input5 132 4 6 8 10outputNO*/
}

二进制枚举例题2

林大 oj 1505 陈老师加油
理解：注意别油早没了，车还能继续跑

#include <bits/stdc++.h>using namespace std;
int t,ans,i;
int main()
{while(cin>>t){ans=0;//还是枚举的思想。for(i=0; i<(1<<15); i++)//它只有两层循环，加油站和路口是一个性质。{int lu=0,jia=0,now=t;//第一个循环给数for(int j=0; j<15; j++)//第二个循环比较{if(i&(1<<j))//别和自己比就行（用 与 运算排除掉）{lu++;now--;if(now<=0)break;//油都没了这必跑不了了}else{jia++;now*=2;}}if(lu==10&&jia==5&&now==0)//只有油没了，路口加油站全过才能通过ans++;}printf("%d\n",ans);}return 0;
}

二进制枚举例题3

林大 oj 1518 纸牌求和
//同上面的 和为k 一个意思，但你得循环完，不提前结束

#include <bits/stdc++.h>
using namespace std;
int a[21],p,n,i,sum,j,ans;
int main()
{while(scanf("%d",&n)!=-1){cin>>p;for(i=0; i<n; i++)cin>>a[i];ans=0;for(i=0; i<(1<<n); i++){sum=0;for(j=0; j<n; j++){if(i&(1<<j))sum=sum+a[j];}if(sum==p)ans++;}printf("%d\n",ans);}return 0;
}

不多说，有请（看）下一位（道）选手（题），开始你的表演（做题）

二进制枚举例题4

林大 oj 1641 权利指数
//这题比较麻烦些，暴力它
//开个一样的数组记它是不是在关键团队里面

#include <bits/stdc++.h>
using namespace std;
int n,t,i,j,sum,tmp,a[21],ans[21],flag[21];//flag就是判断
int main()
{while(scanf("%d",&t)!=-1){while(t--){cin>>n;sum=0;for(i=0; i<n; i++){cin>>a[i];sum+=a[i];//求总票数sum。*=这一类的符号还是好用的。}sum=sum/2;//先除了，懒memset(ans,0,sizeof(ans));//好习惯，归0；C++的好处，不用for循环归0for(i=0; i<(1<<n); i++){tmp=0;memset(flag,0,sizeof(flag));for(j=0; j<n; j++){if(i&(1<<j)){tmp=tmp+a[j];flag[j]=1;//如果这个数在里面，记下它}}if(tmp<=sum)//还有一种思路，从已经超过的组里面找关键票{for(j=0; j<n; j++){if(tmp+a[j]>sum&&flag[j]==0)ans[j]++;//两个条件都得满足：1.是关键票 2.不在组里面}}}for(i=0; i<n-1; i++)printf("%d ",ans[i]);printf("%d\n",ans[n-1]);//注意格式，中间空格尾数换行}}return 0;
}

二进制枚举例题5

林大 oj 1285 趣味解题
//涨知识，错了很心疼
//这题要把概率算清楚

#include <bits/stdc++.h>
using namespace std;
double a[15],c[15],b[15],ac[15],wa[15],ans,p;
int t,x,n,i,j,tex;
int main()
{cin>>t;for(int z=0; z<t; z++){cin>>n;for(i=0; i<n; i++)cin>>a[i];for(i=0; i<n; i++)cin>>b[i];for(i=0; i<n; i++)cin>>c[i];cin>>x;ans=0;for(i=0; i<(1<<n); i++)//枚举，两个循环找完{p=1; tex=0;//得从1开始，p要是1，才能让概率出现for(j=0; j<n; j++){wa[j]=(1-a[j])*(1-b[j])*(1-c[j]);//要是想先算ac再算wa，它就是不行（精度问题？）ac[j]=1-wa[j];if(i&(1<<j)){p=p*ac[j];tex++;}elsep=p*wa[j];}if(tex==x)ans=ans+p;}printf("%.4lf\n",ans);}return 0;
}

总结
1.二进制枚举找数，还是枚举的思想。但引入了二进制，避免自己找自己
2.异或运算，解决找不同的问题很方便（用二进制找）
3.与 （别找自己），或（找其他），

杂
1.基本运算符和=组合运用
2.max（）
3. .ength（）
4. .c_str()

大概是这些了，不懂还是多百度多问，压榨大佬也是不错的选择，让他给你检查代码。