有符号整数的表示 - YHT's Note Repo

%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A - 关于补码 - 设计补码的主要目的是什么？有何优势？ - 对于一个给定的正数或负数，如何怎么得到其补码表示？ - 补码的表示方式是如何推导/设计出来的？ - 给点一个二进制补码表示，如何求得其表示的真值？ - 补码之间的运算是如何进行的？ - 补码的溢出 - 如何判断补码运算是否会溢出？ - 加法溢出、减法溢出、乘法溢出，需要采取不同的判断逻辑 - 如何快速求出补码运算溢出时的溢出结果？ #### 已明确 ![[02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示#^i6lffr]] #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 真值 "真值" 指一个数**在数学上的实际值**，即**正数/负数**分别用 $+/-$ 符号表示。 # 原码原码是对有符号整数的一种**二进制表示方式**，在**给定数据位宽**下： - 最高位为 **符号位**（0 表示非负，1 表示负）； - 其余位为 **数值位**，即 **=="真值绝对值"的二进制表示==**。 - 0 有两种表示： - $+0$： $[0000\;...\;0000]$ - $-0$： $[1000\;...\;0000]$ > [!caution] 原码的缺点 > > 1. **加减运算复杂**：在原码表示下，**加法和减法运算需要根据符号位分别处理**，不能直接利用标准的二进制加法器，这在硬件实现上增加了复杂性。 > 2. **存在+0 和-0 的问题**：在某些情况下可能导致比较和运算的混乱 ### 原码的数值表示范围给定数据位宽 $w$，原码所能表示的**有符号整数范围**为 $[-2^{w-1}+1,\;2^{w-1}-1]$： | | 可表示的数值范围 | 可表示的数值总数 | | --- | :---------------: | :-----------: | | 正数 | $(0, 2^{w-1}-1]$ | $2^{w-1}-1$ 个 | | 负数 | $[-2^{w-1}+1, 0)$ | $2^{w-1}-1$ 个 | | 0 | | 1 | | | | 共 $2^{w}-1$ 个 | - 最大值：$2^{w-1}-1$ ，表示为 $[0111\;...\;1111]$ - 最小值：$-2^{w-1}+1$，表示为 $[1111\;...\;1111]$ > [!example] > > 以 8 位系统下原码所能表示的最大值 $+127$ 与最小值 $-127$ 为例，其原码表示如下： > > - $+127:\;\;[0111\;1111]$ > - $-127:\;\;[1111\;1111]$ > # 反码反码是对有符号整数的一种**二进制表示方式**，在**给定数据位宽**下： - 最高位为**符号位**（0 表示非负，1 表示负），其余位为**数值位**。 - 正数的反码：即为其**二进制表示**； - **负数**的反码：将其 **=="绝对值"的二进制表示全部取反得到==** - **0 有两种表示**： - $+0$： $[0000\;...\;0000]$ - $-0$： $[1111\;...\;1111]$ ### 反码转真值 - 对于正数，其反码即为真值本身的二进制表示； - **对于负数，将反码全部取反得到==真值的绝对值的二进制表示==，再将其解释为负数。也可用下列方法求反码的真值：**各个二进制位 0/1 与对应的 2 的幂次方相乘，其中高位权重取为 $-(2^{w-1}-1)$**，而后累加各项之和。 ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-35126E00D49F8A8D881AE88D74E1B0DF.png|575]] ### 反码的数值表示范围给定数据位宽 $w$，反码所能表示的**有符号整数范围**为 $[-2^{w-1}+1,\;2^{w-1}-1]$： | | 可表示的数值范围 | 可表示的数值总数 | | --- | :---------------: | :-----------: | | 正数 | $(0, 2^{w-1}-1]$ | $2^{w-1}-1$ 个 | | 负数 | $[-2^{w-1}-1, 0)$ | $2^{w-1}-1$ 个 | | 0 | | 1 | | | | 共 $2^{w}-1$ 个 | - 最大值：$2^{w-1}-1$ ，表示为 $[0111\;...\;1111]$ - 最小值：$-2^{w-1}+1$，表示为 $[1000\;...\;0000]$ > [!example] > > 以 8 位系统下反码所能表示的最大值 $+127$ 与最小值 $-127$ 为例，其反码表示如下： > > - $+127:\;\;[0111\;1111]$ > - $-127:\;\;[1000\;0000]$ > # 补码 > 补码（Two's Complement）补码是一种**用于表示==有符号整数==的二进制编码方式**。现代计算机系统中均使用**补码**来表示**有符号整数**。 ## 补码表示的由来 ⭐ ### ❓为什么需要补码？ 根据冯·诺依曼提出的经典计算机体系结构框架，计算机中的运算器**只有加法运算器**，**没有减法运算器**（据说曾尝试过减法运算器，但由于硬件开销太大而不可行）。所以，**计算机中不能直接做减法**。为此，需要**设计一种能够==将减法转换成加法运算==的二进制表示方法**。这正是采用补码的原因。在补码表示下，**"减法" 可以等价转化为 "加法" 实现**，因而**可由==加法器来执行加法和减法==，简化计算机算术逻辑单元（ALU）的设计**。 ### ❓ 补码是如何设计出来的？ **补码** (Two's Complement) 是基于**模运算**系统中的 "**补数**" 设计出来的编码[^1]。在 **模 $m$ 运算系统** 中，两个自然数间的减法 $a-b$ 可**等价转换为加法**，存在以下同余关系： $ \begin{align} a-b &\equiv a+b_{\text {补数 }}\;\;(\bmod m) \\ -b &\equiv b_{\text {补数 }}\;\;(\bmod m) \end{align} $ 其中， $b_{补数}$ 为 **==模 $m$ 下非负数 $b$ 的补数==**，等于 **==模 $m$ 减去 $b$ ==** 得到。 > [!example] > 模 12 系统中，有 $-4 \equiv 8 \quad(\bmod 12)$，则 **$8$ 称之为 $-4$ 的补码**（也称补数）。 > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-4AB74BB8A3E561C0A83C40F680974D25.png|350]] **位宽为 $w$ 的二进制系统**，也即是一个**模 $2^w$ 运算系统**， **二进制减法**可转换为**等价的二进制加法**。（二进制加法**只会保留 $w$ 位而==忽略最高位的进位==**，相当于做了 **$\text{mod} \;\;2^w$**）因此，对于**负数真值 $-b$**，用其**在模 $2^w$ 系统下的==补数 $b_{补数}$ 的二进制表示==** 作为其 "**==补码表示==**"： $ \begin{align} -b &\equiv b_{\text {补数 }}\;\;(\bmod 2^w)\\ [-b]_{补} &=b_{补数}\;\;\; \text{(位宽} w\text{下)} \end{align} $ 由此，**对 $b$ 的二进制减法**都**等价于==加上 $-b$ 的补码表示==** $[-b]_{补}$（即 $b_{补数}$）： $ \begin{aligned} a-b & \equiv a+[-b]_{\text {补}}\;\left(\bmod 2^w\right) \\ & \equiv a+b_{\text {补数 }}\;\;\;\left(\bmod 2^w\right) \end{aligned} $ > [!NOTE] "**补码表示**" 正是由此设计的： > > 二进制位宽 $w$ 下，将其中**一半的位模式** （对应真值 $b_{补数}$）**用作负数 $-b$ 的补码表示**（负数范围 $[-1, -2^{w-1}]$），另一半用于**表示非负数值 $[0, 2^{w-1}-1]$** > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-0A8C2F16188416CE7C241A49F206939A.png|295]] > > 由此： > > - 1）**每个负数都有自己的补码表示**，补码表示下的 **==正、负数之间可以直接相加==**； > - 2）**减法都统一转换为等价的加法执行**， $a-b \equiv a+[-b]_{\text {补 }}\left(\bmod 2^w\right)$ > > 例如： > > - `7 - 5` 只需要用 `7` 的补码和 `-5` 的补码做二进制加法，结果即为 `2` 的补码。 > - `3 - 6` 只需要用 `3` 的补码和 `-6` 的补码做二进制加法，结果即为 `-3` 的补码。 > [!NOTE] 补数 > > 在数学上，"**补数**"（Complement）是对于 **==给定的进位制==**，**相加后能==使得自然数 $a$ 的位数增加 1== 的最小的数**[^2]。 > ——**$a$ 的补数即是给定进制下**，与 $a$ 相加后**能让最高位产生进位的最小数。** > > 设 $d$ 进制下使用 $n$ 位来表示自然数 $a$ ，则 **$a$ 的补数 $a_{补数}=d^n - a$**，称之为 "**$d$ 进制 n 位宽下 a 的关于基数 $d$ 的补数**"。 > （也即==**模 $d^n$ 系统**中 **$a$ 的补数**==） > > 例如，对于自然数 2： > > - 在**二进制**且**位宽为 2**时，2 的补数是 2； 2+2 将由二进制位的最高位产生一个进位 > - 在**十进制**且**位宽为 1** 时，2 的补数是 8； 2+8 将由十进制位的最高位产生一个进位 > - 在**十二进制**且**位宽为 1** 时，2 的补数是 10； 2+10 将由十二进制位的最高位产生一个进位 > - 在**十六进制**且**位宽为 1** 时，2 的补数是 14（D）； 2+D 将由十六进制位的最高位产生一个进位 ## 补码表示的格式给定数据位宽 $w$ 下，**补码**表示规则如下： > [!summary] 补码表示规则 > > 补码： $[X]_{\text {补 }}=\left(2^w+X \right) \bmod 2^w,\;\;\;\;-2^{w-1} \leq X<2^{w-1}$，其中 $X$ 是真值 > > - 最高位为 **==符号位==**（0 表示非负，1 表示负），其余位为**数值位**。 > > - 正数的补码：即为二进制表示本身。 > > - **负数**的补码：可由**三种**方式得到 > 1. 将其 "**绝对值**" 的二进制表示 **==全部取反==后+1**； > 2. 将其 "**绝对值**" 的二进制表示==**保留最低位的 1 及右侧 0 全不变**==，而 **==将高位全部取反==**。 > 3. 用 "**模**" 减去**其绝对值**得到 **==补数==**，**补数的二进制表示**即为该负数的补码 > - 例如 8 位下，$-1 \equiv 255 \quad(\bmod 2^8)$，因此 **$-1$ 的补码**等于**255 的二进制表示**。 > > > - **0 只有一种表示**：$[0000\;...\;0000]$ > > > 其中，**负数的补码** = **给定位宽下==其绝对值的补数的二进制表示==**， > 即 $[-b]_{补} =b_{补数}\;\;\; \text{(位宽} w\text{下)}$ 。 > > 因此，"求负数补码" 的方式实际上是给定二进制位宽下 "**==求负数的绝对值的补数==**" 的方式。 > > ^looeif ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-896AB3244CF2E602F86C9114666E4872.png|344]] ## 真值与补码间的转换 ### 真值转补码 ![[02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示#^looeif]] > [!example] > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-3D5FE96A2550909DCC80EE8AAE573F4E.png|633]] > > 对于真值 $-52$，其绝对值为 $52$， > 而 $52\;(00110100)$ 在 8 位二进制位宽下的 "**补数**" 为 $204\;(11001100)$ ， > 这一**补数 $204$ 的二进制表示 $[11001100]$** 即作为**负数 $-52$ 的 "补码表示"**。 > 即 $[-52]_{补}=52_{补数}=204_2=[11001100]$ > > [!example] > $[-123]_{补数}=123_{{补数}}=133_{2}=128_{2}+5_{2}=[10000101]$ ### 补码转真值 > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-3ACF417E03225D42796A6B77CAC6DC73.png|457]] #### 方式一：通用（理论上的求法）补码表示中，**在给定数据位宽下，==最高位==（符号位）为 "==负权=="（negative weight）**。 **将给定补码转为真值**，**只需将补码表示下各个二进制位 0/1 乘上对应的 2 的幂次方后进行累加（其中==符号位的权值取为"负"==）即可**，如下图所示： ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-B2C509379B185C6EDC9269C5EDD659C3.png|559]] > [!note] 补码表示下各个二进制位的权重示意图 > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-2B527236702283FACB76D716B8A872B1.png|325]] #### 方式二（针对负数） $[-b]_{补} =b_{补数}\;\;\; \text{(位宽} w\text{下)}$ ，因此对该负数 "**补码**" 再求 "**补数**"，即可得到 **==负数的绝对值== $b$**，添上负号即为**补码对应的真值**。求 "**补数**" 的三种方法参见上文。 > [!example] > 例如，给定 8 位的补码 $[1111 1011]$，求其对应真值： > > 1. **确定符号**：最高位是 1，所以这是一个负数的补码。 > 2. 方式二：**保留最低位的 1 及其右侧 0 不变，而反转其余所有高位**，得到 $[00000101]$ 为负数真值的绝对值），因此真值是 $-5$。 > 3. 方式三：**用模 256 减去该补码对应的补数值 251**，得到该补数的补数 $b=5$（负数真值的绝对值），因此真值为 $-5$. > ## 补码的数值表示范围位宽 $w$ 下，**补码**所能表示的**有符号整数范围**为 $[-2^{w-1},\;\;2^{w-1}-1]$：**一半的位模式表示负数**，**另一半非负**。 | | 可表示的数值范围 | 可表示的数值总数 | 边界值 | | --- | :--------------: | :-----------------: | ---------------------------------------- | | 正数 | $(0, 2^{w-1}-1]$ | $2^{w-1}-1$ 个 | 最大值：$2^{w-1}-1$，位模式为 $[0111\;...\;1111]$ | | 负数 | $[-2^{w-1}, 0)$ | $2^{w-1}$ 个 | 最小值：$-2^{w-1}$，位模式为 $[1000\;...\;0000]$ | | 0 | | 1 | | | | | ==**共 $2^{w}$ 个**== | | > [!info] 不同位宽下补码的表示范围 > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-8EAC1E609744E2681D57E24F62DD0B13.png|700]] - 单字节 8 位，数值位为 7 位，补码表示的整数范围为 $[-2^7, 2^7-1]$，即 $[-128，127]$ - 双字节 16 位，数值位为 15 位，补码表示的整数范围为 $[-2^{15},2^{15}-1]$，即 $[-32768,32767]$ - 四字节 32 位，数值位为 31 位，补码表示的整数范围为 $[-2^{31},2^{31}-1]$，即 $[-2147483648, 2147483647]$ - 八字节 64 位，数值位为 63 位，补码表示的整数范围为 $[-2^{63},2^{63}-1]$。 ```text // 补码表示 Int32.MaxValue = 2^31 - 1 = 01111111111111111111111111111111 1 = 00000000000000000000000000000001 0 = 00000000000000000000000000000000 -1 = 11111111111111111111111111111111 Int32.MinValue = -2^31 = 10000000000000000000000000000000 ``` ## 补码的优点采用补码系统进行表示，具有以下**优点**： - **补码表示下，"==减法==" 运算都可通过 "==补码的二进制加法==" 运算完成**，**==能够直接处理负数==**： - 例如，$5-5$ 可表示为 $5+(-5)$，二者对应的**补码表示直接相加**即为算术运算结果： $5\;(0101) + (-5)\;(1011) = 0\;(0000)$ - **补码本身**支持 "**==算术右移==**" 操作 - 例如，$-8\;(1000)>>1$ 得到 $1100$，即为 $-4$ 的补码； - 例如，$-6\;(1010)>>1$ 得到 $1101$，即为 $-3$ 的补码。 - 例如，$-3\;(1101)>>1$ 得到 $1110$，即为 $-2$ 的补码（下取整，向负无穷取）； - **==便于溢出判断==**：当**运算结果超出表示范围**时，**补码可以自然地回绕**，通过**观察操作数和结果的符号位即可判断是否溢出**，而不需要额外的溢出检测逻辑。 - **正溢出**：两个正数相加得到一个负数。 - **负溢出**：两个负数相加得到一个正数。 ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-F8DA2CD9859822492B6075587E69DB22.png|425]] #### 补码的其他特点 - **唯一的零表示**：在补码中 $0$ 只有唯一的表示（所有位都是 0）。（而原码和反码有 $+0$ 和 $-0$ 之分） - **范围不对称**：给定数据位宽 $w$，补码能表示的范围是 $[-2^{w-1},\;\;2^{w-1}-1]$。（而原码和反码是对称范围） - 例如，8 位二进制能表示的范围是 $-128$ 到 $+127$ 。 - **模运算特性**：补码的加减运算等同于**模 $2^n$ 的加减运算**，这使得溢出处理变得自然且一致，硬件实现也更简单。 - **转换简便**：**正数到负数（或反之）的转换只需取反加一**，不需要单独的减法电路。 ## 补码运算 ### 补码表示下的运算结果 ⭐ 在**给定位宽 $w$ 下**，**采用补码表示的有符号数之间的算术运算**，实质上是**两个有符号数对应的补码的==二进制位模式==之间的 "==二进制运算=="**，并**对二进制运算结果==截断保留 $w$ 位==**，再**将所得的==二进制位模式==作为 "==补码=="，==解释为对应真值==。** 其中，给定位宽 $w$ 下 **==二进制位模式之间==（而不是真值之间）的运算** 等价于 **==模 $2^w$ 运算==**： **运算结果保留 $w$ 位即等价于 $\mod 2^w$。** 因此，**$w$ 位补码表示下**两个**有符号数 $x$ 与 $y$** 之间的**算术运算结果**，可按以下方式直接求得: 1. **计算十进制下算术运算的 "==预期结果==" (真值 $r$) 并取 $\mod 2^w$**，得到**二进制位模式本身对应的十进制数 $d$**； - 在模 $m$ 运算里，"取模" 始终都是**取正余数**，即如果为负就一直加到正。 $ \begin{align} r &= x\;\; \text{op}\;\;y \\ \\ d &= r\;\;\text{mod}\;\; 2^w \;\;(0\le d\le 2^{w}-1)\\ \end{align} $ 2. **将 $w$ 位的二进制位模式 $d$ 作为 "补码" ，解释得到对应真值** - 若 **$d$ 大于 $w$ 位补码可表示的最大值 $2^{w-1}-1$** ，则**减去 $2^w$**，得到**补码对应的真值 $T=d-2^w$；** - 若 **$d$ 小于 $w$ 位补码可表示的最小值 $2^{w-1}$** ，则**加上 $2^w$**，得到**补码对应的真值 $T=d+2^w$** $ T=x\;\;\text{op}^t_w\;\;y= \begin{cases} & d, \;\;\;\;\;\;\;\;\;\;\;\text{ if }\;-2^{w-1} \le d \le 2^{w-1}-1 \\\ & d-2^w,\;\;\;\text{ if }\; d>2^{w-1}-1\;\;\;(正溢出) \\ & d+2^w,\;\;\;\text{ if }\; d<-2^{w-1}\;\;\;\;\;\;\;(负溢出) \end{cases} $ 其中： - $r = x\;\; \text{op}\;\;\;\;y$ 为两个**十进制真值 $x$ 和 $y$ 算术运算的直接结果** - $T=x\;\;\text{op}^t_w\;\;y$ 为两个**十进制真值 $x$ 和 $y$ ==在 $w$ 位补码表示下==进行相同运算所得的结果 > [!example] 8 位宽补码表示下，有符号数之间的运算示例： > > - $4\;*^T_8\;127=>-4$ > - 十进制下 $4*127=508$ ，二进制截断保留 8 位得 $508\%256=252\;[1111\;1100]$，作为补码解释为 $-4$（$252-2^8$） > > - $1\; +^T_8\;127=>-128$ > - 十进制下 $1+127=128$，位模式为 $128\;[1000\;0000]$，作为补码解释为 $-128$（$128-2^8$）。 > > - $-1\;-^T_8\;(-128)=>127$ > - 十进制下 $-1-(-128)=127$，位模式为 $127[0111\;1111]$，作为补码解释为 $127$ 。 > > ### 补码加法 **==补码加法==**（给定位宽下）：**将两个操作数的补码表示==直接做二进制加法并舍弃最高位进位==，再将所得的二进制位模式按补码解释为对应真值。 $ [X+Y]_{补码}=[X]_{补码}+[Y]_{补码} $ ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-72A2C3D88B776FD546DA7712D70F62C0.png|625]] - $\large x\;+\;y$ 为两个**十进制整数 $x$ 和 $y$ 的算术加法结果**； - $\large x\;+^t_{w}\; y$ 为 $x$ 和 $y$ 在 **$w$ 位补码表示下的==补码加法==结果**。 > [!example] 补码加法计算示例 (8 位宽) > > **正数+正数**，可能产生**正溢出** > - $1\;[0000\;0001]+127\;[0111\;1111]=-128\;[1000\;0000]$ 正溢出 > - $127\;[0111\;1111]+127\;[0111\;1111]=-2\;[1111\;1100]$ 正溢出 > > **负数+负数**，可能产生**负溢出** > - $-127\;[1000\;0001]+(-127\;[1000\;0001])=2\;[0000\;0010]$ 负溢出 > - $-128\;[1000\;0000]+(-128\;[1000\;0000])=0\;[0000\;0000]$ 负溢出 > - $-1\;[1111\;1111]+(-128\;[1000\;0000])=127\;[0111\;1111]$ 负溢出 > > 正数+负数，不会产生溢出 ### 补码减法 **==补码减法==**（给定位宽下）：**转换为加法运算**， $X-Y => X+(-Y)$ ，**对 $X$ 和 $-Y$ 做补码加法**： $ [X-Y]_{补码}=[X]_{补码}+[-Y]_{补码} $ > [!NOTE] 补码表示下的加法逆元 $-Y$ > > 无论 $Y$ 是正数还是负数，$-Y$ 即是**对 $Y$ 的补码表示再求补码**——即**对 $Y$ 的补码==取反+1== 得到 $-Y$** > > 对于一个**负数 $-b$**（$b$ 是正数），在算术逻辑上**减去 $-b$ 即 $-(-b)=b$** ， > 在补码表示中**体现为==对 $-b$ 的补码表示取反加一==，得到其绝对值 $b$ 的二进制表示（也即 b 的补码表示）** > [!important] 补码取反 > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-69DC7C204208BA90B12A9050826749CE.png|625]] > - $-^t_{w} x$ 是对真值 $x$ **在 $w$ 位补码表示下取反**的结果 > - $-x$ 是对 $x$ **在十进制下的取反**，即**取相反数** > > [!example] 补码减法计算示例 (8 位宽) > > 非负数减正数，不会溢出 > > - $0\;[0000\;0000]-127\;[0111\;1111]=-127\;[1000\;0001]$ > > 非负数减负数，可能产生正溢出 > > - $0\;[0000\;0000]-(-128\;[1000\;0000])=0\;[0000\;0000]+(-(-128))\;[1000\;0000]=-128\;[1000\;0000]$ 正溢出 > - $1\;[0000\;0001]-(-128\;[1000\;0000])= 1\;[0000\;0001]+(-(-128))\;[1000\;0000]=-127\;[1000\;0001]$ 正溢出 > - $1\;[0000\;0001]-(-127\;[1000\;0001])=1\;[0000\;0001]+(-(-127))\;[0111\;1111]=-128\;[1000\;0000]$ 正溢出 > - $127\;[0111\;1111]-(-128\;[1000\;0000])=127\;[0111\;1111]+(-(-128)\;)[1000\;0000]=-1\;[1111\;1111]$ 正溢出 > > 负数减正数，可能产生负溢出 > > - $-1\;[1111\;1111]-127\;[0111\;1111]=-1\;[1111\; 1111]+(-127\;[1000\;0001])=-128\;[1000\;0000]$ 没有溢出 > - $-128\;[1000\;0000]-1\;[0000\;0001]=-128\;[1000\; 0000]+(-1\;[1111\;1111])=127\;[0111\;1111]$ 负溢出 > - $-127\;[1000\; 0001]-127\;[0111\; 1111]=-127\;[1000\;0001]+(-127\;[1000\;0001])=2\;[0000\;0010]$ 负溢出 > - $-128\;[1000\;0000]-127\;[0111\;1111]=-128\;[1000\;0000]+(-127\;[1000\;0001])=1\;[0000\;0001]$ 负溢出 > ### 补码乘法 > ❓位宽为 w 的补码乘法是如何计算的？在硬件层面、高级程序语言层面有何不同？ ^i6lffr 位宽为 w 的两个二进制数相乘，其**结果共需要 ==2w 位==来表示**。 **位宽 w 下的==有符号数乘法==**，**不能直接用两个数的补码做 "二进制乘法"**，因为 **w 与 2w 位宽下的==符号位==的位置不同**。为此，需要先对两个有符号数进行 "**==符号扩展==**" => 均**扩展到 2w 位**，即将**符号位对齐到 2w 下最高位**，再执行 "**二进制乘法运算**"，最终 **==保留 2w 位运算结果==**。如下图所示： ![[Excalidraw/Excalidraw-Solution/有符号整数的表示.excalidraw.md#^group=YW1tJjTXqyPzR4kWJvwND|766]] 由上图可知，**"==w 位补码表示的有符号数乘法==" 与 "==w 位无符号数乘法=="，所得乘法结果==在 2w 位表示下可能不相同==（==低 w 位一定相同==，高 w 位可能不同）** > [!summary] > > - 在**硬件层面的机器指令**中会区分 "**有符号数乘法指令**" 与 "**无符号数乘法指令**"，**硬件会==保留 2w 位的计算结果==在寄存器中** 。 > - **"==w 位补码表示的有符号数乘法=="** 与 "==**w 位无符号数乘法**=="，所得乘法结果**在 2w 位表示下可能不相同** （**==低 w 位一定相同==**，高 w 位可能不同） > > > > > - 在**高级程序语言层面**，通过将 "**2w 位的乘积结果==截断保留 w 位==**" 来得到**乘法运算结果**。 > - 在这种**截断方式下**，无论是**有符号数还是无符号数**，截断所得的 **==低 w 位==的位级表示都是相同的**。 > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-E19C101FFA8B8506F355439E07FACA85.png|454]] ^3v2uar > [!example] w 位有符号乘法与无符号乘法，**==完整 2w 位乘法结果的位模式==** 可能不同，但是==截断保留低 w 位所得的位模式一定相同==。 > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-34103AA3310110C31FBD5A4F76DE37AA.png|613]] > [!info] 两个分别为 n、m 位的乘数，其乘积结果至少为 n + m - 1 位，至多为 n + m 位。 > > ![[Excalidraw/Excalidraw-Solution/有符号整数的表示.excalidraw.md#^group=vozBH2n8|460]] > > #### 截断保留 w 位下，补码乘法的结果求值 **给定位宽 w 下，求补码乘法的运算结果**： ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-FF0C17445566631670804B9BC69F014A.png|604]] - $\large x\;\cdot\;y$ 为两个**十进制整数 $x$ 和 $y$ 的算术乘法结果**（可正可负） - $\operatorname{mod}\; 2^w$ 表示**模 $2^w$，正余数，范围为 $[0, 2^{w}-1]$；** - $U2T_{w}(\cdot)$ 是将**无符号整数对应的 $w$ 位二进制位模式作为补码**，**解释为补码数字** - $\large x\;*^t_{w}\; y$ 为 $x$ 和 $y$ 在 **$w$ 位补码表示下的==补码乘法==结果（截断保留低 2w 位）**。 > [!example] 补码乘法示例 (8 位宽) > > 正数乘法 > > - $2\;[0000\;0010] * 127\;[0111\;1111]=-2\;[1111\;1110]$ > - $3\;[0000\;0011] * 127\;[0111\;1111]=125\;[0111\;1101]$ > - $4\;[0000\;0100] * 127\;[0111\;1111]=-4\;[1111\;1100]$ > - $5\;[0000\;0101] * 127\;[0111\;1111]=123\;[0111\;1011]$ > - $6\;[0000\;0110] * 127\;[0111\;1111]=-6\;[1111\;1010]$ > - $7\;[0000\;0011] * 127\;[0111\;1111]=121\;[0111\;1001]$ > - $127\;[0111\;1111] * 127\;[0111\;1111]=1\;[0000\;0001]$ > > 负数乘法 > > - $-1\;[1111\;1111]*(-128\;[1000\;0000])=-128\;[1000\;0000]$ > - $-2\;[1111\;1110]*(-128\;[1000\;0000])=0\;[0000\;0000]$ > - $-3\;[1111\;1101]*(-128\;[1000\;0000])=-128\;[1000\;0000]$ > - $-4\;[1111\;1100]*(-128\;[1000\;0000])=0\;[0000\;0000]$ > - $-127\;[1111\;1100]*(-128\;[1000\;0000])=-128\;[1000\;0000]$ > - $-128\;[1000\;0000]*(-128\;[1000\;0000])=0\;[0000\;0000]$ > > 一正一负 > > - $2\;[0000\;0010]*(-128\;[1000\;0000])=0\;[0000\;0000]$ > - $3\;[0000\;0011]*(-128\;[1000\;0000])=-128\;[1000\;0000]$ > - $4\;[0000\;0100]*(-128\;[1000\;0000])=0\;[0000\;0000]$ > - $5\;[0000\;0101]*(-128\;[1000\;0000])=-128\;[1000\;0000]$ > - $6\;[0000\;0110]*(-128\;[1000\;0000])=-0\;[0000\;0000]$ > - $127\;[0111\;1111]*(-128\;[1000\;0000])=-128\;[1000\;0000]$ > - $127\;[0111\;1111] * (-2\;[1111\;1110])=2\;[0000\;0010]$ > - $127\;[0111\;1111] * (-3\;[1111\;1101])=-125\;[1000\;0011]$ > - $127\;[0111\;1111] * (-4\;[1111\;1100])=4[0000\;0100]$ > - $127\;[0111\;1111] * (-5\;[1111\;1011])=-123[1000\;0101]$ > - $127\;[0111\;1111] * (-6\;[1111\;1011])=6[0000\;0110]$ > - $127\;[0111\;1111] * (-7\;[1111\;1011])=-121\;[1000\;0111]$ > - $127\;[0111\;1111] * (-127\;[1000\;0001])=-1[1111\;1111]$ ### 补码除法 **==补码除法==**（给定位宽下）： - **只在一种情况下会产生溢出**：$-2^{w-1} / -1$ 时，结果会溢出为 $-2^{w-1}$。 > [!tip] 算术右移 `X>>i` 等价于**除以** $2^i$ **并向下取整（==向负无穷取整==）**，结果为 $\left\lfloor\frac{X}{\Large 2^i}\right\rfloor$。 > [!danger] C++中如果除数为 0，将会导致程序直接异常终止。 ## 补码的溢出（Overflow）在对有符号整数的补码下，溢出包括**正溢出**（Positive Overflow）和**负溢出**（Negative Overflow） - **正溢出**：计算结果超出数据类型 **==可表示的最大正值==** 时，发生**正溢出**，回绕得到一个**负数**； - **负溢出**：计算结果超出数据类型 **==可表示的最小负值==** 时，发生**负溢出**，回绕得到一个**正数**；给定位宽的补码表示下，**加减乘除运算都可能导致溢出**。 > [!info] 补码的溢出 > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示.assets/IMG-有符号整数的表示-F97C15E0B914A9D7F1F44974C2C0013C.png|575]] > > 如上图所示（4 位宽），补码的 "**==溢出边界==**" 是在**给定位宽下补码可表示的 "最大值" 和 "最小值" 之间**， > 而不是在二进制位模式的最大位模式和最小位模式之间。 > > 例如，有符号数 $-1[1111] + 1[0001] = 0[0000]$ **单看二进制位模式（补码）实际上已经发生了回绕**，但并没有溢出，结果仍在 4 位补码可表示的有效范围内。 #### 补码加法的溢出判断 - **==异号==** 的两个数（一正一负）相加， **==不会发生溢出==** - **==同号==** 的两个数相加，结果为 **==异号==** 则表明发生溢出 - **两个正数相加**，若结果为**负数**，表明发生**正溢出**； - **两个负数相加**，若结果为**正数**，表明发生**负溢出**。通过**观察==操作数和结果的符号位是否相同==即可判断是否溢出**，而不需要额外的溢出检测逻辑。 ```cpp bool signed_add_overflow (int x, int y) { // 溢出返回1, 未溢出返回0 int sum = x + y; int neg_over = x < 0 && y < 0 && sum > 0; int pos_over = x > 0 && y > 0 && sum < 0; return neg_over || pos_over; } ``` #### 补码减法的溢出判断 - **同号**的两个数相减，**不会发生溢出** - **正数**减去**负数**，若结果**小于被减数**，则表明发生**正溢出**，溢出得到负值； - **负数**减去**正数**，若结果**大于被减数**，则表明发生**负溢出**，溢出得到正值； ```cpp bool signed_subtract_overflow(int x, int y) { int res = a - b; return (a > 0 && b < 0 && res < a) || (a < 0 && b > 0 && res > a) } ``` > [!caution] **补码减法==不能复用补码加法的溢出判断逻辑==**。 > > 尽管减法都会转换为加法，但由于补码**表示范围非对称**，因此**补码减法不能复用补码加法的溢出判断逻辑**。 > > 例如，$0-(-128)$ 算术加法的预期结果是 128，但在 **8 位**下产生**正溢出得到 $-128$** ： > > 计算机硬件对 $0-(-128)$ 的实际运算过程会转为 $0+(-(-128))$，**即对 $-128$ 的补码表示再取补码**，**得到 $(-(-128))$ 的补码表示**后**与 $0$ 的补码表示执行二进制加法**。 > 然而， 8 位补码表示下是没有正数 $128$ 的，==**对 $-128\;[1000\;0000]$ 再求补码得到的仍然是 $-128\;[1000\;0000]$ **==。 > 此时==**两个二进制位模式的符号位是异号的，但仍然发生了溢出**==，可见补码加法的溢出判断逻辑不适用。 #### 补码乘法的溢出判断通过**除法**来判断补码乘法是否会溢出。 ```cpp bool signed_multiply_overflow(int x, int y) { int p = x * y; return x && p/x != y; // x不为0, 且p除以x不等于y, 则说明溢出. } ``` > [!example] 以 `x` 为 `INT_MIN`，`y` 为 `-1` 为例，此时 `p==INT_MIN`，`p/x==1`, `p/x!=y`，所以**可以判断溢出**。 > [!NOTE] 在硬件层面，对于 2w 乘法运算结果，编译器可通过判断高 w+1 位是否满足全 0 或全 1 来判断，**若满足则未溢出**。 > > 2w 位乘法结果中，**==高 w+1 位全 0 或者全 1==**，说明**乘法运算的结果仍然在 ==w 位有符号数的可表示范围==内**。 > #### 补码除法的溢出判断 - **$w$ 位补码表示**下，补码除法**只在一种情况下会产生溢出**：$-2^{w-1} / -1$ 时，结果会溢出为 $-2^{w-1}$。 #### C++中的溢出示例 ```cpp // 窄化转换-超出范围: 溢出 // long long类型或unsigned int类型的值2147483648转换为int类型. // 2147483648超出了int的表示范围(INT_MAX==214748364), 因此发生溢出. // 2147483648的二进制补码表示是0x80000000 // 位模式0x80000000不变, 但在int类型下被解释为-2147483648. long long lli {2147483648}; unsigned ui {2147483648}; assert((int) lli == -2147483648); assert((int) ui == -2147483648); int v = 2147483648; // long long类型的字面量 assert(v == -2147483648); ``` #### 溢出处理 - **编程中的处理**：在高级语言编程中，通常有特定的异常处理机制或状态标志来检测和处理溢出。 - **硬件中的处理**：许多 CPU 设计包括用于检测算术溢出的标志位，**如 x86 架构中的溢出标志（OF）**。 # 关于计算机中硬件计算的说明 - 硬件执行 **加减运算** 时，不区分**有符号与无符号数**，均应用 **==相同的加减指令==**。 - 硬件执行 **==乘法==运算** 时： - ![[02-开发笔记/03-计算机基础/数据的编码表示/有符号整数的表示#^3v2uar]] # 参考资料 # Footnotes [^1]: [南京大学《计算机系统基础（一）：程序的表示、转换与链接》中国大学慕课，袁春风老师](https://www.icourse163.org/learn/NJU-1001625001?tid=1472100484#/learn/content?type=detail&id=1257458477&sm=1) [^2]: [补数 - 维基百科，自由的百科全书](https://zh.wikipedia.org/wiki/%E8%A1%A5%E6%95%B0)