[Computer Composition] Representation and Computation – Integer

Representation and Computation – Integer

Representation

The Representation of Integer

Unsigned Integer

这是我们最常见的整数表示法,在进制转换中经常使用该等式作为中介

由于是无符号数,我们并不需要考虑负整数的问题,该表示方式建立了一个二进制位模式十进制非负整数之间的一个简单的双射:

因而,我们说无符号数编码具有唯一性

 

Signed Integer

Tow’s Complement Method

大部分的机器采用补码编码, 补码的含义为:对于非负整数x,我们使用来计算-x的w位表示

补码编码无符号数编码的基础上,将二进制位模式的最高位作为符号位,权重为

也可以把补码编码看成:将无符号数编码求和式最后一项 取相反数从而得到。

注意到,除了最高位拥有一个非常大的负权重之外,二进制位模式中的其他位的权重均为 正权重

进而我们可以表示的

注意这个表示范围,因为

准确地说,补码编码是将整数划分为负数非负数

同理,补码编码也具有唯一性

此外,我们还发现

证明:思路是让等式两边的值相等

Q.E.D

 

Ones’ Complement

反码编码补码编码的区别在于,反码编码最高位的权重补码编码的最高位权重 小1

反码表示的含义为:使用[111...1] - 1来表示-x的反码表示

Sign-Magnitude

原码编码补码编码虽然都是由最高位来决定符号,但原码编码的最高位仅仅用于表示正负

而且,我们注意到后面的部分相等,但由于对负数的表示方法不同

原码编码的 正整数个数 = 负整数个数,并且,我们还发现表示0的位模式有两个: +0 和 -0

多出来的一个0是由补码编码中的最小的负整数 的位模式所得来的。

 

Coding Conversion

T2U


补码编码无符号数编码的区别在于位模式的最高位的权重

因此,需要分情况考虑x的补码编码表示下的位模式的最高位

  1. 最高位 = 0:即x在补码编码下为非负整数,则可以直接转化为 无符号数编码的x

    因为无符号数编码的非负整数的范围 > 补码编码的非负整数的范围,所以当前的非负数必定可以被装下

  2. 最高位 = 1:即x的补码编码下为负数,则在补码编码的表示下,最高位权重为在无符号数的编码表示下,最高位的权重为

    因此,

综上,我们得出结论:

该结论表明,当有符号数(即用补码编码)被映射到无符号数(即用无符号正数编码)时,负数会被转化为大的正数,而非负数保持不变。

 

U2T


Unsigned IntegerTwo's Complement的区别就在于位模式的最高位,而除了最高的其他w-1位所表示的权重是一样的

因此,我们仍然需要从位模式的最高位 的取值情况 来考虑

  1. :在这种情况下,无符号数编码补码编码所表示的含义就是一样的了。

  2. :对于位模式的最高位为1的情况。

我们可以得出结论:

有符号数无符号数转换相关的结论:

综上,Q.E.D

 

Extend Bit Mode

当在不同字长的证整数之间进行转换,同时又想保持数值不变时。

显然,我们只可能从较小的数据类型 -> 较大的数据类型

 

Methods

Zero Extension

 

 

Sign Extension

在需要将补码数字转化为一个更大的数据类型保持数值不变时,可使用符号拓展

也就是说:我们可以将较小的补码数字表示 拓展到较大的补码数字表示并且保持数值不变


由于的部分在补码编码下的拓展前后的前后的权重 相等

故接下来我们只需要证明,我们拓展的位的权重的累加 = 0

但为了证明的简单,我们使用归纳法:仅证明符号拓展了1位的补码编码的数值 不会发生改变,进而得出对补码编码符号拓展任意多位,数值也不会改变

 

分类讨论的取值

  1. :显然成立

Q.E.D

蓝色部分:先考虑从,当位数拓展1位后,拓展前后的第w-1位的含义就不同了

红色部分:这部分是多出来的,可以直接相加即可。第w位的值,权重为

另一种观点是:

加上一个权为-2^w的位 = 将一个权为-2^{w-1}的位 转换为 权为2^{w-1}

PROOF

  1. 如果权重前的系数=0,则显然成立
  2. 如果权重前的系数≠0,则

 

Truncate Integer

截断发生在较大的数据类型 -> 较小的数据类型

Methods

Truncate Unsigned Integer

对于无符号数编码

分别计算等式左侧等式右侧

所有被截去的位的重数都是 因此这些权在 取模操作 下都变为0

也就是说:取模操作可以使得

Q.E.D

Truncate Two’s Complement Integer

等效于将最高有效位的权重 从转换到

注:在对最高位k进行操作之前,如果则我们当然可以 加权但是,在进行 取模操作后,即使,则在取模运算后,我们加权+0

  • 如果,那么权重转换的等效性 显然成立
  • 如果,则在取模运算后,相当于 最高位是废的,本应当加权实际却只加权。这等价于我们损失了数量的权(即实际加权为

Q.E.D

 

Computation

 

Unsigned Addition

 

如果,则该位被丢弃不会影响数值

如果,则该位被丢弃会影响数值丢弃该位最高位=数值减少


Overflow Detection

Unsigned for Non

注:上面的-号并不是减号,而是表示求逆元

根据模数加法(阿贝尔群 Abelian Group):对于


  1. 当x = 0时,加法逆元即为0
  2. 当x > 0时,考虑,有。故下的加法逆元

Tow’s Complement Addition

上述式子告诉我们,补码加法无符号加法之间有完全相同的位级表示

所以,对于运算:可以先将参数转化为无符号数,执行无符号加法,然后再将结果转化为补码


image-20220402193536399

Overflow Detection for Two’s Complement Addition

Two’s Complement for Non


Q.E.D

Unsigned Multiplication

Two’s Multiplication

对于内的整数x和y可以被表示为w位的补码数字

对于C语言的有符号数乘法,是通过将2w位的乘积 截断为 w位来实现的。


无符号数乘法补法乘法位级表示具有等价性

 

Multiply by a Constant