Java教程

《算法进阶指南》- 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位运算的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!