C++学习之与&或&非&异或&二进制枚举_c++ 与或非

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

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

1.与或非

                                      **|以下内容均在二进制下操作|**
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;//假设第一个数是 3
        n=n-1;//第二个数开始
        while(n--)//（这里是个数递减）
        {
            scanf("%d",&x);//读下一个数 2
            ans=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
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

异或 能把不同的那个找出来
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;
 /*
 3
 A
 B
 C
 B
 C
 */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

————异或完了，就这么用。找不同。
需要另外学习的有 .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;
    /*
    input
    5 13
    2 4 6 8 10
    output
    NO
    */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

二进制枚举例题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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

二进制枚举例题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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

二进制枚举例题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循环归0
            for(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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

二进制枚举例题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++;
                }
                else
                    p=p*wa[j];
            }
            if(tex==x)ans=ans+p;
        }
        printf("%.4lf\n",ans);

    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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

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

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