补码溢出判断解析

补码的溢出

利用二进制补码进行运算时，最高位和其余位代表的值不一致，如果补码一共有 \(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}\)。

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

于是可以用异或（非最高位部分相加进位，最高位再进位）判断是否溢出