C++位运算及其应用
sdxjzsq
2018-08-12 21:05:13
## 为什么会写这篇blog？
位运算是用来进行玄学优化的一种非常好的途径，特别是在wys大佬的“浅谈计算机系统结构与OI种的使用编程技巧”中体现得淋漓尽致！我就是在看这个pdf的过程中突然发现自己已经不太能记得位运算的一些规则，故搜索之，得到一些便于理解的例子，记下来。
## 位运算！
参考资料：[来谈谈C++ 位运算 & | << >> ^ ~ %](https://blog.csdn.net/fox64194167/article/details/20692645)
### 0.位运算一定记得加括号！！！他的优先级最小！！！
### 1. & 按位与
只有对应的二进制位都为1结果为1，否则为0.
### 2. | 按位或
对应的二进制位中只要一个为1，则结果为1，否则为0.
### 3. << 左移
x<<n表示x向左移动n位，即：
$x<<n==x\times 2^n$
### 4. >> 右移
x<<n表示x向右移动n位，即：
$x>>n==x\div 2^n$
(除法结果保留整数)
### 5. ^ 按位异或
对应的二进制位相同，则结果为0，否则为1.
为了便于理解异或，一定要用这个题目：
一个数组中，所有数字都出现了两次，只有一个没有，请找出这个数字。
统计每个数字次数？NO！只要异或就够了！
只需要想下面这样写：
```cpp
for(int i=1;i<=n;i++)
a[0]^=a[i];
```
最后a[0]便是题目的答案。
为什么呢？因为两个相同的数异或的结果为0，而异或具有交换律，因此最后剩下的就是只出现一次的数了。
借用上面参考资料中的话来说：
**异或是嫉妒成双成对的。**
### 6. ~ 取反
他的结果与当前二进制位上的数相反（0变成1，1变成0）
他满足：$x-y==x+\sim y+1$
因此$\sim y==-y-1$
比如$\sim 11==-11-1==-12$
## 单个位运算符号的妙用！
### 1. &
我们经常要用的是否被2整除，一般都写成 `if(n % 2 == 0)`
可以换成 `if((n&1) == 0)`
### 2. |
(复制自参考资料)
可以用一个unsigned int 来存储多个布尔值。
比如一个文件有读权限，写权限，执行权限。看起来要记录3个布尔值。我们可以用一个unsigned int也可以完成任务。
一个数r来表示读权限，它只更改个位来记录读权限的布尔值
0000000**1** (表示有读权限)
0000000**0** (表示没有读权限)
一个数w表示写权限，它只用二进制的倒数第二位来记录布尔值
000000**1**0 (表示有写权限)
000000**0**0 (表示没有写权限)
一个数x表示执行权限，它只用倒数第三位来记录布尔值
00000**1**00 (表示有执行权限)
00000**0**00 (表示没有执行权限)
那么一个文件同时没有3种权限就是
~r | ~ w | ~ x 即为 00000000，就是0
只有读的权限就是
r | ~w | ~x 即为 00000001，就是1
只有写的权限就是
~r | w | ~x 即为 00000010，就是2
...
一个文件同时有3种权限就是
r | w | x 即为 00000111，就是7
### 3. << 和 >>
用来代替$\times 2$和$\div 2$的运算
### 4. 使用<<和>>代替%
比如求x%8.
按照%的定义，
$a\%b==a-\lfloor {a\over b}\rfloor\times b$
我们还知道，$\lfloor{x\over 8}\rfloor ==\lfloor{x\over 2^3}\rfloor==x>>3$
因此，
$x\%8==((x>>3)<<3)$
### 5. ^用于交换两个数的值
```cpp
void swap(int *a,int *b)
{
*a^=*b;
*b^=*a;
*a^=*b;
}
```
## 综合运用位运算进行玄学加速！
（摘自wys大佬的“浅谈计算机系统结构与OI种的使用编程技巧”）
### 1. 读某个二进制位
``` cpp
inline int read_bit(int x,int pos)
{
return (x>>pos)&1;
}
```
### 2. 将某个二进制位置为1
``` cpp
inline int set_bit(int x,int pos)
{
return x|(1<<pos)
}
```
### 3. 将某个二进制为置为0
``` cpp
inline int clear_bit(int x,int pos)
{
return x&~(1<<pos);
}
```
### 4. lowbit
``` cpp
inline int lowbit(int x)
{
return x&-x;
}
```
### 5. 判断是否是二的幂次
``` cpp
inline bool is2(int x)
{
return !(x&(x-1));
}
```
### 6. 状压DP
- 判断一个数字x二进制下第i位是不是1
``` cpp
if((x>>i)&1>0)
```
这实际上就是我们第1条
- 将一个数字x二进制下第i位更改为1
这实际上就是第2条
- 把一个数字二进制下最靠右的第一个1去掉。
```cpp
x=x&(x-1)
```
这个也可以用来判断x是否是2的次幂：
```cpp
if((x&(x-1))==0)
```
- 枚举状态S的子集
``` cpp
for(int i=S;i;i=(i-1)&S)
work(i);
```
大概就是这些了...
（其实还有bitset，但是因为用不到所以不写了）
位运算万岁！！！