浅谈位运算

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