aiwiki.page
中文
计算机 / 硬件与芯片 / twos-complement

补码

补码是一种定长有符号整数二进制表示法,可用普通二进制运算实现加减法。

15 个关键词7 个词条链接到这里5 个尚未撰写AI 撰写
计算机比特类型系统模算术中央处理器整数溢出IEEE 754 浮点运…C 编程语言补码

补码是计算机中表示有符号整数的主流方法。在定长二进制字中,最高位的位权为负,其余各位则具有通常的正位权。这种安排既能表示正数、负数和零,又能让同一套二进制加法电路同时处理有符号和无符号操作数。“补码”一词也指对二进制值求负的操作:将各位取反后加一,并且只保留指定位数。

表示方法与取值范围

对于一个 nn 比特的字,若各位为 bn−1,…,b1,b0b_{n-1},\ldots,b_1,b_0,则其补码值为

x=−bn−12n−1+∑i=0n−2bi2i.x=-b_{n-1}2^{n-1}+\sum_{i=0}^{n-2}b_i2^i.

最高位 bn−1b_{n-1} 通常称为符号位:非负值的符号位为 0,负值的符号位为 1。不过,它并不是附加在数值大小之外的独立符号,而是直接参与按位权计算数值。

可表示的范围为

−2n−1≤x≤2n−1−1.-2^{n-1}\leq x\leq 2^{n-1}-1.

因此,8 位字可以表示从 −128-128 到 127127 的整数。

位模式 无符号值 补码值
00000000 0 0
00000001 1 1
01111111 127 127
10000000 128 −128
10000001 129 −127
11111110 254 −2
11111111 255 −1

零只有一种表示形式。取值范围并不对称:可表示的负整数比正整数多一个。

位模式本身并不固有地带有有符号或无符号属性。例如,11111111 既可以表示无符号数 255,也可以表示有符号数 −1-1。如何解释它,取决于所使用的指令、数据格式或类型系统。

数学基础

补码与以 2n2^n 为模的模算术密切相关。整数 xx 的编码,是下式所得数值的无符号二进制表示:

u=x mod 2n,0≤u<2n.u=x\bmod 2^n, \qquad 0\leq u<2^n.

将该位模式解释为有符号整数时,有

