python/TangDou/AcWing/DP/StateCompression/状态压缩DP专题.md

状态压缩动态规划（简称状压dp）是另一类非常典型的动态规划，通常使用在NP问题的小规模求解中，虽然是指数级别的复杂度，但速度比搜索快，其思想非常值得借鉴。

一、位运算相关知识

为了更好的理解状压dp，首先介绍位运算相关的知识。

• &符号，x\&y，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。例如3(11) & 2(10)=2(10)。

• |符号，x|y，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。例如3(11) | 2(10)=3(11)。

• \wedge符号，x^y，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。例如3(11) ^ 2(10)=1(01)。

• <<符号，左移操作，x<<2，将x在二进制下的每一位向左移动两位，最右边用0填充，x<<2相当于让x乘以4。相应的，’>>’是右移操作，x>>1相当于给x/2，去掉x二进制下的最有一位。

二、常见应用

这四种运算在状压dp中有着广泛的应用，常见的应用如下：

1.判断一个数字x二进制下第i位是不是等于1。

if(((1<<(i-1))&x)> 0){

}

将1左移i-1位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0，说明x第i位上是1，反之则是0。

2.将一个数字x二进制下第i位更改成1。

x = x | (1<<(i-1))

3.把一个数字二进制下最靠右的第一个1去掉。

 x=x & (x-1)

4.判断一个数字的二进制下是不是有连续的1

bool check(int x) {
    return !(x & x >> 1);
}

三、获取一个数字的二进制表示中有多少个数字1

1、枚举32位判断

传统的整数按位向右移动，效率稍差，贵在好理解

int f1(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++)
        if ((n >> i) & 1) res++;
    return res;
}

2、用位运算x \& (x-1)，每次干掉最后一个1

使用 x \& (x-1) 假如输入 n = 13 ，13 的二进制 1101 1101 —— n 1100 —— n-1

1100 —— n \& n-1 再赋给 n 1011 —— n-1

1000 —— n \& n-1 再赋给 n 0111 —— n-1 0000 —— n \& n-1 再赋给 n

每次去掉一个 1，执行几次就有几个 1 ，每次把二进制数的最右边的1去掉，直到为零停止

int f2(int x) {
    int res = 0;
    while (x) {
        x = x & (x - 1);
        res++;
    }
    return res;
}

3、位运算lowbit，每次减掉获得的值

lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1，举个例子，x = 6，它的二进制为110，那么lowbit(x)就返回2，因为最后一位1表示2。

#define lowbit(x) (x & -x)

int f3(int x) {
    int res = 0;
    while (x) {
        x -= lowbit(x);
        res++;
    }
    return res;
}

4、完整测试代码

#include <bits/stdc++.h>

using namespace std;

#define lowbit(x) (x & -x)

// 1、传统的整数按位向右移动，效率稍差，贵在好理解
int f1(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++)
        if ((n >> i) & 1) res++;
    return res;
}

// 2、使用 x & (x-1)
int f2(int x) {
    int res = 0;
    while (x) {
        x = x & (x - 1);
        res++;
    }
    return res;
}

// 3、lowbit函数法
int f3(int x) {
    int res = 0;
    while (x) {
        x -= lowbit(x);
        res++;
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", f1(n));
    printf("%d\n", f2(n));
    printf("%d\n", f3(n));
    return 0;
}