位运算知识点

289 0 0

作者:qlhoier

知识点：

位运算

与运算：

两者都为真时返回true，否则返回false

C++中用 & 表示与运算

或运算：

两者有一者为真就返回true,都为假时返回false

C++中用 | 表示或运算

非运算：

如果是真就返回false,如果是假就返回true

C++中用 ~ 表示非运算，也叫取反

异或运算：

当两者都为真或都为假时返回false,当一者为真一者为假时返回true

C++中用 ^ 表示异或运算

编码和补码

编码方式

无符号整数unsigned int

可以直接把它的编码看成是它的二进制表现形式

有符号整数int

32位编码的最高位为0表示非负整数，32为编码最高位为1表示负整数

对于非负整数，我们可以直接把它的编码看成它的二进制表现形式

000000000……1表示1

000000000…10表示2

对于负整数，我们我们是倒过来看的：

1111111……11(32个1)表示-1

11111……10表示-2

以此类推

对此，我们可以发现：

负整数的编码实际实际上是它的相反数-1的编码按位取反

补码方式

一个数x和它的补码y之和为00000000000

例如：

1的编码是000000……1

那么它的补码就是1111111111111111……1

相当于1的编码按位取反再+1

用int的编码方式这个数就是-1

2的编码是00000000……10

它的补码就是1111111……10

用int的编码方式这个数就是-2

相当于2的编码按位取反再+1

以此类推，我们发现：

一个数x的补码就是~x+1

即：

-x=~x+1

小技巧：

初始化变量或数组为正无穷时，常用0x3f3f3f3f

因为它的两倍不超过int能表示的最大正整数，即0xffffffff

并且每个字节的值是相同的

因此我们初始化的时候为了避免类似a+b操作造成算术上溢，一般初始化正无穷为0x3f3f3f3f

移位运算

左移n位，相当于乘以2^n

右移n位，相当于除以2^n

都是向下取整

注意，这都是算术右移，不是逻辑右移

因此，正整数最高位补0，负整数最高位补1

右移是除以2向下取整，/2是除以二向零取整

二进制状态压缩

类似表示一个数组中某个数是否被用过的状态表示，我们可以用到一个长度相等的bool数组，通过某一位的true和false来进行状态表示

当然，如果用一个二进制数也可以表示，通过第n个二进制位上的数字是0还是1来表示状态，并且不同的二进制数表示的数也不同，在我们看来就是不同的十进制数

习题：

位运算习题：

习题1：a^b

求a的b次方模p的结果，a<=a,b,p<=10^9

对于一个数，我们可以通过几个2的n次方的数的和表示

具体做法是转化成二进制数并从小到大遍历每一位，定义一个数x每次给自己乘2，如果发现当前的二进制为是1，结果就加上x，否则不加

这道题可以用快速幂做法，把指数转化成二进制从小到大枚举每一位，每次把底数平方并赋值成平方之后的值，如果二进制位是1结果就加上当前底数的值，否则不加

题目代码如下：

#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,p;
int main()
{
    scanf("%lld%lld%lld",&a,&b,&p);
    if(!b)
    {
        printf("%lld",1%p);
        return 0;
    }
    ll res=1;
    while(b)
    {
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    printf("%lld",res);
    return 0;
}

这里注意任何数的0次方=1，而我们的计算是从1次方开始的，注意边界条件

y总的小trick:乘法中乘以1ll相当于乘以了一个long long类型的1，结果就会变成long long，防止溢出

习题2:64位整数乘法

求a乘b对p取模的值，其中1<=a,b,p<=10^18

这道题我们也可以用到上一道题的思想，不过这次是b个a相加

我们可以预处理出来a,2a,4a,8a,……,2^n*a，根据实际情况判断是否要加上

从低到高枚举b的二进制为，如果是0就不加，如果是1的话就加

代码如下：

#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,p;
int main()
{
    scanf("%lld%lld%lld",&a,&b,&p);
    ll res=0;
    while(b)
    {
        if(b&1)res+=a%p;
        res%=p;//这里注意每次都要模p，因为可能本身res和a%p都小于P，但加起来就不小于了，多次累加就会溢出
        a=a*2%p;
        b>>=1;
    }
    printf("%lld",res);
    return 0;
}

二进制状态压缩习题:

最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

#include<iostream>
#include<cstring>
using namespace std;
const int N=20,M=1<<20;
int weight[N][N];//存某两个点之间的消耗
int f[M][N];//M为二进制压缩后的状态,N为当前停留在哪个点
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)//因为二进制状态压缩下标是从0开始记录的，为了方便调用这里也从下表为0开始记录
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&weight[i][j]);
        }
    }
    memset(f,0x3f,sizeof f);//因为取较小值，要初始化成正无穷
    f[1][0]=0;//在最开始的点没动，起点已经被走过所以状态为1，因为没有走所以消耗为0
    for(int i=1;i<1<<n;i++)//枚举从只走了第一个点到走了所有点的状态
    {
        for(int j=0;j<n;j++)//枚举上一次走的是哪个点
        {
            if(i>>j&1)//如果当前枚举的状态中j已经被走过才可以继续枚举，否则不合法
            {
                for(int k=0;k<n;k++)//枚举上一次走过的是哪个点
                {
                    if(i-(1<<j) >> k&1)f[i][j]=min(f[i][j],f[i-(1<<j)][k]+weight[k][j]);
                    //如果当前枚举的状态中第k个点已经被走过了才算合法，先去掉i再判断是防止k和j重合的情况
                    //当前状态的最小消耗是这一状态枚举过的情况中的最小值和当前状态下的消耗取较小值
                    //当前状态的消耗为走到第k个点的最小消耗加上从第k个点走到第j个点的消耗，并且第k个点的状态为没走过j
                    //如果已经走过j，那么如果再走到j就进行了没必要的消耗
                }
            }
        }
    }
    printf("%d",f[(1<<n)-1][n-1]);//表示每个点都走过的状态是所有点都是1，相当于更高一位的1000……的数减一
                                  //因为有n个点，编号从0开始，所以更高一位就是n位
                                  //最后一个点就是终点
    return 0;
}

