146 lines
4.0 KiB
Markdown
146 lines
4.0 KiB
Markdown
状态压缩动态规划（简称状压$dp$）是另一类非常典型的动态规划，通常使用在$NP$问题的小规模求解中，虽然是指数级别的复杂度，但速度比搜索快，其思想非常值得借鉴。
|
||
|
||
### 一、位运算相关知识
|
||
|
||
为了更好的理解状压$dp$，首先介绍位运算相关的知识。
|
||
|
||
* <font color='red'>**&**</font>符号，$x\&y$，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。例如$3(11)$ & $2(10)=2(10)$。
|
||
|
||
* <font color='red'>**|**</font>符号，$x$|$y$，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。例如$3(11)$ | $2(10)=3(11)$。
|
||
|
||
* <font color='red'>**$\wedge$**</font>符号，$x$^$y$，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。例如$3(11)$ ^ $2(10)=1(01)$。
|
||
|
||
* <font color='red'>**<<**</font>符号，左移操作，$x<<2$，将$x$在二进制下的每一位向左移动两位，最右边用$0$填充，$x<<2$相当于让$x$乘以$4$。相应的，’$>>$’是右移操作，$x>>1$相当于给$x/2$，去掉$x$二进制下的最有一位。
|
||
|
||
### 二、常见应用
|
||
这四种运算在状压$dp$中有着广泛的应用，常见的应用如下：
|
||
|
||
**1.判断一个数字`x`二进制下第`i`位是不是等于`1`。**
|
||
```c++
|
||
if(((1<<(i-1))&x)> 0){
|
||
|
||
}
|
||
```
|
||
将$1$左移$i-1$位，相当于制造了一个只有第$i$位上是$1$，其他位上都是$0$的二进制数。然后与$x$做与运算，如果结果>$0$，说明$x$第$i$位上是$1$，反之则是$0$。
|
||
|
||
**2.将一个数字`x`二进制下第`i`位更改成`1`。**
|
||
|
||
```c++
|
||
x = x | (1<<(i-1))
|
||
```
|
||
|
||
**3.把一个数字二进制下最靠右的第一个`1`去掉。**
|
||
|
||
```c++
|
||
x=x & (x-1)
|
||
```
|
||
|
||
**4.判断一个数字的二进制下是不是有连续的1**
|
||
```c++
|
||
bool check(int x) {
|
||
return !(x & x >> 1);
|
||
}
|
||
```
|
||
|
||
### 三、获取一个数字的二进制表示中有多少个数字$1$
|
||
|
||
|
||
#### 1、枚举$32$位判断
|
||
传统的整数按位向右移动，效率稍差，贵在好理解
|
||
```c++
|
||
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$去掉，直到为零停止
|
||
|
||
```c++
|
||
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$。
|
||
|
||
```c++
|
||
#define lowbit(x) (x & -x)
|
||
|
||
int f3(int x) {
|
||
int res = 0;
|
||
while (x) {
|
||
x -= lowbit(x);
|
||
res++;
|
||
}
|
||
return res;
|
||
}
|
||
```
|
||
|
||
#### 4、完整测试代码
|
||
```c++
|
||
#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;
|
||
}
|
||
``` |