计算转化成位运算快如闪电，按位与或非异或还有左右移小数点。
——《我们仍未知道那天所见算法的名字》

前言

SDSC刚刚结束，作者便踏上了前往浙江的旅程。结果……Day1就是状压DP

so……作者便开始疯狂补习位运算

何为位运算？

位运算就是将一个十进制数转换为一个二进制数后，对其中每一位进行运算所得到的结果。

平时爱颓废对计算机原理感兴趣的同学们都知道，计算机中的内容是用二进制数表示的。

而我们平时所用的$+$，$-$，$\times$，$/$都是在十进制下进行的运算。

这样的话，在每次运算之前计算机都会把二进制转为十进制。造成时间上的浪费

而位运算则可以直接在二进制上进行操作，因此，位运算的时间效率是比较高的。(卡常神器)

位运算的基本操作

常用的位运算有$6$种，分别为与(&) ， 或(|) ，异或(^) ，取反(~) ，左移(<<) ， 右移(>>)。

下面，我们就对这几种运算进行解读。

与(&)，或(|)，异或(^)

这三种运算都是在两者间进行比较的运算。

它们的性质如下表

位运算符 英文 集合符号 性质
与 $and$ $∩$ 只有两个对应的位数均为1时才会为1
或 $or$ $∪$ 两个对应位数中只要有一位为1就会为1
异或 $xor$ 无 两个对应位数的值相同时为0，不同时为1

同时，^的逆运算是其本身，也就是说两次^同一个数的结果是不变的。比如(a ^ b) ^ b = a

举个栗砸：

eBQQhR.jpg

取反(~)

取反就是对一个数进行取反运算。即对于每一位如果该位是$1$就变成$0$，是$0$就变成$1$.

但要注意，这并不是直接对其进行取反，而是对他的补码进行取反。

蛤，您不知道补码是蛤？

那我放一个关于补码的解释：

一个正数的补码是它本身，负数的补码是其取反后 $+ 1$

就像下图：

eB18eO.jpg

左移(<<)，右移(>>)

很显然，这两种操作是将一个数二进制位进行移动。

其中，左移(num << k)是将$num$转为二进制后向左移动$k$位，右移(num >> k)是向右移动$k$位。

举个例子：

ercnVU.jpg

从上面的例子中不难看出，5 << 1相当于$5 \times 2^1$，而5 >> 1就相当于$5 / 2 ^ 1$(向下取整).

事实上，在$num$为整数的情况下，num << k等价于$num \times 2^k$ , num >> k等价于$num / 2 ^ k$。，

位运算的应用

集合

对于每一个数，它的二进制表示可以看作是一个集合（0 表示不在集合中，1 表示在集合中）。

比如集合 {1, 3, 4, 8} ，可以将其表示成 100011010 ，十进制就是 $2^8 + 2^4 + 2^3 + 2^1 = 282$。

这样的话，位运算就代表了其对应集合的操作

操作 集合符号 位运算语句
交集 $a ∩ b$ a & b
并集 $a ∪ b$ `a b`
补集 $ā$ ~a
差集 $a$ \ $b$ a & (~b)

Others

不多说，直接上代码。

乘以2

int calc(int x){
    return x << 1;
}

除以2

int calc(int x){
    return x >> 1;
}
``` 

-----------------------------

#### 乘以2的m次方

```C++
int calc(int x , int m){
    return x << m;
}

除以2的m次方

int calc(int x , int m){
    return x >> m;
}

判断一个数的奇偶性

bool pd(int x){
    return x & 1;   //奇数返回true，偶数返回false
}

对2的n次方取模

int calc(int n , int mod){
    return mod & (n - 1);
}

求两个整数的平均值

int calc(int a , int b){
    return (a + b) >> 1;
}

遍历一个集合中的子集

for(int s2 = S1; S2 > 0; S2 = (S2 - 1) & S1);

例题

下面我们就以这道题目为例来讲解位运算的实际应用

题目描述

21世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。

作为一名青春阳光好少年，$atm$一直坚持与起床困难综合症作斗争。

u=214682120,3059573823&fm=26&gp=0.jpg

