位运算
位运算
概述
现代计算机中所有的数据均以二进制的形式存储在设备中，即 $0$、$1$ 两种状态计。计算机对二进制数据进行的运算( $+$、$-$、$*$、$/$ )都是位运算，即将符号位共同参与运算的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。
基本的位运算共 $6$ 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。通俗叫法会去掉“按位”，即与、或、异或、取反、左移和右移。
其中，按位与、按位或、按位异或是将两个整数作为二进制数，对二进制表示中的每一位逐一运算；按位取反、左移和右移是对于某一个整数作为二进制数，对二进制表示中的每一位逐一运算。
在位运算时，若两个整数的二进制位数不同，则在位数较少的前面补 $0$ 即可。
整数二进制表
这是一张 $0\sim31$ 的 $十进制\longleftrightarrow二进制$ 对照表。
二进制这个东西可以手推，但是比较麻烦，这张表在位运算的学习和实际应用中很方便比较并找到规律。
| 十进制 | 二进制 |
|---|---|
| 0 | 00000 |
| 1 | 00001 |
| 2 | 00010 |
| 3 | 00011 |
| 4 | 00100 |
| 5 | 00101 |
| 6 | 00110 |
| 7 | 00111 |
| 8 | 01000 |
| 9 | 01001 |
| 10 | 01010 |
| 11 | 01011 |
| 12 | 01100 |
| 13 | 01101 |
| 14 | 01110 |
| 15 | 01111 |
| 16 | 10000 |
| 17 | 10001 |
| 18 | 10010 |
| 19 | 10011 |
| 20 | 10100 |
| 21 | 10101 |
| 22 | 10110 |
| 23 | 10111 |
| 24 | 11000 |
| 25 | 11001 |
| 26 | 11010 |
| 27 | 11011 |
| 28 | 11100 |
| 29 | 11101 |
| 30 | 11110 |
| 31 | 11111 |
与
“与”，就是和的意思。定义如下：
| C++运算符 | 数学符号 | 意义(咋算的) |
|---|---|---|
| & | $&\space、\operatorname{and}$ | 均为 $1$，则结果为 $1$；任意一个是 $0$，结果为 $0$。 |
其对应的结果如下表：
| 数A第 $i$ 位 | 数B第 $i$ 位 | 结果 |
|---|---|---|
| $1$ | $1$ | $1$ |
| $1$ | $0$ | $0$ |
| $0$ | $1$ | $0$ |
| $0$ | $0$ | $0$ |
lowbit
正确的使用与运算(再加上一点技巧)，可以求出某一个数二进制下最低位的 $1$ 的位置。详情请参见树状数组。
或
“或”，即或者。定义：
| C++运算符 | 数学符号 | 意义(咋算的) |
|---|---|---|
| | | $\mid\space、\operatorname{or}$ | 均为 $0$，则结果为 $0$；任意一个是 $1$，结果为 $1$。 |
其对应的结果如下表：
| 数A第 $i$ 位 | 数B第 $i$ 位 | 结果 |
|---|---|---|
| $1$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $0$ | $1$ | $1$ |
| $0$ | $0$ | $0$ |
异或
“异或”，大概就是变异的“或”吧。
| C++运算符 | 数学符号 | 意义(咋算的) |
|---|---|---|
| ^ | $\oplus\space、\operatorname{xor}$ | 均为 $0$ 或均为 $1$，结果为 $0$；两个不同(任意一个是 $1$，另一个是 $0$)，结果为 $1$。 |
其对应的结果如下表：
| 数A第 $i$ 位 | 数B第 $i$ 位 | 结果 |
|---|---|---|
| $1$ | $1$ | $0$ |
| $1$ | $0$ | $1$ |
| $0$ | $1$ | $1$ |
| $0$ | $0$ | $0$ |
异或与加法
一个定理：$a\oplus{b}\le{a+b}$
证明：
我们发现，位运算不进位；而加法运算当两个位都是 $1$ 时会进位。因此，观察上表，异或运算的得数是加法运算进位后剩余的数字。
因此，在加法不进位时，$a\oplus{b}={a+b}$；加法进位时，$a\oplus{b}<{a+b}$。
取反
“取反”，顾名思义，就是 $0$ 变 $1$；