整数的运算

在C语言中,将两个正数$x$和$y$相加可能会得到一个负数,$x < y$和$x - y < 0$两个语句得到的结果有可能不一样。这些“莫名其妙”的现象经常会导致bug,编程老手不经意也会犯下错误。了解整数运算的原理有助于写出更可靠的程序。

无符号加法运算

两个$w$位的非负数$x$和$y$的大小范围是$0 \le x, y \le 2^w - 1$,它们的和的大小范围是$0 \le x + y \le 2^{w+1} - 2$,需要用$w+1$位来表示。如果相加所得到的和超出$w$位,将最高位丢弃即可。因此,无符号数加法运算的结果实际上是将它们的和对$2^w$取模,用$+_w^u$表示无符号数加法:

$x +_w^u \ y = (x+y)\, \bmod \, 2^w$$

补码加法运算

有符号数一般采用补码表示。两个$w$位的符号数$x$和$y$的大小范围是$-2^{w-1} \le x, y \le 2^{w-1} - 1$,它们的和的范围是$-2^w \le x + y \le 2^w - 2$,也需要用$w+1$位来表示。实际上,无符号加法和补码加法的运算过程在位模式层次上是完全一样的,而且,大多数计算机对符号数和无符号数做加法都使用同一条指令,只是位模式解析方法的不同造成了结果的差异。得到和的位模式后,溢出则直接舍弃最高位(取模),解析位模式便得到最后的运算结果。用$+_w^t$表示符号数加法:

$$x +_w^t \ y \doteq U2T_w(T2U_w(x) +_w^u \ T2U_w(y)) = U2T_w[(x+y) \bmod 2^w]$$

补码加法运算的结果需要分4种情况讨论,在这里不列出。

补码相反数运算

$w$位补码表示的数字$x$的范围是$-2^{w-1} \le x < 2^{w-1}$。对于$-2^{w-1} < x < 2^{w-1}$,$x$的相反数即为$-x$,此时有$-x +_w^t x = -x + x = 0$。对于$x = -2^{w-1}$,$-x = 2^{w-1}$超出了$w$位数字所表示的范围。因此,特别规定这种情况下$-x = x = -2^{w-1}$。因为$-2^{w-1} + -2^{w-1} = -2^{w}$,根据上述补码加法运算的原则有$-2^{w-1} +_w^t -2^{w-1} = 0$。

乘法运算

有符号乘法和补码乘法如果出现溢出,和上述的加法运算处理方式类似,舍弃多余的高位即可,运算结果在这里就不再列出。

参考

CS:APP