学习：回归本源——位运算及其应用
2018chenyu · · 个人记录
<center><h2>学习：回归本源——位运算及其应用</h2></center>
<center>中山一中 陈煜</center>
前言
二进制是计算技术中广泛采用的一种数制。它的基数为2，进位规则是“逢二进一”，借位规则是“借一当二”。程序中的所有数在计算机内存中都是以二进制的形式储存的，位运算就是直接对整数在内存中的二进制位进行操作。
因此，在电子计算机中，位运算可以说是比四则运算更加基础的运算，但是因为它不是数学的基本运算而不容易得到重视，本文将通过位运算及其应用的介绍，使更多
说明
- 约定二进制的最高位为最左边，最低位为最左边，最低位（代表1）记为第0位；
- 若无特别说明，本文中的位运算使用
C++ 运算符表示；
1. 基本运算
1.1 与、或、非、异或
| 与、或、非、异或四种基本运算对应的汇编指令及在 |
与 | 或 | 非 | 异或 |
|---|---|---|---|---|
| $\text | $ |
由上可得：带符号整数和无符号整数并没有对应不同的汇编指令，即带符号整数的符号位进行位运算的规则和其他位相同。
| 位运算，顾名思义是对二进制位的运算，不会涉及进位，进行位运算的效果如下： | $\text{p | q}$ | ||||
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 | ||
| 0 | 1 | 0 | 1 | 1 | ||
| 1 | 0 | 0 | 1 | 1 | ||
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | |
| 0 | 1 | |
| 简单的找个规律：与运算“有0为0”，或运算“有1为1”，非运算”取反“，异或运算“相同为0，不同为1”。然后我们发现，异或运算的规律比较鬼畜，其实异或运算是可以用其它三种运算表示出来的：$\text{a^b=(a | b)&(!a | !b)}$（方法不只一种，有兴趣的读者可以自行探究，十分有趣）。 |
1.2 移位运算
移位运算分为逻辑移位、算术移位、循环移位、带进位移位四种。最后一种我们暂且不讨论（涉及过于高深的CF标志位）。
注意：以下对于”
逻辑移位：
- 逻辑左移，功能为把
x 的每个二进制位向左移动y 位，移动造成的最右边空位用0补位，最左边的数溢出 - 逻辑右移，功能为把
x 的每个二进制位向右移动y 位，移动造成的最左边空位用0补位，最右边的数溢出，与逻辑左移完全相反
算术移位：
- 算术左移，与逻辑左移完全相同
- 算术右移，区别于逻辑右移的是最左边空位用符号位（最高位）补位，其余相同
循环移位：（顾名思义啦）
- 循环左移：区别于逻辑左移的是最右边空位用最左边溢出的数补位
- 循环右移：区别于逻辑右移的是最左边空位用最右边溢出的数补位，与循环左移完全相反
移位运算的数学含义：
逻辑移位被用于处理无符号整数，算术移位被用于处理带符号整数。
左移
举个例子就好懂了：0101左移1位，变成1010，5变成10；感性理解为相邻的二进制位、高位代表的权值为低位的两倍。
为什么有、无符号整数右移方式不同？（以八位有符号二进制举例）
计算机一律使用补码进行运算，补码由符号位、数值位组成，补码规则如下:
- 正整数，与原码相同，例：+9的补码是00001001；
- 负整数，将其原码除符号位外的所有位取反后加1，例：-5的原码（10000101）
\Rightarrow 除符号位外所有位取反\Rightarrow （11111010）\Rightarrow 加1\Rightarrow -5的补码（11111011）； - 0，+0和-0的补码是一样的，即0的补码是唯一的，为00000000；
用补码进行运算，减法可以用加法实现，例：9-5 = 9+(-5) = 00001001 + 11111011 = 00000100 = 4，也就是说符号位可以直接参与运算了，这是原码、反码所没有的优点，为乘除法器算器铺平了道路，这是后话。
我们发现，原码除去符号位就成了“绝对值”，而负整数的补码每一位经原码反转所得，假如我们用逻辑右移给高位补0的话，反转回原码反而绝对值变大了，与我们所期待的数学含义矛盾，因此我们给他补1从而使得移位运算在处理负数时数学含义不变。
在
表示方法如下：
| 左移 | 右移 |
|---|---|
| << | >> |
但是我们发现，对于带符号整数，我们不能进行逻辑右移了，但是不用慌，把它强行转换成无符号整数后（符号位就是最高位）就可以进行逻辑移位了，移完再转换成带符号整数（最高位变成符号位）即可。