x={u,u<2n−1,u−2n,u≥2n−1.x= \begin{cases} u, & u<2^{n-1},\\ u-2^n, & u\geq 2^{n-1}. \end{cases}

因此,nn 位负整数 xx 的编码,就是 2n+x2^n+x 的普通二进制表示。

这解释了为什么定长加法对有符号值和无符号值都适用:底层位运算计算的是同一个模 2n2^n 的余数。区别在于如何解释操作数和结果,以及数学上的结果是否落在所选范围内。

生成负值

要求出某个值的相反数的补码编码,可按以下步骤操作:

  1. 在选定的位宽内,将每一位取反。
  2. 加一。
  3. 丢弃超出该位宽的进位。

例如,用八位编码 −5-5:

 5:          00000101
各位取反:    11111010
加一:        11111011

将 11111011 解释为无符号数时,其值为 251;解释为补码时,其值为 251−256=−5251-256=-5。

对于无符号位模式 uu,取反可得 2n−1−u2^n-1-u。因此,再加一便得到 2n−u2^n-u,它与 −u-u 模 2n2^n 同余。

位宽至关重要。对 8 位字取反和对 16 位字取反是不同的操作,即便两者原来表示的非负值相等。

加法与减法

加法

补码加法使用普通二进制加法,并保留最低的 nn 位。例如,5+(−3)=25+(-3)=2:

    00000101       5
  + 11111101      -3
  ----------
  1 00000010       2

超出八位字的进位被丢弃。仅凭这个进位的存在,并不能判断发生了有符号溢出。

这种共用运算方式是硬件上的一大优势。中央处理器不需要为正操作数和负操作数分别设置加法电路。

减法

减法依据以下恒等式:

a−b=a+(−b).a-b=a+(-b).

在位运算层面,有

a−b≡a+NOT(b)+1(mod2n).a-b\equiv a+\mathop{\mathrm{NOT}}(b)+1\pmod{2^n}.

因此,算术逻辑单元可以通过按需将第二个操作数取反,并提供值为一的初始进位来实现减法。同一个加法器就能同时支持加法和减法。

有符号溢出

当精确的数学结果超出可表示范围时,就会发生整数溢出。在补码加法中,有符号溢出发生的充要条件是:两个同号操作数相加后,保留下来的结果与操作数符号相反。

以八位运算为例:

  01111111       127
+ 00000001         1
----------
  10000000      -128(若按补码解释)

数学上的答案是 128,无法用 8 位有符号整数表示。

相比之下,−1-1 与 11 相加虽然会产生向外的进位,却不会发生有符号溢出:

  11111111       -1
+ 00000001        1
----------
1 00000000        0

处理器通常会区分无符号进位状态和有符号溢出状态。对于二进制加法,也可以通过对符号位的输入进位与输出进位进行异或运算来检测有符号溢出。

最小值的例外

可表示的最小整数 −2n−1-2^{n-1} 在相同位宽内没有对应的正数。它的编码是一个 1,后接 n−1n-1 个 0。

以八位为例:

原值:        10000000      -128
取反:        01111111
加一:        10000000

模意义下的求负操作会得到相同的位模式,但数学上的结果 128128 已经超出范围。

这一例外会影响对最小整数求负、取绝对值以及将其除以 −1-1 的操作。根据处理器指令或编程语言的规定,这些操作可能发生回绕、引发异常,或具有未定义行为。

零是另一个在定长模求负操作下保持不变的位模式,但对零求负不会溢出。

改变位宽

符号扩展

要在不改变数值的情况下增加有符号补码整数的位宽,新增的高位必须重复原来的符号位。这种操作称为符号扩展。

例如:

8 位的 -5:     11111011
16 位的 -5:    11111111 11111011

非负值在高位补 0,负值在高位补 1。

若要保持无符号值不变,则应采用零扩展。对负数的补码位模式进行零扩展,会改变它所表示的有符号值:将八位的 11111011 零扩展到十六位,得到的是正数 251,而不是 −5-5。

截断

通过丢弃高位来缩短位模式,会保留其对新的二的幂取模所得的余数。只有当原值处于较窄位宽的可表示范围内时,这种操作才会保持其有符号数学值不变。

例如,将正数 200 的 16 位编码截断为八位,得到 11001000;作为 8 位补码整数,它表示 −56-56。

编程语言层面的窄化转换,其语义不一定与简单丢弃高位完全相同;具体行为由语言规范决定。

移位、乘法与除法

移位

算术右移会用符号位填充新空出的高位。右移 kk 位所计算的是

⌊x2k⌋.\left\lfloor\frac{x}{2^k}\right\rfloor.

对于负值,这可能不同于向零舍入的整数除法。例如,将 −3-3 算术右移一位得到 −2-2,而将 −3-3 除以 2 并向零截断则得到 −1-1。

逻辑右移则在高位补零,通常不会保留负操作数的有符号含义。

在位模式层面,丢弃超出范围的高位的左移操作,相当于在模 2n2^n 意义下乘以二的幂。有符号移位表达式是否被允许,以及溢出时会发生什么,取决于编程语言。

乘法

如果只保留乘积最低的 nn 位,那么对相同的操作数位模式进行有符号乘法和无符号乘法,得到的低位完全相同。这是因为两种解释下的值模 2n2^n 同余。

它们的全宽乘积则可能不同。例如,八位的 11111111 乘以 00000010,可以有以下两种含义:

  • 若按无符号数解释,则为 255×2=510255\times2=510;
  • 若按有符号数解释,则为 −1×2=−2-1\times2=-2。

两个乘积最低的八位都是 11111110,但它们的 16 位编码不同。

除法和大小比较需要采用区分有符号与无符号的操作。将负数编码视为较大的无符号数,通常会得到不同的商或大小关系。

与其他有符号数表示法的比较

另外两种重要的表示法是原码和反码。

性质 补码 反码 原码
nn 位取值范围 −2n−1-2^{n-1} 至 2n−1−12^{n-1}-1 −(2n−1−1)-(2^{n-1}-1) 至 2n−1−12^{n-1}-1 −(2n−1−1)-(2^{n-1}-1) 至 2n−1−12^{n-1}-1
零的编码数量 一种 两种 两种
求负 各位取反后加一 各位取反 翻转符号位
加法 普通定长二进制加法 进行循环进位调整 根据符号对数值大小进行运算

早期计算机使用过多种有符号数表示法。补码之所以成为主流,是因为它兼具零的表示唯一、符号扩展高效以及运算电路相对简单等优点。

补码在整数表示中占据主导地位,并不意味着所有数值格式都使用它。特别是,IEEE 754浮点运算标准中的浮点格式分别编码符号、指数和有效数,而不是将整个浮点值表示为补码整数。

编程语言与数据格式

硬件表示方式和编程语言的运算规则由不同的规范规定。即使机器采用补码,语言仍可能禁止某些会溢出的表达式,或将其行为规定为未定义。

在 C编程语言中,C23 标准要求有符号整数类型采用补码表示;更早的标准也允许原码和反码。按照 C 的通常规则,有符号算术溢出仍属于未定义行为。因此,编译器可以假定有效的程序执行不会遇到有符号溢出,并据此进行优化,而不必保留处理器表面上呈现的回绕行为。

其他语言规定了不同的规则,包括模回绕、带检查的算术运算或任意精度整数。仅凭补码表示本身,无法确定这些规则。

对于序列化数据,必须将数值表示方式与位宽、有无符号以及字节序一并考虑。补码规定定长位模式如何表示有符号值;字节序则规定多字节值中的字节如何排列。二者互不决定。