欢迎光临散文网会员登陆 & 注册

如何判断整数运算溢出

2023-07-18 16:35 作者:~Sakuno酱 0人读过 | 我要投稿

首先我们看下无符号整数的加减法

对于一个 $n$ 位的无符号二进制整数 $x$ 有 $0%5Cle%20x%20%5Clt%202%5En$

所以 $x%2By%20%5Cge%202%5En$ 时就溢出了这体现在最高位的进位

再考虑下无符号整数的减法

对于 $x-y$ 因为无符号整数没有负数的概念所以 $x%3Cy$ 时就溢出了

运算器减法运算是用加上补码实现的所以

$x%3Cy%20%5Crightarrow%20x%2B%5Clnot%7By%7D%20%3C%202%5En-1%20%5Crightarrow%20x%2B%5Clnot%7By%7D%2B1%20%5Clt%202%5En$

而 $%5Clnot%20y%2B1$ 刚好是 $y$ 的补码

所以最高位没有产生进为时就溢出了

有符号整数的溢出

假设 $%5Calpha%2C%20%5Cbeta$ 是 $n%2B1$ 位整数他们符号为记作 $a%2Cb$ 地位记作 $x%2Cy$

显然有

$%5Calpha%3D%5Ba%2Cx%5D%3Dx-a%5Ccdot2%5En$

$%5Cbeta%3D%5Bb%2Cy%5D%3Dy-b%5Ccdot2%5En$

理论上

$%5Calpha%2B%5Cbeta%3D(x%2By)-(a%2Bb)%5Ccdot2%5En$

实际结果分类讨论

$a%3Db%3D0$ $x%2By%3C2%5En$ 结果其实是 $x%2By$ 没有溢出 $C_%7Bn%2B1%7D%3DC_n%3D0$
$a%3Db%3D0%20$ $x%2By%20%5Cge%202%5En$ 因为进位进到符号位上去了实际结果是 $x%2By-2%5E%7Bn%2B1%7D$ 溢出了 $C_%7Bn%2B1%7D%20%3D%200%20$ $C_n%3D1$
$a%3D0%20$ $b%3D1$ $x%2By%3C2%5En$ 结果其实是 $x%2By-2%5En$ 没有溢出 $C_%7Bn%2B1%7D%3DC_n%3D0$
$a%3D0%20$ $b%3D1$ $x%2By%20%5Cge%202%5En$ 实际结果是 $x%2By-2%5E%7Bn%7D$ 没有溢出 $C_%7Bn%2B1%7D%3DC_%7Bn%7D%3D1$
$a%3D1$ $b%3D1$ $x%2By%3C2%5En$ 世界结果是 $x%2By$ 溢出了 $C_%7Bn%2B1%7D%3D1%20$ $C_n%3D0$
$a%3D1$ $b%3D1$ $x%2By%5Cge2%5En$ 世界结果是 $x%2By-2%5En-2%5En$ 没有溢出 $C_%7Bn%2B1%7D%3DC_n%3D1$

所以就是 $C_%7Bn%2B1%7D%20%5Cne%20C_n$ 时会溢出这可以用异或运算得到

标签：

如何判断整数运算溢出的评论 (共条)