位运算

c++之位运算（详解，初学者绝对能看懂）c++位运算？！？？的博客-CSDN博客

位运算符号

按位与如果两个相应的二进制位都为1，则该位的结果值为1，否则为0

|按位或两个相应的二进制位中只要有一个为1，该位的结果值为1

按位异或若参加运算的两个二进制位值相同则为0，否则为1

取反~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1

 5e3d18cbe0b741f69c2bc34173ef4b1a

位移运算

 2f4e628fb5c64473911da2c21c89e982

常用技巧

在m位二进制数中，通常称最低为为第0位，从右到左依次类推，最高位为第m-1位

(n >> k) & 1 求n二进制下的第k位是0还是1，若结果为真，是1，若结果为假，是0。！！！！！因为1的二进制数中只有第0位数是1，其余位数0。！！！！

n^=1,，即n=n^1,能让n变成与原来相反的数（0或1）

n | (1 << k)，能把n的第k位变成1

a^b^b=a

x=x&(x-1)用于消去x的最后一位

运算符优先级

 6b24db5fe89b43529213686003146043

经典例题

最短Hamilton路径

给定一张 nn 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 n。

接下来 n行每行 n个整数，其中第 i 行第 j个整数表示点 i 到 j 的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x]并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

1≤n≤200≤a[i,j]≤10^7

输入样例

输出样例

思路：在任意时刻如何表示哪些点已经被经过，哪些点没有哦被经过？可以使用一个n位二进制数，若其第i位（0<=i<n）为1，则表示第i个点已经被经过，反之未被经过。在任意时刻还需要知道当前所处的位置，因此我们可以使用f[i[j表示“点被经过的状态”对应的二进制数为i，且目前处于点j时的最短路径。总的时间复杂度是 O(n^2*2n)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20,M=1<<N;//2的20次方，数据最坏n是20，
//一个点都有用和不用（1和0）两种情况，n=20时就是2^20
int f[M][N],w[N][N];//w表示的是无权图
//状态：1.哪些点被用过  2.目前停在哪些点上   所以用二维
//e***0 1 4   M=10011（第0个点存在，第1个点存在，第2，3个点不存在，第4个点存在）
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        cin>>w[i][j];
    memset(f,0x3f,sizeof(f));//因为要求最小值，所以初始化为无穷大
    f[1][0]=0;//因为零是起点,所以f[1][0]=0;

    for(int i=0;i<1<<n;i++)//i表示所有的情况,i表示的集合，哪些点是否被用
     for(int j=0;j<n;j++)//j表示走到哪一个点
      if(i>>j&1)//i的第j位（二进制）是1
       for(int k=0;k<n;k++)//k表示走到j这个点之前,以k为终点的最短距离
        if(i>>k&1)//第k位有点存在
          //f[state][j]=f[state_k][k]+w[k][j]; 
          //state_k表示state除去j后的集合,k表示停在第k个点上，state_k要包含k
         f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
         //更新最短距离，枚举state_k这个集合里面的所有点

    cout<<f[(1<<n)-1][n-1]<<endl;//表示所有点都走过了,且终点是n-1的最短距离
    //位运算的优先级低于'+'-'所以有必要的情况下要打括号
    return 0;
}