integer - complement - overflow
02. 整数、补码与溢出
0. 本章先解决什么问题
整数看起来最简单:
1 + 1 = 2
但在计算机里,整数不是数学里无限精度的整数。它是:
固定位宽的位模式
这会带来一系列真实问题:
- 为什么最大整数加 1 会变成最小负数?
- 为什么负数能用二进制表示?
- 为什么补码能让加法器同时处理加法和减法?
- 为什么最小负数取绝对值可能还是负数?
- 为什么无符号和有符号看的是同一串 bit,却值不同?
- 为什么位运算能做权限、状态、压缩和掩码?
本章从 0 解释整数的机器表示,重点是补码和溢出。
这张图把补码的直觉画成一个环:固定位宽只能容纳有限状态,超过边界就会回绕。同一串 bit 在 signed 和 unsigned 规则下可以解释成不同值,排查整数异常必须先确认位宽和解释规则。
这张图怎么读
读补码环时,要把整数看成“有限状态环”:
位宽固定
-> 状态数量固定
-> 加法沿环移动
-> 超过边界就回绕
图里的关键不是某个十进制值,而是边界:
| 边界 | 问题 |
|---|---|
| 最大正数再加 1 | 有符号数进入最小负数 |
| 最小负数再减 1 | 有符号数回到最大正数 |
| unsigned 最大值再加 1 | 回到 0 |
| 同一位模式 | signed / unsigned 解释不同 |
只要你看到数字突然变负、长度变小、比较异常,第一反应应该是:位宽和解释规则有没有越界。
1. 整数为什么需要固定宽度
硬件寄存器、内存读写单元、指令格式都有固定宽度。
常见整数宽度:
| 位宽 | 状态数 | 无符号范围 | 补码有符号范围 |
|---|---|---|---|
| 8 bit | 256 | 0 到 255 | -128 到 127 |
| 16 bit | 65536 | 0 到 65535 | -32768 到 32767 |
| 32 bit | 2^32 | 0 到 2^32-1 | -2^31 到 2^31-1 |
| 64 bit | 2^64 | 0 到 2^64-1 | -2^63 到 2^63-1 |
固定位宽的本质是:
只有固定数量的 bit
只能表示固定数量的状态
数学整数可以无限大,机器整数不行。
2. 负数要解决什么问题
如果只表示非负整数,二进制很直接:
00000101 = 5
问题是负数怎么表示。
最朴素的办法是用最高位表示符号:
0 表示正
1 表示负
这叫原码思想。
以 8 bit 为例:
+5 = 00000101
-5 = 10000101
看起来简单,但有问题:
- 加法电路要额外处理符号。
- 0 有两个表示:
00000000和10000000。 - 减法和加法不能自然统一。
硬件希望计算规则简单、统一、稳定。补码就是为这个目标服务的。
3. 原码、反码、补码
以 8 bit 的 +5 和 -5 为例:
| 表示 | +5 | -5 |
|---|---|---|
| 原码 | 00000101 | 10000101 |
| 反码 | 00000101 | 11111010 |
| 补码 | 00000101 | 11111011 |
补码求负数的规则:
正数位模式
-> 按位取反
-> 加 1
例如:
+5 = 00000101
取反 = 11111010
加 1 = 11111011
-5 = 11111011
这个规则看似奇怪,但它让加法变得非常自然。
4. 为什么补码好用
看 5 + (-5):
00000101
- 11111011
1 00000000
如果只保留 8 bit,最高进位丢弃,结果是:
00000000
也就是 0。
这说明补码有一个巨大优势:
同一个加法器可以处理正数加法、负数加法和减法。
减法可以转成加负数:
a - b = a + (-b)
硬件不需要为所有情况设计复杂分支,而是统一使用二进制加法。
手推:为什么 -x 可以写成 ~x + 1
在 n bit 的世界里,所有计算都绕着 2^n 取模。一个数 x 的相反数应该满足:
x + (-x) = 0
在模 2^n 的环上,-x 等价于:
2^n - x
而 ~x 的含义是把 n bit 内所有位取反。对于无符号解释:
x + ~x = 2^n - 1
所以:
~x + 1 = 2^n - x
这正好是 x 在固定位宽下的相反数。
以 4 bit 的 5 为例:
0101 = 5
~ 0101 = 1010
1010 + 1 = 1011
0101 + 1011 = 1 0000
保留低 4 bit = 0000
因此 1011 就是 4 bit 补码里的 -5。补码看起来像技巧,本质是模运算环上的相反数。
5. 补码的环:整数像一个圈
用 4 bit 补码看更直观:
0000 = 0
0001 = 1
0010 = 2
…
0111 = 7
1000 = -8
1001 = -7
…
1111 = -1
继续加 1:
0111 (7) + 1 = 1000 (-8)
它像一个环:
… -2, -1, 0, 1, 2 …
但在固定位宽下只能保留一圈。
所以溢出后会环绕,不是随机变化。
6. 为什么补码范围不对称
8 bit 补码范围是:
-128 到 127
为什么不是 -127 到 127?
因为总共有 256 个状态:
- 1 个状态表示 0。
- 127 个状态表示正数 1 到 127。
- 128 个状态表示负数 -1 到 -128。
最小负数 -128 的位模式是:
10000000
它没有对应的 +128,因为 8 bit 正数最大只有 127。
这会导致一个经典问题:
abs(最小负数)
在同样位宽里可能无法表示。
7. 溢出:结果超出可表示范围
溢出发生在:
真实数学结果超出了当前位宽能表示的范围。
8 bit 补码:
127 + 1
位模式:
01111111
- 00000001
10000000
按补码解释:
10000000 = -128
所以:
127 + 1 -> -128
这不是因为 CPU 不会加法,而是因为 8 bit 装不下 128。
8. 如何判断有符号加法是否溢出
对于补码有符号整数,一个简单直觉:
两个正数相加得到负数 -> 溢出
两个负数相加得到正数 -> 溢出
一正一负相加通常不会有符号溢出
例子:
01111111 (127)
+00000001 (1)
=10000000 (-128)
正 + 正 得到负,溢出。
再例:
10000000 (-128)
+11111111 (-1)
=01111111 (127)
负 + 负 得到正,溢出。
这类判断用于理解底层,但工程里更重要的是提前识别溢出风险。
手推:先比较范围,再做会溢出的加法
如果要判断:
a + b 是否超过 max
直接计算:
a + b > max
可能已经太晚,因为 a + b 本身先溢出了。
更安全的思路是把式子改写成不会先溢出的比较:
a > max - b
例子:8 bit 有符号范围是 -128..127。检查 120 + 20:
max = 127
b = 20
max - b = 107
a = 120
120 > 107
所以还没真正相加,就能知道结果会超过上界。
负数方向也要检查下界:
如果 b < 0,检查 a < min - b
例如 -120 + (-20):
min = -128
b = -20
min - b = -128 - (-20) = -108
a = -120
-120 < -108
所以会低于下界。
乘法更危险。检查 a * b 时,常见思路是用除法反推边界:
如果 a > 0 且 b > 0:
a > max / b 说明会溢出
核心原则是:不要用可能已经溢出的结果去判断是否溢出。
9. 常见溢出场景
| 场景 | 为什么危险 |
|---|---|
| 中间结果 | 最终结果没溢出,中间计算先溢出 |
| 下标计算 | start + length 超范围 |
| 二分中点 | left + right 可能溢出 |
| 时间换算 | 秒、毫秒、纳秒单位放大 |
| 文件大小 | 大文件长度超过 32 bit |
| 计数器 | 长时间运行后回绕 |
| 乘法 | 比加法更容易超范围 |
| 哈希 | 有时故意溢出,但必须知道规则 |
二分查找中点更稳的写法是思路:
mid = left + (right - left) / 2
它避免先计算可能超范围的 left + right。
10. 有符号和无符号:同一位模式,不同解释
同样 8 bit:
11111111
如果按无符号解释:
255
如果按补码有符号解释:
-1
位模式没变,解释规则变了。
这会影响:
- 比较大小。
- 类型转换。
- 网络协议字段。
- 文件格式字段。
- 二进制打印和调试。
一个危险点:
负数按无符号解释
可能变成非常大的正数。
所以处理长度、下标、大小时,要确认字段是 signed 还是 unsigned。
边界条件:比较前发生类型提升,结果可能已经变了
整数 bug 不只来自加减乘除,也来自比较。危险点在于:比较之前,操作数可能先被转换到另一种解释规则。
考虑 8 bit 的位模式:
11111111
如果它表示 signed,就是 -1;如果表示 unsigned,就是 255。
比较时如果把 -1 转成 unsigned,再比较:
255 > 10
结果为真。人脑以为在比较 -1 > 10,机器实际可能在比较 255 > 10。
这类问题常出现在:
| 场景 | 风险 |
|---|---|
| 长度字段和错误码混用 | -1 被当成巨大长度 |
| 下标计算 | 负下标转无符号后越过边界 |
| 循环条件 | i >= 0 对无符号变量恒真 |
| 协议字段解析 | signed/unsigned 解释不一致 |
排查比较异常时,不要只看源码里的符号,还要看参与比较的实际位宽和转换后的解释规则。
11. 位运算:直接操作 bit
常见位运算:
| 运算 | 作用 | 直觉 |
|---|---|---|
& | 按位与 | 取出某些位 |
| ` | ` | 按位或 |
^ | 按位异或 | 相同为 0,不同为 1 |
~ | 按位取反 | 0 变 1,1 变 0 |
<< | 左移 | 低位补 0 |
| 算术右移 | 右移并保留符号 | 负数高位补 1 |
| 逻辑右移 | 右移高位补 0 | 当成无符号位模式 |
常见用途:
- 权限标记。
- 状态集合。
- 位图。
- 压缩多个布尔值。
- 掩码提取字段。
- 哈希扰动。
- 协议字段打包。
例子:用 bit 表示权限:
0001 = read
0010 = write
0100 = execute
0111 = read + write + execute
检查是否有写权限:
permissions & 0010 != 0
12. 位移和乘除 2 的关系
左移一位通常相当于乘 2:
00000101 (5)
左移 1 位
00001010 (10)
右移一位对非负整数通常相当于除 2 取整。
但要小心:
- 位移可能把高位移丢,造成溢出。
- 负数右移涉及算术右移和逻辑右移差异。
- 编译器和 CPU 已经很擅长优化,不要为了“看起来快”牺牲可读性。
位运算最重要的价值不是炫技,而是理解底层表示和协议字段。
边界条件:位移不是无限精度乘除法
位移操作看起来像乘除 2,但它仍然在固定位宽里发生。
8 bit 里:
01000000 = 64
左移 1 位
10000000
如果按有符号补码解释,结果是 -128,不是数学上的 128。
再看右移。对负数 11111000,按 8 bit 补码是 -8:
算术右移 1 位: 11111100 = -4
逻辑右移 1 位: 01111100 = 124
位模式只差高位补什么,解释结果完全不同。
还有一个边界是移位数量。移位数量等于或超过位宽时,不同环境可能有不同规定或限制;学习时至少要形成警惕:
不要默认 x << k 在任何 k 下都等价于 x * 2^k。
先确认位宽、符号、移位规则和溢出语义。
位移适合表达 bit 字段、掩码和底层编码;如果你只是想写普通乘除,清晰的算术表达通常更可靠。
13. 联系实际:看到整数异常怎么排查
如果整数结果突然变负、变成巨大值、下标异常、长度异常,按这个顺序问:
- 当前整数是多少 bit?
- 它是有符号还是无符号?
- 每一步中间结果是否可能超范围?
- 有没有乘法、单位换算、时间换算?
- 有没有把负数转成无符号?
- 有没有把大范围类型缩窄成小范围类型?
- 有没有把字节序或字段长度解析错?
- 溢出是 bug,还是算法故意依赖环绕?
不要只看最后结果。要找哪一步第一次超出了位宽范围。
小实验:手算 4 bit 补码溢出
用 4 bit 补码表示整数:
范围: -8 到 7
手算下面几组:
| 计算 | 位模式 | 解释 |
|---|---|---|
7 + 1 | 0111 + 0001 = 1000 | -8,正数溢出 |
-8 - 1 | 1000 + 1111 = 0111 | 7,负数溢出 |
-1 按 unsigned 看 | 1111 | 15 |
5 + (-5) | 0101 + 1011 = 0000 | 进位丢弃后为 0 |
这能训练一个非常重要的习惯:
先看位模式
再看解释规则
最后判断是否越界
如果一个长度、下标、时间戳突然变成负数或巨大正数,优先查中间计算是否越过位宽边界,以及 signed/unsigned 是否混用。
14. 学完本章你能解决什么问题
学完这一章,你应该能解决或开始分析这些问题:
- 为什么机器整数必须有固定位宽?
- 负数为什么可以用补码表示?
- 为什么补码能统一加法和减法?
- 为什么补码范围负数比正数多一个?
- 为什么最大整数加 1 会变成最小负数?
- 有符号和无符号为什么能对同一位模式给出不同结果?
- 位运算适合解决哪些底层问题?
- 遇到整数异常时,如何从位宽、符号、溢出、中间结果排查?
整数不是无限数学对象。它是固定长度的位模式。理解这一点,你就能解释大量“看起来离谱”的整数 bug。