起床困难综合症

这就不说原题目描述了，又长又不好懂
题意：给定 n,mn,m 以及 nn 个数和该数所对应的运算，其中运算有与、或、异或三种，问在所有不大于 mm 的非负整数中，对给定的 nn 个数都按该数所对应的运算运算一遍后，能得到得最大的值是多少。

AND 表示按位与，OR 表示按位或，XOR 表示按位异或

解题思路：

位运算有一个特点，即除了位移运算其他运算每一位之间没有关系，不存在进位
因此，我们可以从每一位分析在确保val不大于m的情况下val的每一位应当选择0还是1
根据数据范围，我们可以求出val的二进制位数一定不大于29
因为要考虑到选的数小于等于m，我们应该从高位到低位进行枚举
对于每一位，我们对0和1进行尝试，从相应的n个运算的t中选出对应的位并进行运算算出最终结果
存在4种情况：
0,0 1,0 0,1 1,1
如果选择0能输出1：
如果选择1也能输出1，我们选择一会导致val偏大，导致后面可以选择1的情况减少，所以我们要选择0
如果选择1输出0，那一定选0
如果选择0输出了0：
如果选择1输出了1，如果不选1即使后面全选择1总伤害也不可能大于这一位选择1，因此一定选1
如果选择1输出了0，那选择一会对val造成不必要的消耗，可能导致后面必须选1才能输出1的情况无法执行，所以也选择0
至此，我们发现了只有0,1的情况下才会选择1，其他情况均选择0
因此，如果选择1那就把答案和val同时加上1左移当前位，如果选择0，那就把答案加上选择0输出的数所以当前位
最后输出答案即可

代码如下：

/*
位运算有一个特点，即除了位移运算其他运算每一位之间没有关系，不存在进位
因此，我们可以从每一位分析在确保val不大于m的情况下val的每一位应当选择0还是1
根据数据范围，我们可以求出val的二进制位数一定不大于29
因为要考虑到选的数小于等于m，我们应该从高位到低位进行枚举
对于每一位，我们对0和1进行尝试，从相应的n个运算的t中选出对应的位并进行运算算出最终结果
存在4种情况：
0,0      1,0       0,1       1,1
如果选择0能输出1：
    如果选择1也能输出1，我们选择一会导致val偏大，导致后面可以选择1的情况减少，所以我们要选择0
    如果选择1输出0，那一定选0
如果选择0输出了0：
    如果选择1输出了1，如果不选1即使后面全选择1总伤害也不可能大于这一位选择1，因此一定选1
    如果选择1输出了0，那选择一会对val造成不必要的消耗，可能导致后面必须选1才能输出1的情况无法执行，所以也选择0
至此，我们发现了只有0,1的情况下才会选择1，其他情况均选择0
因此，如果选择1那就把答案和val同时加上1左移当前位，如果选择0，那就把答案加上选择0输出的数所以当前位
最后输出答案即可
*/
#include<iostream>
using namespace std;
int n,m;
const int N=100010;
int d[N][2];
int calc(int val,int bit)//val表示第bit位选择0还是1，bit表示第几位
{
    for(int i=1;i<=n;i++)
    {
        int x=(d[i][0]>>bit)&1;//取出第i个位运算第bit位
        //进行相应的运算
        if(d[i][1]==1)val&=x;
        else if(d[i][1]==2)val|=x;
        else if(d[i][1]==3)val^=x;
    }
    return val;//返回第bit位运算的结果
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)//读入要进行的运算
    {
        string op;
        cin>>op;
        if(op=="AND")d[i][1]=1;
        else if(op=="OR")d[i][1]=2;
        else if(op=="XOR")d[i][1]=3;
        scanf("%d",&d[i][0]);
    }
    int val=0,ans=0;//val表示选择的初始攻击，ans表示最终的攻击
    for(int bit=29;bit>=0;bit--)//从高往低枚举，防止超出m
    {
        int res0=calc(0,bit);//求出第bit位选择0输出的值
        int res1=calc(1,bit);//求出第bit位选择1输出的值
        if(res0<res1&&val+(1<<bit)<=m)val+=1<<bit,ans+=1<<bit;
        //如果res0=0,res1=1,并且初始值加上1左移bit位不大于m就选1,初始值和最终答案第bit位同时改成1
        else ans+=res0<<bit;//否则选0,根据输出的值左移bit位的结果给答案该值
    }
    printf("%d",ans);
    return 0;
}