通过研究相关文献，他找到了该病的发病原因：

在深邃的太平洋海底中，出现了一条名为$drd$的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。

58477ba3d972fcd1dd9bff9b56354b95.jpg

正是由于$drd$的活动，起床困难综合症愈演愈烈， 以惊人的速度在世界上传播。

为了彻底消灭这种病，$atm$决定前往海底，消灭这条恶龙。

历经千辛万苦，$atm$终于来到了$drd$所在的地方，准备与其展开艰苦卓绝的战斗。

$drd$有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。

具体说来，$drd$的防御战线由$n$扇防御门组成。每扇防御门包括一个运算$op$和一个参数$t$，其中运算一定是$OR,XOR,AND$中的一种，参数则一定为非负整数。

如果还未通过防御门时攻击力为$x$，则其通过这扇防御门后攻击力将变为$x$ $op$ $t$。最终$drd$受到的伤害为对方初始攻击力$x$依次经过所有$n$扇防御门后转变得到的攻击力。

由于$atm$水平有限，他的初始攻击力只能为$0$到$m$之间的一个整数（即他的初始攻击力只能在 $0, 1, … , m$中任选，但在通过防御门之后的攻击力不受$m$的限制）。

为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让$drd$受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使$drd$受到多少伤害。

输入格式：

输入文件的第 $1$ 行包含 $2$ 个整数，依次为$n, m$，表示 $drd$ 有$n$扇防御门，$atm$ 的初始攻击力为$0$到$m$之间的整数。

接下来$n$行，依次表示每一扇防御门。

每行包括一个字符串$op$和一个非负整数$t$，两者由一个空格隔开，且$op$在前，$t$在后，$op$表示该防御门所对应的操作，$t$表示对应的参数。

输出格式：

输出一行一个整数，表示$atm$的一次攻击最多使$drd$受到多少伤害。

Input & Output ‘s examples

Input ‘s eg

3 10
AND 5
OR 6
XOR 7

Output ‘s eg

1

数据范围和约定

1246.png

分析

不知道有没有人想到这张图（反正我是想到了）

er4zNV.jpg

咳咳，回到正题。

首先我们设两个变量，分别为一个很大的数和$0$，然后我们把那些奇怪的门先过一遍，我们就可以得到每一位的真值表

对于每一位，真值表会有以下$4$种。

0 -> 0 ， 1 -> 0
0 -> 0 ， 1 -> 1
0 -> 1 ， 1 -> 0
0 -> 1 , 1 -> 1

再根据贪心的原则，一个二进制数前边几位的$1$越多，造成的伤害也就越多。

所以我们就要让每一位尽量的变成$1$

无疑，对于可以从$0$变成$1$的情况，我们直接变$1$。而对于从$1$开始变的情况，我们要分两种情况讨论

如果是$1$变$1$，只要只要攻击力大于等于这一位需要的攻击力，就变

$1$变$0$的话就直接忽略就好啦

是不是很简单啊(逃)

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<iomanip>
#include<cstdlib>
#include<cmath>

#define ll long long
#define N 100001

using namespace std;

int n , m;
string opt;
int a[N] , b[N];
int ans , tot;

int calc(int x){
    for(int i = 1; i <= n; i ++){
        if(a[i] == 1){
            x = (x & b[i]);
        }
        else if(a[i] == 2){
            x = (x | b[i]);
        }
        else{
            x = (x ^ b[i]);
        }
    }
    return x;
}

int f[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> opt;
        if(opt == "AND"){
            a[i] = 1;
        }
        else if(opt == "OR"){
            a[i] = 2;
        }
        else{
            a[i] = 3;
        }
        cin >> b[i];
    }
    int t = calc(0);
    for(int i = 0; i <= 30; i ++){
        f[i] = (calc(1 << i) & (1 << i));
    }
    for(int i = 30; i >= 0; i --){
        if((1 << i) & t){
            ans += (1 << i);
        }
        else if((tot + (1 << i) <= m) && f[i]){
            tot += f[i];
            ans += f[i];
        } 
    }
    cout << ans << endl; 
    return 0;
}

THE END