Chapter 2.2 Integer Representations

大量数学表达式预警⚠️⚠️⚠️~~(但其实都是小学二年级就学过的难度)~~。

课堂上时间的限制仅仅提到位权表达式，没有运用这个式子去推导性质。而很多性质又是直接给出，没能加以证明，毕竟计算机是实践的科学，一些简单好懂一眼丁真的性质也没有必要去大费周章的证明。

但笔者认为如果学有余力，从位权、同余的角度，用数学的语言去合理表述与证明这些性质，对于理解计算机中整型表示与了解计算的底层数学原理也是颇有裨益 👍

本节以及下一节中式子部分来源于 CS:APP 教材，部分来源于笔者自己推导，难免会有疏漏，如果发现什么错误或者更简洁严谨的推导，欢迎在仓库的issue中提出，或者提个PR👏

计算机中的数据是对现实世界数据的有限近似

Unsigned

编码方式相对简单，直接按位权编码，可以按下面的方式形式化定义函数 \(B_{2}U_{\omega}\) (Bits to Unsigned)。

\[B_{2}U_{\omega}(\boldsymbol{x})=\sum_{i=0}^{\omega-1}x_{i}·2^{i} \]

其中 \(\boldsymbol{x}\) 是编码的位向量，位向量长度为 \(\omega\)，\(x_{i}\) 代表位向量第 \(i\) 位。

Signed: two's-complement encode

相信经过一年半的计算机学习，你已经对编码有过多次了解，那么本文档默认你清楚原码，反码，补码的基础概念，如果在以前的课摆了如今悔过从头再来，又或是有点记不清了，不妨试试 GPT or Deepseek，相信你会得到满意的答案 👍

绝大多数计算机编码有符号数均采用补码编码，后文的重点也将落在补码上。部分同学或许觉得反码或者原码这种更为直观简单的编码或许更好理解，但从位运算以及电路的角度上看，补码更为简洁高效，一个最直观的例子就是加法。

本课程和文档不会进一步深入讨论为什么补码优于反码和原码,如果十分感兴趣，或许你在数电课上会找到答案 🧐

补码的基本定义

