软考复习:补码、溢出与位运算边界

补码计算容易把“二进制结果”与“它代表的有符号整数”混在一起。

edyang · 2013-01-25

补码计算容易把“二进制结果”与“它代表的有符号整数”混在一起。先固定字长,才能判断溢出。

本文使用经典算法与关系数据库的纸面例题。复习时把概念放进一个可手算的小问题:先声明假设,再列状态变化,最后检查反例。题目中的边界条件往往比公式本身更容易失分。

1. 从现象推到机制

八位有符号补码的范围是不对称的,最小负数的绝对值无法用同样位数的正数表示。进位位不等于有符号溢出位:两个正数相加得到负数,才是值得检查的情况之一。Java 的 int 固定三十二位,右移还区分符号扩展。

软考复习:补码、溢出与位运算边界的处理、反馈与观察关系

图中的四个节点分别表示数学整数、固定字长、符号解释、边界检查。顺着实线检查输入如何变成输出,再沿虚线核对反馈条件。图示表达的是本文讨论的关系,不是实测曲线或现场截图。

2. 最小实现与输入条件

先在纸上做八位演算,再使用 Java 的掩码保留低八位。把显示值与有符号解释分成两步,可以避免把截断误认为任意精度计算。

1
2
3
4
int raw = (100 + 60) & 0xff;
int signed = raw >= 128 ? raw - 256 : raw;
System.out.println(raw);    // 160
System.out.println(signed); // -96

例题中的规模和耗时都是教学输入。先手算一遍,再用短程序核对;记录推导过程,避免只背住选项或最终数字。实际系统的性能不能直接从纸面复杂度推出。

3. 用对照区分原因

下表列出需要主动改变的条件。预期行为来自机制分析,复现时还需记录运行环境和原始输出,不能将预期当作已经测得的结果。

改变的条件 需要验证的行为
两个正数相加越界 截断后的符号可能翻转
负数使用无符号右移 高位补零而非复制符号
最小负数取相反数 同字长下仍无法表示其正值

对照 1:两个正数相加越界

截断后的符号可能翻转。观察时记录低八位结果与数学和。把这个条件与基准情形分开,有助于判断变化来自哪一层;若得到相反结果,应先核对前提,再修改实现。

对照 2:负数使用无符号右移

高位补零而非复制符号。观察时记录固定字长下的位模式。把这个条件与基准情形分开,有助于判断变化来自哪一层;若得到相反结果,应先核对前提,再修改实现。

对照 3:最小负数取相反数

同字长下仍无法表示其正值。观察时记录范围上下界是否对称。把这个条件与基准情形分开,有助于判断变化来自哪一层;若得到相反结果,应先核对前提,再修改实现。

4. 适用条件与取舍

位运算适合协议字段和状态掩码,但业务金额不能依赖溢出后的值。把窄类型提升为 int 后,仍要在缩窄转换处检查范围。

一次正常运行只覆盖了这组输入。继续扩展前,应把上面的异常对照保留下来,尤其关注“最小负数取相反数”这一分支。后续方案若改变了图中任意一处依赖,原来的判断就要重新验证,不能仅凭界面相似或返回值相同沿用结论。

同月延伸

参考资料

  1. MIT 算法课程资料
  2. Java SE 7 API 文档