《算法进阶指南》- 0.1位运算

本文主要是介绍《算法进阶指南》- 0.1位运算，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

总结：第一次看的时候感觉位运算很难，最近在学状态压缩dp的时候运用到移位，用二进制表示状态，回头看了一下，感觉并没有想象中的难。

1.四种位运算

• 与：x & y
• 或：x | y
• 非：!x
• 异或：x^y，又称不进位加法

2.补码

int 32位
1：00000000....01
2：00000000....10
3：00000000....11

补码引入：
x + 1 = 00000000....0000
1 + 1111111111111111 = 00000000..0000
由此 -1 = 1111111111111111

2 + 1111111111111110 = 00000000..0000
由此 -2 = 1111111111111110

x + ? = 0 
? = -x = ~x + 1(推导出)

由上式推导出：-n = ~n + 1

3.左移右移

左移 x 位：相当于乘\(2^x\)，低位补0

右移

• 逻辑右移就是不考虑符号位，右移一位，左边补零即可，相当于除以\(2^x\)
• 算术右移需要考虑符号位，右移一位，若符号位为1，就在左边补1,否则，就补0。

4.lowbit运算(二进制下求最后一个1)

lowbit(1110010000) = 10000

推导过程：
 n = 1110010000

-n = 0001101111 + 1
   = 0001110000

此时 -n & n = 10000
 
即：int lowbit(int n)
{
    return (-n) & n;
}

相关例题：

>a^b(快速幂)

\(a^b = a^1*a^2*a^4*a^8*....a^x,其中1 + 2 + 4 + 8 + ... + x = b\)

#include<iostream>
using namespace std;

typedef long long LL;

int main()
{
    int a,b,p;
    cin>>a>>b>>p;
    LL res = 1 % p;// 可能有 123456789 0  1 的样例
    
    while(b)
    {
        if(b & 1) res = (long long) res * a % p;//看每一位,转成long long是避免在过程中爆int
        a = (long long) a * a % p;
        b >>= 1;
    }
    cout<<res<<endl;
    return 0;
}

>64位整数乘法

\(a * b = (1 + 2 + 4 + 8 + ... + x) * b,其中 1 + 2 + 4 + 8 + ... + x = a\)

#include<iostream>
using namespace std;

typedef long long LL;
LL res;
int main()
{
    LL a,b,p;
    cin>>a>>b>>p;
    while(a)
    {
        if(a&1) res = (res + b) % p;
        b = (b + b) % p;
        a >>= 1;
    }
    cout<<res<<endl;
    return 0;
}

细节：0x3f3f3f3f有什么性质？ 1.很大 2. 2 x 0x3f3f3f3f 小于 0x4f4f4f4f

>最短Hamilton路径

抽风大佬讲解,这题是压缩DP，可以用二进制数把每个状态表示出来，此题解法极秒。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 20,M = 1 << 20;

int n;
int f[M][N],weight[N][N];//第一维是路径，第二维是当前到达了第几个点

int main()
{
    cin>>n;
    for(int i = 0;i < n;i++)
     for(int j = 0;j < n;j++)
      cin>>weight[i][j];
      
    memset(f,0x3f,sizeof f);//每个字节赋值成0x3f
    f[1][0] = 0;
    
    for(int i = 0;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){//点集存在k
                  f[i][j] = min(f[i][j],f[i - (1<<j)][k]+weight[k][j]);
              }
         }
     }
     cout << f[(1 << n) - 1][n - 1] << endl;
     return 0;
}

细节：memset是给每个字节赋值，0x3f3f3f3f性质：很大，但是比0x4f4f4f4f小

这篇关于《算法进阶指南》- 0.1位运算的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！