位运算，状态压缩dp（算法竞赛进阶指南学习笔记）
目录
- 移位运算
- 一些位运算的操作
- 最短 Hamilton 路径（状态压缩dp模板，位运算）
0x是十六进制常数的开头；本身是声明进制，后面是对应具体的数；
数组初始化最大值时用0x3f赋值；
移位运算
左移
把二进制下的数左移低位以0填充
1<<n=2n n<<1=2n
算数右移
把二进制下的数右移 高位以符号位填充，低位舍弃
相当于除以二向下取整：(-3)>>1=-2，3>>1=2；
与/2不同的点在于/2时是向0取整 (-3)/2=-1；
优先级
+,- > <<,>> > <,>,==,!= > &(位与) > ^(异或) > |(位或)
不确定就加括号！
一些位运算的操作
以N=84，a=5，b=3为例；
换为二进制表示为N=0101 0100，a=0101，b=0011
~（按位非）：将二进制数的每一位都取反
~N=1010 1011 ~a=1010 ~b=1100
&（按位与）：比较两个二进制数的每一位；同时为1时记录为1
a&b=0001
((~N)+1)&N=0000 0100
|（按位或）：比较两个二进制数的每一位；只要有1就记录为1，同时为0才是0
a|b=0111
N|(~N)=1111 1111
^（异 或）：比较两个二进制数的每一位；相同记为0，不同记为1
N^(~N)=1111 1111
a^b=0110
最短 Hamilton 路径（状态压缩dp模板，位运算）
题目原文
P10447 最短 Hamilton 路径 - 洛谷
一张 n 个点的带权无向图，求起点 0 至终点 n−1 的最短 Hamilton 路径（从 0∼n−1 不重复地经过每个点一次）。
思路分析
如果暴力去遍历的话时间复杂度是O(n*n!)显然会超时；所以这里就可以利用位运算；用二进制的每一位来代表是否选取过这个点；
这样枚举的次数就降到了2n；就可以通过这道题了；
初始时建立a数组存储点i和点j之间的距离；
再利用f数组进行状态转移的模拟；最后求得的f[(1<<n)-1][n-1]即为最小距离；
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=21;
int a[N][N];
int f[1<<N][N];
signed main(){int n;cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];memset(f,0x3f,sizeof f);f[1][0]=0;for(int i=1;i<1<<n;i++){ // 枚举所有情况for(int j=0;j<n;j++){ // 遍历每个点if(i>>j&1) //可以到达for(int k=0;k<n;k++){ // 找下一步准备去的点if((i^(1<<j))>>k&1) //(i^(1<<j)是为了把j的哪一位先去掉，避免jk重复f[i][j]=min(f[i][j],f[i^(1<<j)][k]+a[j][k]);}}}cout<<f[(1<<n)-1][n-1];
}