位运算 二进制枚举 掩位码
0xFF 二进制
众所周知在计算机中信息都是用二进制储存的 那你知道在计算机内部怎样储存的吗
原码
原码就是在这个数绝对值的二进制前面加上一个符号位(符号位为 \(0\) 则为正数 符号位为 \(1\)则为负数 反之亦然)
举几个栗子
比如 \(42\) 它的二进制就是 \((101010)_2\) 所以原码是 \((00101010)_2\)
再比如 \(-42\) 的原码是 \((10101010)_2\)
我们来验证一下
这不对啊
反码
聪明的你想到了一个方法那就是把负数除了符号位都反过来
比如 \(-42\) 的原码是 \((10101010)_2\) 所以反码是 \((11010101)_2\)
再来计算一下
是 \(-0\) ？
补码
你又想到了 我们可以在反码的基础上\(+1\)
比如 \(-42\) 的原码是 \((10101010)_2\) 反码是 \((11010101)_2\) 所以补码是 \((11010110)_2\)
再来计算一下
没错 就是 \(0\)
这就是在计算机内部储存整数的方法补码
0x01 位运算
正片开始
在计算机中有些运算速度极快 它们就是位运算
位运算有六种分别是
-按位与: $\mathrm{AND} $ &
-按位或: $\mathrm{OR} $ |
-取反: $\mathrm{NOT} $ ~
-异或: $\oplus $ ^
-左移: \(<<\) <<
-右移: \(>>\) >>
具体做什么就不说了应该都知道 重要的是那一些性质
位运算的性质
我们可以发现计算位运算时每一位是互相无关的 我们可以用这一个特点来做题
例题
可以发现当最高位为 \(0\) 时这个算式为 \(0\)
code:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll x;
int t;
int main(){cin>>t;while(t--){cin>>x;for(int i=30;i>=0;i--){ll A=(1<<i);if(x&A){cout<<A-1<<"\n";break;}}}return 0;
}
$\mathrm{AND} $ 和 $\mathrm{OR} $
根据定义可以知道
可以用上这个性质将 $\mathrm{OR} $ 和 $\mathrm{AND} $ 互相转换
$\mathrm{NOT} \ a $ 和 \(-a\)
根据补码的定义 \(\mathrm{NOT} \ a = -(a+1)\) 和 $ -a = \mathrm{NOT} \ a +1 $
这个和树状数组的 \(\mathrm{lowbit}\) 有密切的关系
\(\mathrm{lowbit}\)
\(\mathrm{lowbit}\) 就是二进制位上最低位的 \(1\) 所代表的数 如 \(\mathrm{lowbit} \ (42) = \mathrm{lowbit} \ ((00101010)_2) = 2\)
通过瞪眼法观察可以发现 \(\mathrm{lowbit} \ (x) = x\ \mathrm{AND} \ (-x)\) 证明不难
$\oplus $
$\oplus $ 就十分有趣了有许多题都爱用它的性质
- \(a\oplus a=0\)
- \(0\oplus a=a\)
- \(a\oplus b\ \oplus b=a\)
- \(a \oplus b \le a+b\)
例题
根据 $\oplus $ 的性质可以想到 把所有数异或起来 出现两次的会归零
code:
#include<bits/stdc++.h>
using namespace std;
long long n,x,ans;
int main(){cin>>n;while(n--)cin>>x,ans^=x;cout<<ans;
}
记得卡一下常 把输入输出换成 printf和scanf 或者 手写快读快写
判断第 \(x\) 位是否为 \(1\)
可用 \(a\ \mathrm{AND} (1\ << \ x)\)
0x02 二进制枚举
我们可以用一个 bool 数组来表示选与不选 那我们也可以用二进制来表示 这就是 二进制枚举多说无益看题
例题
我们可以枚举每一科的每一道题用左脑还是右脑来做
code:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int s1,s2,s3,s4,ans;
int A[30],B[30],C[30],D[30];
int main(){cin>>s1>>s2>>s3>>s4;for(int i=1;i<=s1;i++)cin>>A[i];for(int i=1;i<=s2;i++)cin>>B[i];for(int i=1;i<=s3;i++)cin>>C[i];for(int i=1;i<=s4;i++)cin>>D[i];int MiN=INT_MAX;for(int i=0;i<(1<<s1);i++){int x=0,y=0;for(int j=0;j<=s1;j++){if(i&(1<<j)){x+=A[j+1];}else{y+=A[j+1];}}MiN=min(MiN,max(x,y));}ans+=MiN;MiN=INT_MAX;for(int i=0;i<(1<<s2);i++){int x=0,y=0;for(int j=0;j<=s2;j++){if(i&(1<<j)){x+=B[j+1];}else{y+=B[j+1];}}MiN=min(MiN,max(x,y));}ans+=MiN;MiN=INT_MAX;for(int i=0;i<(1<<s3);i++){int x=0,y=0;for(int j=0;j<=s3;j++){if(i&(1<<j)){x+=C[j+1];}else{y+=C[j+1];}}MiN=min(MiN,max(x,y));}ans+=MiN;MiN=INT_MAX;for(int i=0;i<(1<<s4);i++){int x=0,y=0;for(int j=0;j<=s4;j++){if(i&(1<<j)){x+=D[j+1];}else{y+=D[j+1];}}MiN=min(MiN,max(x,y));}ans+=MiN;cout<<ans;return 0;
}
其实可以封装成函数但我懒 AwA
0x03 掩位码
那我们会想我们可不可以用二进制来表示集合呢 当然可以
下面是集合运算和位运算的对照表
| 名称 | 集合符号 | 位运算 |
|---|---|---|
| 并集 | $ A\cup B $ | $ A \ \mathrm{OR} \ B $ |
| 交集 | $ A\cap B $ | \(A \ \mathrm{AND} \ B\) |
| 补集 | \(\complement _U A\) | \(\mathrm{NOT} \ A\) |
| 差集 | \(A - B\) | \(A \ \mathrm{AND} \ (\mathrm{NOT} B)\) |
| 对称差 | \(A \bigtriangleup B\) | \(A \oplus B\) |
| 同时还有许多操作 我们直接看code |
code:
//LG
//集合运算 2
//https://www.luogu.com.cn/problem/B3633
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll A,B;
int n,m;
void in(ll &Set,int x){Set|=(1ll<<x);}
void del(ll &Set,int x){Set&=~(1ll<<x);}
ll And(ll A,ll B){return A&B;}
ll Or(ll A,ll B){return A|B;}
ll Not(ll A){return ~A;}
ll Sub(ll A,ll B){return A&(~B);}
ll Diff(ll A,ll B){return A^B;}
bool In1(int x,ll A){return A&(1ll<<x);}
bool In2(ll A,ll B){return (A&B)==A;}
int Size(ll A){int tot=0;while(A){tot++;A-=A&(-A);}return tot;
}
void Out(ll A){for(ll i=0;i<=63;i++){if(A&(1ll<<i))cout<<i<<" ";}}
int main(){cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;in(A,x);}cin>>m;for(int i=1;i<=m;i++){int x;cin>>x;in(B,x);}cout<<Size(A)<<"\n";Out(And(A,B)),cout<<"\n";Out(Or(A,B)),cout<<"\n";Out(Not(A)),cout<<"\n";cout<<(A==B)<<"\n"<<In2(A,B)<<"\n"<<In1(0,A);return 0;
}
为绝对不会告诉你有个东西叫 bitset
0x04 奇技淫巧
我们就直接看 code
判断奇数
if(x&1){//...
}
交换两数
void swap(int &a,int &b){a^=b,b^=a,a^=b;}
判断符号
bool Sign(int a){return (a>>31);} //0为非负数
绝对值
bool Abs(int a){return (n^(n >> 31)) - (n >> 31);}