0x01 位运算（2）

0x01 位运算（2）本节主要内容：第一部分：补码反码、移位运算、快速幂、快速乘法第二部分：二进制状压、成对变换、lowbit运算，Barrett模乘（补充）五、 二进制状压说起状压，我们更熟悉的一个名词是状压DPDP，即动态规划，是一种以空间换时间的算法（准确来说是思想）当时间复杂度进入预期范围内，我们有时会发现，空间复杂度超出预期，于是，我们需要压缩空间以课本习题最短Hamilton路径为例，在压缩空间时，我们将“点被经过的状态”与二进制数码0/1对应，n个点的状态压缩在一个n为二进制数中，需要访问时移位计算取出状态。从而，我们用这个二进制数表示全局状态，并可以将其作为dp数组的下标使用，写出更清晰的状态转移方程。六、 成对变换通过计算可以发现$$\begin{aligned} 0\quad xor\quad 1 = 1\\ 1\quad xor\quad 1 = 0\\ \dots\\ \\ n\quad xor\quad 1 = n+1\quad n为偶数\\ n\quad xor\quad 1 = n-1\quad n为奇数\\ \end{aligned}$$该结论可用于图论，用于存储一对无向边七、lowbit运算何为lowbit，顾名思义，与“最低位”有关下面给出几个算式（后缀B表示该数为二进制数，逗号为隔位符便于）$$\begin{aligned} lowbit(01011000B) = 00001000B \quad 即lobit(88)=8\\ lowbit(01001100B) = 00000100B \qua