补码溢出判断解析

补码的溢出

利用二进制补码进行运算时,最高位和其余位代表的值不一致,如果补码一共有 \(m\) 位,每一位为 \(a_i\) 其中 \(i=1,2,3,…,m\) 。则其对应的数为

\begin{equation}
-2^m * a_m +\sum_{i=1}^{m-1}2^i * a_i
\end{equation}

当使用全加器对a,b两个补码相加,即希望得到这样的结果

\begin{equation}
-2^m * a_m -2^m * b_m +\sum_{i=1}^{m-1}2^i * (a_i + b_i)
\end{equation}

但由于补码在全加器下的特性,计算可以分成两块:

1.非最高位部分相加:

\begin{equation}
\sum_{i=1}^{m-1}2^i * (a_i + b_i)
\end{equation}

如果这部分产生了进位,即

\begin{equation}
\sum_{i=1}^{m-1}2^i * (a_i + b_i) \geq 2^m
\end{equation}

此时会使高位加一(对补码相当于 \(-2^m\)),且对次首位 \(-2^m\),于是总的来说使结果 \(-2^{m+1}\) 。可以和普通二进制的加法对比,普通二进制下这两块会抵消。

2.最高位相加

\begin{equation}
-2^m * a_m -2^m * b_m -2^m * c
\end{equation}

\(c\) 是可能存在的进位。如果最高位再产生进位,即

\begin{equation}
-2^m * a_m -2^m * b_m -2^m * c \geq -2^{m+1}
\end{equation}

此时会标记真正的加法进位,如果忽略掉相当于对结果 \(+2^{m+1}\)。

结合最高位和非最高位计算可知

非最高位部分相加进位最高位再进位对结果的实际影响说明
\(-2^{m+1} +2^{m+1} = 0 \)无溢出
\(-2^{m+1} = -2^{m+1}\)溢出
\(+2^{m+1} = +2^{m+1}\)溢出
\(0\)无溢出

于是可以用 异或(非最高位部分相加进位,最高位再进位) 判断是否溢出

发表评论