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

%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 无符号整数的表示计算机中对于**无符号整数**使用 **==直接的二进制表示==**——给定位宽下，**所有二进制位均用于表示数值本身，没有符号位**。给定二进制位宽 $w$，可表示的**无符号整数范围为 $[0, 2^w-1]$**。 # 无符号整数的运算 **给定位宽 $w$** 下，**无符号整数运算即为==模 $2^w$ 运算==**（$\text{mod}\;\;2^w$），当**运算结果超出可表示范围时会==从 0 开始回绕==**。 ### 无符号数加法 **==无符号数加法==（$w$ 位宽下）**：**两个无符号数的==二进制表示做二进制加法并舍弃最高位进位**==，所得的二进制位模式再直接解释为无符号整数。 $ [X+Y]_{\text{BitPattern}}=[X]_{\text{BitPattern}}+[Y]_{\text{BitPattern}} $ 就运算结果而言，**$w$ 位宽下的无符号数加法**即 **"模 $2^w$ 加法**"——**若结果大于 $2^{w}-1$，就将结果减去 $2^w$ ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/无符号整数的表示.assets/IMG-无符号整数的表示-F752340D8F494A83856E983784B47C01.png|575]] ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/无符号整数的表示.assets/IMG-无符号整数的表示-2227E2581D0B9355BCE414FF800A0DD7.png|325]] > [!example] 无符号整数加法示例 (8 位宽) > > - $1\;[0000\;0001]+255\;[1111\;1111]=0\;[0000\;0000]$ 溢出 > - $255\;[1111\;1111]+255\;[1111\;1111]=254\;[1111\;1110]$ 溢出 ### 无符号数减法 **==无符号整数减法==**（给定位宽下）：**转换为加法运算**， $X-Y => X+(-Y)$ ，**对 $X$ 和 $-Y$ 做二进制加法**： $ [X-Y]_{\text{BitPattern}}=[X]_{\text{BitPattern}}+[-Y]_{\text{BitPattern}} $ > [!important] 无符号数的二进制表示求反 > > ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/无符号整数的表示.assets/IMG-无符号整数的表示-77B10C9B8F55B032F5BC49CE89F56D8D.png|475]] > > 在实际硬件计算中，$a-b$ 通过==转换为**$a$ 加上 $b$ 的补码 $b_{补数}$ 实现**==，即 $a-b=a+b_{补数}=a+(2^w-b)$ > > 其中，$b_{补数}=2^{w}-b$ 可**由 $b$ 的二进制表示==取反加一==得到**。就运算结果而言，**$w$ 位下的无符号数减法**即 "**模 $2^w$ 减法**"：当**被减数小于减数时，将结果加上 $2^w$。 > [!example] 无符号整数减法示例 (8 位宽) > > - $0\;[0000\;0000]-1\;[0000\;0001]=0\;[0000\;0000]+(-1\;[1111\;1111])=255\;[1111\;1111]$ 溢出 > - $0\;[0000\;0000]-255\;[1111\;1111]=0\;[0000\;0000]+(-255\;[0000\;0001])=1\;[0000\;0001]$ 溢出 > - $1\;[0000\;0001]-2\;[0000\;0010]=1\;[0000\;0001]+(-2\;[1111\;1110])=255\;[1111\;1111]$ 溢出 > - $1\;[0000\;0001]-255\;[1111\;1111]=1\;[0000\;0001]+(-255\;[0000\;0001])=2\;[0000\;0002]$ 溢出 > - $2\;[0000\;0002]-255\;[1111\;1111]=2\;[0000\;0002]+(-255\;[0000\;0001])=3\;[0000\;0003]$ 溢出 > - $253\;[1111\;1101]-255\;[1111\;1111]=253\;[1111\;1101]+(-255\;[0000\;0001])=254\;[1111\;1110]$ 溢出 > - $254\;[1111\;1110]-255\;[1111\;1111]=254\;[1111\;1110]+(-255\;[0000\;0001])=255\;[1111\;1111]$ 溢出 > ### 无符号数乘法 **$w$ 位下的无符号数乘法**即 "**模 $2^w$ 乘法**"：当**被结果超出可表示范围时，取 $\operatorname{mod}\;2^w$； ![[_attachment/02-开发笔记/03-计算机基础/数据的编码表示/无符号整数的表示.assets/IMG-无符号整数的表示-B8AF7AF33E97AE5805F2A706CD495870.png|575]] # 无符号整数运算的溢出 **无符号整数运算的溢出结果仍然是非负的，因此==不区分正/负溢出==，只称为"溢出"。** > [!summary] 无符号整数运算的溢出判断 > > 对于两个无符号数 $a$ 与 $b$ 之间的运算： > > - 对于无符号整数**加法**，如果**结果小于任一加数**，则说明发生了溢出。 > - 对于无符号整数**减法**，如果**被减数小于减数**，则发生溢出。 > - 对于无符号整数**乘法**，如果 $a\ne0$ 且 $\large \frac{\text{result}}{a}\ne b$，则发生溢出。 > - 对于无符号整数**除法**，不会发生溢出。 ##### 无符号整数加法的溢出判断 ```cpp title: bool unsigned_add_overflow (unsigned int a, unsigned int b) { unsigned int res = a + b; return res < a || res < b; } ``` ##### 无符号整数减法的溢出判断 ```cpp bool unsigned_subtract_overflow(unsigned int a, unsigned int b) { return a < b; } ``` ##### 无符号整数乘法的溢出判断 ```cpp bool unsigned_multiply_overflow(unsigned int a, unsigned int b) { return a != 0 && result / a != b; } ``` # 参考资料 # Footnotes