在听过无数个老师讲过无数次补码以后，个人认为，用位权的方式定义补码最为清晰，对各种性质的证明也最为严谨。课上由于时间原因没能讲到补码自身以及其运算很多性质的证明，本文均会采用位权的方式补充证明，包括下一节中的位移、加法溢出等等。同样形式定义函数 \(B_{2}T_{\omega}\) (Bits to Two's):

\[B_{2}T_{\omega}(\boldsymbol{x})=-x_{\omega-1}·2^{\omega-1}+\sum_{i=0}^{\omega-2}x_{i}·2^{i} \]

其中数学符号定义与无符号数中相同，编码的主要差异在于无符号数最高位表示权重为 \(+2^{\omega-1}\)，而补码编码下最高位位权为 \(-2^{\omega-1}\)。

反码与原码

  1. 反码(One's Complement): \(B_{2}O_{\omega}(\boldsymbol{x})=-(x_{\omega-1}·2^{\omega-1}-1)+\sum_{i=0}^{\omega-2}x_{i}·2^{i} \)

  2. 原码(Sign-Magnitude): \(B_{2}S_{\omega}(\boldsymbol{x})=(-1)^{x^{\omega-1}}\sum_{i=0}^{\omega-2}x_{i}·2^{i} \)

原码的定义比较好理解，应该和其他课接触的定义保持一致，其中反码就相对抽象了，我们第一次接触反码时的定义往往是正数原码按位取反，非常直观，我们这里简单证明一下两种定义等价。

记任意正数原码真值为 \(Tval\)，那么按位取反后除符号位外位权和为 \(Dval=(2^{\omega-1}-1)-Tval\)，而考虑符号位权值，则 \(Tval'=Dval-(2^{\omega-1}-1)=-Tval\)。两种定义形式等价。

观察反码与补码的位权定义，可以很容易的发现 ~x+1=-x 这一性质，这也是大多数其他课程定义的补码。

进一步思考原码补码，对于一个非负数 \(x\) 其位向量表示为 \(\boldsymbol{x}\)，我们试图定义 \(-x\) 的位形式。

  1. 补码定义 \(1[00...0]_{\omega}-\boldsymbol{x}\) 为 \(-x\) 的位向量。

  2. 反码定义 \([11...1]_{\omega}-\boldsymbol{x}\) 为 \(-x\) 的位向量。

有了这个理解，在整型运算时你对所谓的模数系统的理解也会更深入。

Mapping Between Signed & Unsigned

转换方法

要将有符号数与无符号数相互转化，一种很自然的想法就是：我们不改变位向量，仅仅改变位向量的含义。那既然位向量保持不变，那么对比无符号数以及补码定义的有符号数的位权式，转化就十分显然了。

\[B_{2}U_{\omega}(\boldsymbol{x})=x_{w-1}·2^{\omega}+B_{2}T_{\omega}(\boldsymbol{x})\]

C语言中的转换

int foo = -1;
unsigned bar = 1;
foo < bar == true ?

相信上过课的同学对这个小谜题不会太陌生，既然都问你了，答案肯定是反直觉的那个啦~~(某种意义上来讲符合程序员直觉)~~。

C语言中若表达式既包含有符号数又包含无符号数，C编译器会隐式的全部转换为无符号数再执行运算。\(-1\) 根据刚刚的公式转换为无符号数后应为 \(2^{32}-1\)，那么结果自然是foo > bar.

Expanding and Truncating

了解了有无符号数在计算机中的相互转化，计算机中还存在不同位数的整型相互转化。比如，C 语言中的 short、int、long等类型之间相互转化。

位表示的截断

截断的法则相对简单，先讨论无符号数的截断。

将一个 \(\omega\) 位的无符号数 \(x\) 截断为 \(k\) 位的 \(x'\)，直接将 \([k..\omega-1]\) 位舍弃即可。从位权数值的角度，实际上 \(x'=x \space mod \space 2^{k}\)，因为显然有:

\[x'=\sum_{i=0}^{\omega-1}x_{i}·2^{i} \space mod \space 2^{k}=\sum_{i=0}^{k-1}x_{i}·2^{i}\]

而对于有符号数，截断方式在位向量法则是完全一致。可以转化为无符号数，按照无符号数的方法截断，再转化为有符号数，但考虑到同余关系：

\[x_{\omega-1}·2^{\omega}+x \equiv x(mod \space x^{k})\]

所以从数值的角度考虑，直接视作无符号数取模(如果你对模运算不熟悉，或许你应该注意模运算结果恒为正数)得到新的值后再考虑最高位的权值。

这里值得注意的是如果最高位是 \(1\) 需要减去 \(2^{k}\) 而非 \(2^{k-1}\) 。

位表示的拓展

我们希望较小类型转换为较大类型时保持其值的不变。对于无符号数法则简单，直接拓展位上填 \(0\) 就可以了。

但对于有符号数，直接简单在延伸的位上填 \(0\) 显然无法保持数值不变。应当填充符号位的值！

  1. 当符号位为 \(0\) 时，显然与无符号数相同。

  2. 当符号位为 \(1\) 时，如果从反码类似的观点来看，我们将补码意义下当符号位为 \(1\) 时的 \(0\) 才视为绝对值权值的贡献者，那么在高位填充 \(1\) 显然可以保持值不变。但由于前文一直没有提到这种观点，这里还是延续前文的位权给出一个证明。

若从 \(\omega\) 位长拓展到 \(\omega'\) 位长，显然位拓展没有影响到 \([0..\omega-2]\)位的权值，只需考虑从 \([\omega-1..\omega'-1]\) 位引入的权值变化，这些位在补码意义下权值和为:

\[-2^{\omega'-1}+\sum_{i=\omega-1}^{\omega'-2}2^{i}=-2^{\omega-1}\]

恰好就等于原本最高位 \(\omega-1\) 的权值，所以值保持不变。

© 2025. ICS Team. All rights reserved.