文章目录
- 线索栏
- 笔记栏
-
- 1. 无符号加法运算的定义与本质
- 2. 正常与溢出的数学描述
-
- 1）分段函数描述
- 2）范围说明
- 3）溢出解释
- 3. 检测无符号加法溢出
-
- 1）原理
- 2）推导
- 3）C语言实现（练习题2.27）
- 4. 无符号加法逆元（求反）
-
- 1）定义
- 2）计算公式
- 3）推导
- 4）练习题2.28
- 总结栏
线索栏
+
w
u
+_w^u
+wu是如何定义的？其本质是什么运算？
−
w
u
x
−_w^ux
−wux？
笔记栏
1. 无符号加法运算的定义与本质
（1）定义：对于两个
w
w
w位的无符号整数
x
x
x和
y
y
y（满足
0
≤
x
,
y
<
2
w
0≤x,y<2w
0≤x,y<2w），定义运算
+
w
u
+_w^u
+wu为：
x
+
w
u
y
=
(
x
+
y
)
m
o
d
2
w
x+_w^uy=(x+y)mod2^w
x+wuy=(x+y)mod2w （2）操作本质：执行普通的整数加法
x
+
y
x+y
x+y，然后将结果截断到
w
w
w位（丢弃超出
w
w
w位的部分）。这等同于计算
x
+
y
x+y
x+y对
2
w
2^w
2w取模的结果。 （3）示例（
w
=
4
w=4
w=4）：
9
+
4
u
12
。
9
+
12
=
21
9+_4^u 12。9+12=21
9+4u12。9+12=21，21的二进制为10101（5位）。截断（丢弃最高位）后得到0101，即十进制 5，与 21mod16=5一致。
2. 正常与溢出的数学描述
1）分段函数描述
x
+
w
u
y
=
{
x
+
y
,
x
+
y
<
2
w
x
+
y
−
2
w
,
2
w
⩽
x
+
y
<
2
w
+
1
x +_{w}^{u} y = \\begin{cases} x + y, & x + y < 2^w \\\\ x + y – 2^w, & 2^w \\leqslant x + y < 2^{w+1} \\end{cases}
x+wuy={x+y,x+y−2w,x+y<2w2w⩽x+y<2w+1
2）范围说明
（1）参数范围：
0
≤
x
,
y
≤
2
w
−
1
0≤x,y≤2^w−1
0≤x,y≤2w−1（即
U
M
a
x
w
UMax_w
UMaxw ）。 （2）真实和范围：
0
≤
x
+
y
≤
2
w
+
1
−
2
0≤x+y≤2^{w+1}−2
0≤x+y≤2w+1−2。 （3）运算结果范围：
0
≤
x
+
w
u
y
≤
2
w
−
1
0≤x+_w^uy≤2^w−1
0≤x+wuy≤2w−1。
3）溢出解释
当真实和 x+y达到或超过 2w时，w位无法表示，结果“回绕”（wrap around），等于真实和减去 2w（即取模）。图2-22和2-23直观展示了正常与溢出区域。 
3. 检测无符号加法溢出
1）原理
对
0
≤
x
,
y
≤
U
M
a
x
w
0≤x,y≤UMax_w
0≤x,y≤UMaxw，令
s
=
x
+
w
u
y
s=x+_w^u y
s=x+wuy。则当且仅当 s<x（或等价地 s<y）时，发生了溢出。
2）推导
（1）若未溢出 (x+y<2w)，则 s=x+y≥x。 （2）若溢出 (2w≤x+y<2w+1)，则s=x+y−2w。由于 y<2w，可得 y−2w<0，因此 s=x+(y−2w)<x。
3）C语言实现（练习题2.27）
/* 判断无符号加法x+y是否溢出。未溢出返回1，溢出返回0 */
int uadd_ok(unsigned x, unsigned y) {
unsigned sum = x + y;
return sum >= x; // 等价于 !(sum < x)
}
4. 无符号加法逆元（求反）
1）定义
在
+
w
u
+_w^u
+wu 运算下，对于每个值 x，其逆元
−
w
u
x
−_w^ux
−wux是满足
x
+
w
u
(
−
w
u
x
)
=
0
x+_w^u(−_w^ux)=0
x+wu(−wux)=0的值。
2）计算公式
−
w
u
x
=
{
x
,
x
=
0
2
w
−
x
,
x
>
0
-\\overset{u}{_w}x =\\begin{cases}x, & x = 0 \\\\2^w – x, & x > 0\\end{cases}
−wux={x,2w−x,x=0x>0
3）推导
（1）当 x=0时，逆元是 0。 （2）当 x>0时，考虑值 2w−x。由于 0<2w−x<2w，且 (x+(2w−x))mod2w=2wmod2w=0，因此 2w−x是 x的逆元。
4）练习题2.28
总结栏
本节核心是理解有限字长下无符号整数加法的模运算本质及其相关性质。
+
w
u
+_w^u
+wu是模
2
w
2^w
2w的加法，结果通过截断高位实现，可能导致溢出（回绕）。
s
<
x
或
s
<
y
s<x或s<y
s<x或s<y）。这为编写安全的无符号加法检查提供了可靠依据。
x
x
x在模
2
w
2^w
2w加法下都有唯一的逆元
−
w
u
x
−_w^u x
−wux。非零数的逆元是
2
w
−
x
2^w−x
2w−x，这解释了为什么 0u -1u会得到一个大正数（
U
M
a
x
UMax
UMax）。
+
w
u
+_w^u
+wu）与数学上的无限精度整数加法不同，这是程序中出现“反直觉”结果（如正数相加得负数/小数）的根本原因之一。理解其模运算特性是预测和解释程序行为的关键。
编程启示：在使用无符号数进行算术运算（尤其是循环条件、数组索引和内存地址计算）时，必须警惕溢出的可能性。利用 uadd_ok进行检查或预先进行数学范围分析是防御性编程的重要部分。