这里给出一个更优的思路：

除位移运算之外位运算每一位之间互不关联

因此，我们在读入每个运算的时候预处理出来每一位是0和是1的输出情况

根据补码知识可知：

0的二进制表示为000000……0

-1的二进制表示为11111111……1

因此，我们设置两个初始值分别为0和-1

每读入一个运算就把这两个数进行运算

后面判断每一位是选择0和选择1输出的结果的时候只需要调用对应的数的相应位即可

这个做法比上一个做法少了一个log，又是一个不小的优化

贴上代码：

#include<iostream>
using namespace std;
int n,m,res0=0,res1=-1;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char op[5];
        int t;
        cin>>op;
        scanf("%d",&t);
        if(op[0]=='A')res0&=t,res1&=t;
        else if(op[0]=='O')res0|=t,res1|=t;
        else if(op[0]=='X')res0^=t,res1^=t;
    }
    // int p=0;
    // for(int i=0;(1<<i)<=m;i++)p++;
    //这里想一步到位找到m的二进制位数，其实不行，因为最终攻击不受m限制
    // p++;
    int val=0,ans=0;//val表示选择的初始攻击，ans表示最终的攻击
    for(int bit=29;bit>=0;bit--)//从高往低枚举，防止超出m
    {
        if(!((res0>>bit)&1)&&((res1>>bit)&1)&&(val+(1<<bit)<=m))val+=1<<bit,ans+=1<<bit;
        //如果res0=0,res1=1,并且初始值加上1左移bit位不大于m就选1,初始值和最终答案第bit位同时改成1
        else if((res0>>bit)&1)ans+=1<<bit;
    }
    printf("%d",ans);
    return 0;
}

两个技巧

成对变换

当n为偶数时，二进制表示最后一位是0，异或1之后变成1，其他位不变，变成了n+1

当n为奇数时，二进制表示最后一位是1，异或1之后变成0，其他位不变，变成了n-1

对此，我们发现0和1,2和3,4和5……，其中的任意一个数异或1都会变成所对的另外一个数，这便是成对变换

这一性质经常用于图论邻接表中边集的储存

在具有无向边的图中八一队正反方向的边分别储存在邻接表数组的第n与n+1位置，n为偶数，就可以通过xor1的运算获得与当前边(x,y)反向的边(y,x)的储存位置。

lowbit运算

lowbit运算定义为非负整数n在二进制表示下“最低位的1及其后面所有的0”构成的数值

我们知道一个数x末尾的连续的0取反~x之后就变成了1，最后一个1变成了0，~x如果加上1那末尾连续的1都变成了0，那个变成0的1变回了1，这个一之前的所有位x和~x+1都是相反的，这个1之后的所有位x和~x+1都是0，因此进行&运算即可求出这个1左移它在这个数中的位之后的值

而我们知道-x=~x+1，因此lowbit运算就是x&(-x)

如果每一次都把对应位的1减去，再重复操作，就可以求出每一个1，计算的次数与1的个数相同

lowbit运算是树状数组的一个基本运算，用于求出第x位的前缀和应当把树状数组中的哪些值相加

总结完毕，感谢阅读，如有错误或建议请指出，感激不尽

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/qlhoier/p/17240995.html

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

位运算知识点

位运算知识点

知识点：

位运算

与运算：

或运算：

非运算：

异或运算：

编码和补码

编码方式

无符号整数unsigned int

有符号整数int

补码方式

小技巧：

移位运算

二进制状态压缩

习题：

位运算习题：

习题1：a^b

求a的b次方模p的结果，a<=a,b,p<=10^9

习题2:64位整数乘法

求a乘b对p取模的值，其中1<=a,b,p<=10^18

二进制状态压缩习题:

最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

起床困难综合症

AND 表示按位与，OR 表示按位或，XOR 表示按位异或

两个技巧

成对变换

lowbit运算

lowbit运算定义为非负整数n在二进制表示下“最低位的1及其后面所有的0”构成的数值

相关课程

热门标签

位运算知识点

位运算知识点

知识点：

位运算

与运算：

或运算：

非运算：

异或运算：

编码和补码

编码方式

无符号整数unsigned int

有符号整数int

补码方式

小技巧：

移位运算

二进制状态压缩

习题：

位运算习题：

习题1：a^b

求a的b次方模p的结果，a<=a,b,p<=10^9

习题2:64位整数乘法

求a乘b对p取模的值，其中1<=a,b,p<=10^18

二进制状态压缩习题:

最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

起床困难综合症

AND 表示按位与，OR 表示按位或，XOR 表示按位异或

两个技巧

成对变换

lowbit运算

lowbit运算定义为非负整数n在二进制表示下“最低位的1及其后面所有的0”构成的数值

相关课程

热门标签

推荐文章