位运算简介
ryanright
·
·
个人记录
1. 基本运算
1. 按位或（|）
与运算位于 C++ 运算符的第十二级。该运算把数字转成了二进制，按照每一位操作，规则如下：
- 两个都是 0，结果为 0；
- 两个都是 1，结果为 1；
- 一个是 1，一个是 0，结果为 1；
也就是说，只要有一个是 1，结果就是 1，否则就是 0。
例如：170|85
转成二进制，分别是 10101010 和 1010101。
10101010
| 01010101
----------
11111111
\therefore170|85=11111111(2)=255
满足交换律，结合律。
a|a=a
a|0=a
2. 按位异或（^）
按位异或位于 C++ 运算符的第十一级，英文又写成 XOR，一般数学中写成 \oplus，同样是每一位操作，规则如下：
- 两个都是 0，结果为 0；
- 两个都是 1，结果为 0；
- 一个是 1，一个是 0，结果为 1；
也就是说，相同为 0，不同为 1，或者也可以理解为二进制中的不进位加法（因此其符号为 \oplus）。
例如：170\oplus85
10101010
^ 01010101
----------
11111111
\therefore170\oplus85=11111111(2)=255
注意，尽管我们在数学中一般写作 \oplus，但在 C++ 程序中，依然要写成 ^。
满足交换律，结合律。
a\oplus a=0
a\oplus 0=a
3. 按位与（\&）
按位与位于 C++ 运算符的第十级，同样是每一位操作，规则如下：
- 两个都是 0，结果为 0；
- 两个都是 1，结果为 1；
- 一个是 1，一个是 0，结果为 0；
也就是说，只要有一个是 0，结果就是 0，否则就是 1。
例如：170\&85
10101010
& 01010101
----------
00000000
\therefore170\&85=0
满足结合律，交换律。
a\&a=a
a\&0=0
4. 位左移（<<）
位左移位于 C++ 运算符的第七级，其将该数的二进制每一位都左移一些位，右边的空余用 0 补齐，左边超出的位会被覆盖掉。例如：
111(2)<<1=1110(2)
如果是八位二进制整数，那么有：
111(2)<<6=11000000
被覆盖掉了一个 1。
事实上，如果 x，y 都是 z 位二进制整数，那么有
x<<y=2^yx\bmod 2^z
因此，位左移可以帮助我们轻松地计算 2^n（即 1<<n）。
5. 位右移（>>）
位左移位于 C++ 运算符的第七级，其将该数的二进制每一位都右移一些位，超出的位会被覆盖掉。例如：
111(2)>>1=11(2)
事实上，
x>>y=\lfloor\frac{x}{2^y}\rfloor
6. 按位取反（~）
按位取反位于 C++ 运算符的第三级，将二进制的每一位都取反，即：
- 1变成0
- 0变成1
例如 ~1010101(2)=101010(2)
满足结合律：~ (~a)=a
7. 复合运算符
二进制中的混合运算符一般有下面五个：
$|=$：或等于。$a|=b\Leftrightarrow a=a|b$；
^ $=$：异或等于。$a$^$=b\Leftrightarrow a=a$^$b$；
$<<=$：左移等于。$a<<=b\Leftrightarrow a=a<<b$；
$>>=$：右移等于。$a>>=b\Leftrightarrow a=a>>b$；
这五个运算符全部位于 C++ 运算符的第十六级。
# 2. 常用应用
二进制中有一些很重要的组合运算，很容易出。
## 1. $lowbit
lowbit(x)$ 指的是 $x$ 的二进制表示中，最低位的 $1$ 所对应的值。例如，$lowbit(12)=lowbit(1100(2))=2^2=4
一般，比较常用的计算 lowbit(x) 的公式有两个，分别是
lowbit(x)=x\&-x
和
lowbit(x)=x\&(x\oplus(x-1))
其中公式二就出现在了 CSP-S1 2019 中。
## 2. $\gcd
```cpp
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
```
然而，事实上，我们还可以写成这样：
```cpp
int gcd(int a,int b)
{
while(b^=a^=b^=a%=b);
return a;
}
```
不用担心爆栈，看上去也更清爽。
```cpp
__gcd(a,b);
```
……
## 3. 快速幂
快速幂需要快速求解
$$b^p\bmod k$$
一般，我们写递归会写成这个样子：
```cpp
long long quickpow(long long b,long long p,long long k)
{
if(p==1) return b%k;
if(p==0) return 1%k;
long long ans=quickpow(b,p/2,k);
if(p%2==0) return (ans%k)*(ans%k)%k;
if(p%2==1) return (ans%k)*(ans%k)%k*b%k;
}
```
还有的会写递推。但是，真正的王者还是位运算：
```cpp
long long quickpow(long long b,long long p,long long k)
{
long long ans=1%k;
b%=k;
while(p)
{
if(p&1) ans=(ans*b)%k;
p>>=1;
b=(b*b)%k;
}
return ans;
}
```
## 4. 集合运算
我们可以将一个自然数集合 $S$ 压缩成一个二进制数 $s$。该二进制数为
$$s=\sum_{i\in S}2^i$$
如果转成了二进制，那么一些集合操作就能够更好地实现。
设有两集合 $A$、$B$，已经转成了二进制数 $a$、$b$，则
1. 空集 $\Rightarrow$`0`
2. 只含有第 $i$ 个元素的集合 $\{i\}\Rightarrow$`1<<i`
3. 含有全部 $n$ 个元素的集合 $\{0,1,2,...,n-1\}\Rightarrow$`(1<<n)-1`
4. 判断第 $i$ 个元素是否在集合 $A$ 中 $\Rightarrow$ `if(a>>i&1)`
5. 向集合 $A$ 中加入第 $i$ 个元素 $\Rightarrow$ `a|1<<i`
6. 从集合 $A$ 中取出第 $i$ 个元素 $\Rightarrow$ `a&~(1<<i)`
7. $A\cap B\Rightarrow$ `a&b`
8. $A\cup B\Rightarrow$ `a|b`
枚举集合 $S$ 的每一个子集时，只需要这样
```cpp
int sub=s;
do sub=(sub-1)&s;
while(sub!=s);
```
每个 $sub$ 都是 $S$ 的子集，且没有缺漏。
## 5. 状态压缩 DP
略（自己撸）。
## 6. 补码
二进制负数在计算机中使用补码存储。
假设 $a$ 是一个二进制正整数，那么 $-a$ 在计算机中的补码是 ~$a+1$。例如，$-1$ 的八位二进制补码是 $11111111$。
知道就好。
## 7. 其他杂碎
假如有二进制数 $x$，那么
|操作|运算|
|:---:|:---:|
|去掉最后一位|`x>>1`|
|在最后加一个 $0$|`x<<1`|
|在最后加一个 $1$|`(x<<1)+1`|
|最后一位变 $1$|`x|1`|
|最后一位变 $0$|`x|1-1`|
|最后一位取反|`x^1`|
|右数第 $k$ 位变 $1$|`x|1<<k-1`|
|右数第 $k$ 位变 $0$|`x&~(1<<k-1)`|
|右数第 $k$ 位取反|`x^1<<k-1`|
|末 $k$ 位|`x&1<<k-1`|
|右数第 $k$ 位|`x>>k-1&1`|
|末 $k$ 位变成 $1$|`x|(1<<k-1)`|
|末 $k$ 位取反|`1^(1<<k-1)`|
|把右边连续的 $1$ 变 $0$|`x&x+1`|
|把右起第一个 $0$ 变 $1$|`x|x+1`|
|把右边连续的 $0$ 变 $1$|`x|x-1`|
|取右边连续的 $1$ |`(x^x+1)>>1`|