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的补码编码表示下的位模式的最高位
:
最高位 = 0:即
x在补码编码下为非负整数,则可以直接转化为 无符号数编码的x
因为
无符号数编码的非负整数的范围 > 补码编码的非负整数的范围
,所以当前的非负数必定可以被装下
最高位 = 1:即
x的补码编码下为负数
,则在补码编码的表示下,最高位权重为
, 在无符号数的编码表示下,最高位的权重为
。 因此,
综上,我们得出结论:
该结论表明,当
有符号数
(即用补码编码
)被映射到无符号数
(即用无符号正数编码
)时,负数
会被转化为大的正数
,而非负数
保持不变。
U2T
Unsigned Integer
和Two's Complement
的区别就在于位模式的最高位
,而除了最高的其他w-1位所表示的权重是一样的
因此,我们仍然需要从位模式的最高位 的取值情况 来考虑
:
:在这种情况下, 无符号数编码
和补码编码
所表示的含义就是一样的了。:对于 位模式的最高位为1
的情况。
我们可以得出结论:
与
有符号数
和无符号数
转换相关的结论:
综上,Q.E.D
Extend Bit Mode
当在不同字长的证整数
之间进行转换
,同时又想保持数值不变
时。
显然,我们只可能从较小的数据类型 -> 较大的数据类型
Methods
Zero Extension
Sign Extension
在需要将补码数字
转化为一个更大的数据类型
且保持数值不变
时,可使用符号拓展
。
也就是说:我们可以将
较小的补码数字表示
拓展到较大的补码数字表示
并且保持数值不变
由于的部分在补码编码下的拓展前后的前后的权重 相等
。
故接下来我们只需要证明,我们为
拓展的位的权重的累加 = 0
。
但为了证明的简单,我们使用归纳法
:仅证明符号拓展了1位的补码编码的数值 不会发生改变
,进而得出对补码编码符号拓展任意多位,数值也不会改变
分类讨论
:显然成立 :
Q.E.D
蓝色部分:先考虑从
和 的 ,当 位数拓展1位后,拓展前后的第w-1位的含义就不同了
红色部分:这部分是多出来的,可以直接相加即可。
第w位的值
为,权重为
另一种观点是:
即
加上一个权为-2^w的位
=将一个权为-2^{w-1}的位 转换为 权为2^{w-1}
PROOF
- 如果权重前的系数=0,则显然成立
- 如果权重前的系数≠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)
:对于
- 当x = 0时,
加法逆元
即为0
- 当x > 0时,
考虑
,有 且 。故 是 下的 加法逆元
Tow’s Complement Addition
上述式子告诉我们,
补码加法
和无符号加法
之间有完全相同的位级表示
。所以,对于
运算:可以先将参数转化为 无符号数
,执行无符号加法
,然后再将结果转化为补码
:
Overflow Detection for Two’s Complement Addition
Two’s Complement for Non
Q.E.D
Unsigned Multiplication
Two’s Multiplication
对于w位的补码数字
。
但
对于C语言的有符号数乘法,是通过将2w位的乘积 截断为 w位
来实现的。
无符号数乘法
和补法乘法
在位级表示
具有等价性