0%

整数的运算

错误的产生

在C语言中,将两个正数相加可能会得到一个负数,x < yx - 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