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

前言

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

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

何为位运算？

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

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

而我们平时所用的，，，都是在十进制下进行的运算。

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

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

位运算的基本操作

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

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

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

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

它们的性质如下表

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

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

举个栗砸：

eBQQhR.jpg

取反(~)

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

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

蛤，您不知道补码是蛤？

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

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

就像下图：

eB18eO.jpg

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

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

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

举个例子：

ercnVU.jpg

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

事实上，在为整数的情况下，num << k等价于 , num >> k等价于。，

位运算的应用

集合

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

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

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

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

Others

不多说，直接上代码。

乘以2

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

除以2

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

乘以2的m次方

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世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。

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

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

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

58477ba3d972fcd1dd9bff9b56354b95.jpg

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

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

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

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

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

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

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

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

输入格式：

输入文件的第 行包含 个整数，依次为，表示 有扇防御门， 的初始攻击力为到之间的整数。

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

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

输出格式：

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

Input & Output 's examples

Input 's eg

3 10
AND 5
OR 6
XOR 7

Output 's eg

1

数据范围和约定

1246.png

分析

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

er4zNV.jpg

咳咳，回到正题。

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

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

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

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

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

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

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

变的话就直接忽略就好啦

是不是很简单啊(逃)

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