整数运算

无符号整数运算

无符号整数比较简单, 因为其加法, 乘法, 减法 (这里不讨论整数的除法) 运算都是在模域 $2^w$ 下的, 可以直接将结果用人理解的方法算出来. (如果有需要的话把算出的这个结果转换成二进制表示.)

加法溢出

一个判断无符号加法是否溢出Overflow的简单方法是, 假设两个加数为 $x, y$, 结果为 $s = x + y$. 如果存在溢出, 则一定有 $s < x$ (且 $s < y$). 证明很简单, 略.

补码整数运算

由于补码表示的数其实是一个阿贝尔群Abelian Group, 性质和模域比较像, 可以暂且理解为一个模域加上偏移. 所以, 无论加减还是乘法, 运算之后, 如果存在溢出, 我们可以简单地直接截断保留末尾 $w$ 位, 这就是结果的补码了.

加法溢出

判断是否溢出的一个很平凡的方法是, 如果 $x, y > 0$, $s = x + y < 0$, 则正溢出Postive Overflow; 或者 $x, y < 0$, $s = x + y > 0$, 则负溢出Negative Overflow

取相反数

注意到补码表示的正最大和负最大不对称, 比如 8 位整数的最小值是 $-128$, 而最大值是 $127$. 取相反数在 $[-127, 127]$ 之间是没有问题的, 但是如果 $x = -128 (10000000)$, 它的相反数在数学上应该是 $128$, 奈何表示不了. 根据补码的性质, $128$ 是 $127 + 1$ 溢出的数, 最大值溢出了以后就是最小值了. 所以最小值的相反数是它本身.

$$-x = \begin{cases} \mathrm{MIN}, &x = \mathrm{MIN} \\ -x, &x > \mathrm{MIN} \end{cases}$$

在补码的二进制表示下, 取相反数还有一个重要的性质, 即把二进制的最后一个 $1$ 之前的位全部取反. 这个性质很容易证明. 略. 再来看最小值, 它形如 $10 \dots 0$, 最后一个 $1$ 在最高位, 按照这个变换规则, 它就还是它自己.

这里就不得不提到 lowbit 操作了. lowbit 是仅取最低位 $1$, 其他位取 $0$ 的数. 它的实现就利用了这个性质, lowbit(x) = x&(-x).

位移运算

位移Shift运算可以很方便的求乘以 $2^k$ 或者除以 $2^k$.

左移

无论无符号数还是补码表示的整数, 左移Left Shift都很简单, 像之前一样截断到最后 $w$ 位, 就是结果了.

需要说明的一点是, 补码表示的负数在左移之后可能符号位会变成 $0$, 这是正确的结果, 因为此时发生了负溢出.

加减法结合左移运算可以用来代替常数乘法, 并且速度比乘法快很多. 具体来说, 把乘数二进制分解为 $\sum 2^{k_i}$, 然后通过结合率先算 $x \cdot 2^k_i = x « k_i$, 最后求和.

有时候还可以构造减法, 进一步减少求和的次数, 加快运算.

右移

右移Right Shift分为逻辑Logical右移和算数Arithmetic右移. 逻辑右移一般针对无符号整数, 而算数右移针对补码表示的整数. 逻辑右移很简单, 就是高位补 $0$ 即可. 而在补码表示下, 如果是负数, 那么高位补 $0$ 就错了. 这时应该高位补 $1$. 综合来说, 算数右移就是高位 补符号位.

除以常数没法用右移加速.