目录
- 位运算前言
- 位运算应用
- 1 快速幂
- 2 最大公约数
- 3
xor一些应用 - 4 其他
位运算前言
程序中所有东西在计算机中都是以二进制储存的。
位运算可以直接操作这些二进制。
所以位运算相对于普通运算要快。
这些是所有位运算及其优先级：
注意区分逻辑运算和按位运算的区别，逻辑运算视所有 ( eq 0) 的数为 ( exttt{True})（(1)）。
对于全体运算来说：
| 运算 |
|---|
逻辑非（not，!）；按位取反（~ ) |
乘法（*）；除法（/）；取模（mod，%） |
加法（+）；减法（-） |
左移（<<）；右移（>>） |
大于（>）小于（<），大于等于（>=），小于等于（<=） |
转进制IO
一些格式化符：
| 进制 | iomanip 格式化符 |
printf 格式化符 |
|---|---|---|
| 十进制 | dec |
%d |
| 八进制 | oct |
%o |
| 十六进制 | hex |
%x |
注意 cin 的格式化符延长至整个程序，用 dec 恢复！！
位运算应用
- 快速幂
- 最大公约数
1 快速幂
给定 (a,n) 计算 (a^n)。
最朴素的做法当然是 (mathcal{O}(n)) 暴力乘。
typedef long long ll;
ll power(ll a,int n)
{
ll ans=1;
for (int i=0;i<n;i++) ans*=a;
return ans;
}
我们优化一下。
如果我们计算 (7^{31})。
我们做一下变式：
(egin{aligned} 7^{31}&=7^{2^0+2^1+2^2+3^3}\ &=7^{1+2+4+16}\ &=7^1 imes 7^2 imes 7^4 imes 7^{16} end{aligned})
我们对于这个变式，考虑二进制拆分。
(31) 正好分成了 (2) 的正整数次幂，是否所有数字都可以呢？
尝试 (7^{11})，(11=1+2+8)，发现少了个 (4)。
(11=(1101)_2)，每一个幂都乘此数的每一位即可。
所以这样模拟即可，(mathcal{O}(log n)) 时间复杂度。
其中 (a^n) 可以用一个 ( exttt{base}=a^{n-1})，( exttt{base}= exttt{base}* exttt{base}) 求得。
typedef long long ll;
ll qpow(ll a,ll b,ll mod) //带上取模QAQ
{
ll ans=1,base=a;
while (b) //没有乘完
{
if (b&1) ans*=base,ans%=mod; //如果这一位为 1，自乘
base*=base;b>>=1;base%=mod; //更新 base，进入下一位（b>>=1）
}
return ans%mod; //如果 b=0，那么如果模数为 1 不加 %mod 就会 WA。
}
2 最大公约数
众所周知有辗转相除法：
朴素算法也就是这个，最坏被卡 (mathcal{O}(log n))。
int gcd(int a,int b){return b?gcd(b,a%b):a;}
我们知道有更相减损术：
我们能减半尽量要减半，具体看代码即可。
typedef long long ll;
ll gcd(ll a,ll b) //优化后
{
if (b==0) return 0; //特判
if (a<b) return gcd(b,a); //交换顺序
if (a==b) return b; //边界
if (a&1) //如果 a 是奇数
{
if (b&1) return gcd(b,a-b); //如果 b 也是奇数，只能更相减损
else return gcd(a,b>>1); //b 是偶数，减半
}
else //如果 a 是偶数
{
if (b&1) return gcd(a>>1,b); //b 是奇数，a 减半
else return 2*gcd(a>>1,b>>1); //都是偶数，一起减半，答案 *2。
}
}
3 xor 一些应用
首先有个性质：
x^0=x，x^1=~x。
x^p^p=x，即异或为异或的逆运算。
因异或为异或的逆运算，所以异或是唯一的可逆运算（位运算中）。
所以可以进行简单加密：
- 两人持有密钥
- 第一人将自己的数字异或密钥后传至互联网
- 第二人收到后再次异或密钥，获得原文。
异或还可以做一个交换：
a=a^b;b=a^b;a=a^b;
缺点：
- 慢
- 不能处理同一个变量
总之，别用这种交换。
4 其他
- 取二进制末 (k) 位：
a&((1<<k)-1)； - 取二进制第 (k) 位：
(a>>(k-1))&1； - 取二进制第一个 (1) 与后面的 (0) 组成的数字（( exttt{lowbit})）：
x&(-x)； - 将最后一个 (1) 去除：
x&=(x-1)； - 将右数第 (k) 位置 (1)：
a=(a|(1<<(k-1)))； - 将右数第 (k) 位置 (0)：
a&=1<<(k-1)； - 将右数后 (k) 位置 (1)：
a&=(1<<(k+1))-1； - 将右数后 (k) 位置 (0)：
a&=~((1<<(k+1))-1)； - 将右数第 (k) 位取反：
a^=(1<<k)； - 将右数后 (k) 位取反：
a^=((1<<(k+1))-1)；
x==-1：~xx==0：!xx%2：x&1