文章目录
- 位运算
- 简介
- 与、或、异或
- 左移和右移
- 关于优先级
- 常见应用
- 内置函数
- 状压DP
- 简介
- 核心
- 练习题
位运算
简介
位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。
比赛题目中出现的位运算基本有 5 种，分别为按位与、按位或、按位异或、左移和右移。
与、或、异或
这三者都是两数间的运算。
它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。
| 运算 | 代码运算符 | 数学符号 | 解释 |
|---|---|---|---|
| 与 | & | &、and | 只有当两个对应位都为 1 时，结果才为 1；否则为 0。 |
| 或 | ` | ` | |、or |
| 异或 | ^ | ⊕ \oplus⊕, xor | 当两个对应位不同时结果为 1，相同时结果为 0 (也称为不进位加法)。 |
举例：
10 = ( 1010 ) 2 12 = ( 1100 ) 2 10 & 12 = ( 1000 ) 2 = 8 10 ∣ 12 = ( 1110 ) 2 = 14 10 ⊕ 12 = ( 0110 ) 2 = 6 \begin{aligned} 10 &= (1010)_2 \\ 12 &= (1100)_2 \\ 10 \ \& \ 12 &= (1000)_2 = 8 \\ 10 \ | \ 12 &= (1110)_2 = 14 \\ 10 \oplus 12 &= (0110)_2 = 6 \\ \end{aligned}101210&1210∣1210⊕12=(1010)2=(1100)2=(1000)2=8=(1110)2=14=(0110)2=6
对应的 C++ 代码验证：
#include<iostream>usingnamespacestd;intmain(){inta=10;// 二进制 1010intb=12;// 二进制 1100cout<<"10 & 12 = "<<(a&b)<<endl;// 输出 8cout<<"10 | 12 = "<<(a|b)<<endl;// 输出 14cout<<"10 ^ 12 = "<<(a^b)<<endl;// 输出 6return0;}左移和右移
num << i表示将 𝑛𝑢𝑚 的二进制表示向左移动 𝑖 位所得的值。
num >> i表示将 𝑛𝑢𝑚 的二进制表示向右移动 𝑖 位所得的值。
举例：
9 = ( 00001001 ) 2 9 ≪ 2 = ( 00100100 ) 2 = 36 9 ≫ 2 = ( 00000010 ) 2 = 2 \begin{aligned} 9 &= (00001001)_2 \\ 9 \ll 2 &= (00100100)_2 = 36 \\ 9 \gg 2 &= (00000010)_2 = 2 \end{aligned}99≪29≫2=(00001001)2=(00100100)2=36=(00000010)2=2
移位运算中如果出现如下情况，则其行为未定义：
- 右操作数（即移位数）为负值；
- 右操作数大于等于左操作数的位数；
例如，对于int类型的变量a，a<<-1和a<<32都是未定义的。
对于左移操作，需要确保移位后的结果能被原数的类型容纳，否则行为也是未定义的。对一个负数执行左移操作也未定义。
对于右移操作，右侧多余的位将会被舍弃，而左侧较为复杂：对于无符号数，会在左侧补 0；而对于有符号数，则会用最高位的数（其实就是符号位，非负数为 0，负数为 1）补齐。
关于优先级
位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符，所以使用时需多加注意，在必要时添加括号。
常见应用
位运算一般有三种作用：
- 高效地进行某些运算，代替其它低效的方式。
- 表示集合（常用于状压DP）。
- 题目本来就要求进行位运算。
需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但像「乘 2 的非负整数次幂」和「除以 2 的非负整数次幂」就最好使用位运算，因为此时使用位运算可以优化复杂度。）
内置函数
GCC 中还有一些用于位运算的内建函数：
int __builtin_ffs(int x)：返回 𝑥 的二进制末尾最后一个 1 的位置，位置的编号从 1 开始（最低位编号为 1 ）。当 𝑥 为 0 时返回 0 。int __builtin_clz(unsigned int x)：返回 𝑥 的二进制的前导 0 的个数。当 𝑥 为 0 时，结果未定义。int __builtin_ctz(unsigned int x)：返回 𝑥 的二进制末尾连续 0 的个数。当 𝑥 为 0 时，结果未定义。int __builtin_clrsb(int x)：当 𝑥 的符号位为 0 时返回 𝑥 的二进制的前导 0 的个数减一，否则返回 𝑥 的二进制的前导 1 的个数减一。int __builtin_popcount(unsigned int x)：返回 𝑥 的二进制中 1 的个数。int __builtin_parity(unsigned int x)：判断 𝑥 的二进制中 1 的个数的奇偶性。
由于这些函数是内建函数，经过了编译器的高度优化，运行速度十分快（有些甚至只需要一条指令）。
状压DP
简介
状压 DP 是动态规划的一种，通过将状态集合转化为整数记录在 DP 状态中来实现状态转移的目的。
为了达到更低的时间复杂度，通常需要寻找更低状态数的状态。大部分题目中会利用二元状态，用 𝑛 位二进制数表示 𝑛 个独立二元状态的情况。
核心
用一个N位的二进制数，每一位表示一个物品，0/1表示不同的状态。因此可以用0 → 2^(N − 1)(N二 进 制 对 应 的 十 进 制 数 ）中的所有数来枚举全部的状态。
练习题
[蓝桥杯 2019 省 A] 糖果
不难看出，此题不是爆搜就是动态规划，而爆搜需要考虑每一种搭配情况，复杂度O ( 2 n ) O(2^n)O(2n)肯定超时。
考虑动态规划，可以发现数据范围很小，并且是搭配类型的，想到状压。
首先设计状态，一共可以设计出两种：
- d p [ i ] dp[i]dp[i]表示取状态为i ii的几包糖，最多可以凑出的口味数量。这种状态比较麻烦，且结果不是很容易得出。
- d p [ i ] dp[i]dp[i]表示凑出状态为i ii的口味最少需要几包糖。
很显然第二种很合理，那么我们来推一下方程。
思考发现，如果直接枚举i ii，再找合理的上一种状态，不是很好找。但我们可以通过已经求出来的一种状态，配合另一种状态，来更新新的状态。
设v [ i ] v[i]v[i]表示第i ii包糖的口味状态，则有：
d p [ i ∣ v [ j ] ] = min ( d p [ i ∣ v [ j ] ] , d p [ i ] + 1 ) dp[i|v[j]] = \min(dp[i|v[j]], dp[i] + 1)dp[i∣v[j]]=min(dp[i∣v[j]],dp[i]+1)
d p [ i ∣ v [ i ] ] dp[i|v[i]]dp[i∣v[i]]为更新的新状态，i ii为已知的状态 1，再找一包糖j jj，更新出d p [ i ∣ v [ i ] ] dp[i|v[i]]dp[i∣v[i]]。
考虑正确性，因为i ii状态从 0 开始枚举，因此枚举到i ∣ v [ i ] i|v[i]i∣v[i]时肯定已经求出d p [ i ] dp[i]dp[i]的值，并且是最优的。还有一个问题是否可能重复选了某包糖，如果是，那么肯定这个值不是最优的，因为你买两包同样的糖和只买一包口味不会有新的。
#include<bits/stdc++.h>usingnamespacestd;constintN=110,M=22;intn,m,k,v[N],dp[1<<M];voidsolve(){cin>>n>>m>>k;for(inti=0;i<(1<<m);i++){dp[i]=1e9;}for(inti=1;i<=n;i++){intstate=0;for(intj=1;j<=k;j++){intx;cin>>x;x--;state|=(1<<x);}v[i]=state;dp[state]=1;}for(inti=0;i<(1<<m);i++){for(intj=1;j<=n;j++){dp[i|v[j]]=min(dp[i|v[j]],dp[i]+1);}}cout<<(dp[(1<<m)-1]==1e9?-1:dp[(1<<m)-1])<<'\n';}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intT=1;// cin>>T;while(T--)solve();return0;}
