基本运算操作

与: & 或: | 非:~ 异或:^
注意运算的优先级,建议在位运算外多套几层括号

memset

初始化为极大值 0x3f/0x7f
初始化为极小值 0x8f

左移

在二进制表示下把数字同时向左移动,低位以0填充,高位越界后舍弃.

右移

在二进制补码表示下把数字同时向右移动,高位以符号位填充,低位越界后舍弃.

二进制状态压缩

二进制状态压缩,是指将一个长度为m的bool数组用一个m位二进制整数表示并存储的方法。利用下列位运算操作可以实现原bol数组中对应下标元素的存取。

常用操作

取出整数n在二进制表示下的第k位 (n>>k)&1
取出整数n在二进制表示下的第0k-1位(后k位) n&((1<<k)-1)
把整数n在二进制表示下的第k位取反 n xor (1<<k)
对整数n在二进制表示下的第k位赋值1 n|(1<<k)
对整数n在二进制表示下的第k位赋值0 `n&((1<<k))`

这种方法运算简便,并且节省了程序运行的时间和空间。当m不太大时,可以直接使用一个整数类型存储。当m较大时,可以使用若干个整数类型(int数组),也可以直接利用C+STL为我们提供的 bitset实现.
[post cid=”37” /]

例题

[post cid=”59” /]

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

思路

很容易想到本题的一种“朴素”做法,就是枚举n个点的全排列,计算路径长度取最小值,时间复杂度为O(n_n!),使用下面的二进制状态压缩DP可以优化到O(n^2_2^n)。
在任意时刻如何表示哪些点已经被经过,哪些点没有被经过?可以使用一个n位二进制数,若其第i位(0≤i<n)为1,则表示第i个点已经被经过,反之未被经过。在任意时刻还需要知道当前所处的位置,因此我们可以使用F[i,j]表示“点被经过的状态”对应的二进制数为i,且目前处于点j时的最短路径。
在起点时,有F[1,0]=0,即只经过了点0(i只有第0位为1),目前处于起点0,最短路长度为0。方便起见,我们将F数组其他的值设为无穷大。最终目标是F[(1<<n)-1,n-1],即经过所有点(i的所有位都是1),处于终点n-1的最短路。
在任意时刻,有公式$F[i][j]=min{F[i xor (1<<j,k]+ weight(k,j)}$,其中0≤k<n并且(i>>j&1)=1,即当前时刻“被经过的点的状态”对应的二进制数为i处于点j。因为j只能被恰好经过一次,所以一定是刚刚经过的,故在上一时刻“被经过的点的状态”对应的二进制数的第j位应该赋值为0,也就是i xor (1<<j)。另外,上一时刻所处的位置可能是i xor (1<<j)中任意一个是1的数位k,从k走到j需经过 weight(k,j)的路程,可以考虑所有这样的k取最小值。这就是该公式的由来。

代码

#include <bits/stdc++.h>
using namespace std;

int m[25][25],n,f[(1<<20)+1][25]; 

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) scanf("%d",&m[i][j]);
    int ma=(1<<n)-1;
    for (int i=1;i<=ma;++i){
        for (int j=1;j<=n;++j){
            int t=1<<(j-1);
            if (!(i&t)) continue;
            if (i==t){
                f[i][j]=m[1][j];
            }else{
                f[i][j]=1e8;
                for (int k=1;k<=n;++k){
                    int tt=1<<(k-1);
                    if (tt&i && j!=k) f[i][j]=min(f[i][j],f[i-t][k]+m[j][k]);
                }
            }
        }
    }
    cout<<f[ma][n];
    return 0;
}

成对变换

n(奇数) xor 1=n-1
n(偶数) xor 1=n+1
可以通过该运算,将相邻两个自然数方便的转化

lowbit运算

lowbit=n&-n
可以快速找到n中1的个数

其他有关知识

[post cid=”11” /]

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/58/