欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 明星 > csapp笔记——2.2节整数表示

csapp笔记——2.2节整数表示

2025/2/24 11:07:32 来源:https://blog.csdn.net/roboko_/article/details/145248316  浏览:    关键词:csapp笔记——2.2节整数表示

这节很有意思的点在于将整数的编码用数学的语言描述,这样从数学角度思考能更好的理解补码的作用,补码的一些好用的性质,也更加严谨。

C语言整型范围

C语言标准定义了每个类型至少需要表示的范围

实际机器上的范围只能更大不能更小。

无符号数的编码

设某整数二进制有w位,则称向量\vec{x} = ^{[x_{w-1},...,x_{1},x_{0}]}为位向量。现在用\vec{x}来进行编码。

定义函数^{B2U_{w}( \vec{x} )=\sum_{i=0}^{w-1}x_{i}2^{i}}(B2U是Binary to Unsigned的缩写,长度为w),这个函数可将任意一个位向量映射到一个非负整数,如

B2U_{4}([1100])=0\cdot 2^{0}+0\cdot 2^{1}+1\cdot 2^{2}+1\cdot 2^{3}=12

B2U_{w}(\vec{x})的反函数是U2B_{w},将某个非负整数映射都对应的位向量。

至此,位向量和非负数可一一对应起来,这个唯一对应的位向量就是这个非负数的编码。

补码

B2T_{w}(Binary to Two's-complement的缩写,长度为w)定义补码。

B2T_{w}(\vec{x})=-x_{w-1}\cdot 2^{w-1} + \sum_{i=0}^{w-2}x_{i}\cdot 2^{i}

与之前唯一的不同在于最高位的权重变为了-2^{w-1},由此得到补码编码。

从定义式可以看出,最高位为1时表示的数一定是负数(因为除最高位外求和最大为2^{w-1}-1),为0时一定是负数,这也是补码最高位被叫做符号位的原因。

例子 : B2T_{4}([1111]) = -1

同理,定义T2B_{w}为反函数。

接下来讨论32位有符号整数的范围。

根据B2T表达式可以看出最小值是只有最高位为1的情况,最大值是最高位为0,其余为1的情况。

由此得到取值范围

图中看出\left | TMin \right | = \left | TMax \right | + 1,这是由于非负数包含了0,而一半的位模式(最高位为1)表示负数,另一半表示非负数。

到这里可以明白,补码本身是可以跟原码,反码不产生任何关系的,只是作为一种独立的编码方式而已,而我们熟知的原码转补码的方法(取反后加一)这并不是补码的定义,只能作为一种计算方法。

这里贴出原码和反码的定义

这两种方式有一个奇怪的特性,对于0有+0和-0两种编码结果。

对原码和反码来说,+0都是[00...0],对于原码,-0表示为[100...000],对于反码,-0表示为[111...111]。

再介绍反码和补码名字的来源

对于非负数x,用2^{w}-x作为-x的w位表示,由此得名补码。用[111...1]-x来表示-x,得名反码。

有符号数和无符号数之间的转换

C语言有时会发生类型转换,要记住,对于大多的C语言实现来说,转换不会改变位向量,也就是说存在内存中的01序列本身不会改变,只是改变了解释这个位向量的方式。

下面主要用数学化的形式来描述二者相互转换的规则。

有符号数转无符号数

定义T2U_{w}(x) = B2U_{w}(T2B_{w}(x)),x为w位补码表示范围内的数。

x范围[TMin_{w}, TMax_{w}],内层函数结果为x的补码表示,将这个补码的位向量作为外层函数的输入,最终得到x类型转化后的无符号数,这个无符号数范围为[0,UMax_{w}]

根据前面给出的B2U函数和T2B函数定义式

^{B2U_{w}( \vec{x} )=\sum_{i=0}^{w-1}x_{i}2^{i}}

B2T_{w}(\vec{x})=-x_{w-1}\cdot 2^{w-1} + \sum_{i=0}^{w-2}x_{i}\cdot 2^{i}

两式相减得

B2U_{w}(\vec{x})-B2T_{w}(\vec{x})=x_{w-1}\cdot 2^{w}

 B2U_{w}(\vec{x})=B2T_{w}(\vec{x})+x_{w-1}\cdot 2^{w}

代入T2U定义式

T2U_{w}(x)=B2T_{w}(T2B_{w}(x)) + x_{w-1}\cdot 2^{w}=x+x_{w-1}\cdot 2^{w}

故负数转无符号数会加上2^{w},正数不变。

无符号数转补码

定义U2T_{w}(u)=B2T_{w}(U2B_{w}(u)),u范围[0,UMax_{w}]

U2T_{w}(u)范围[TMin_{w}, TMax_{w}]

由有符号数转无符号数的推导过程

B2T_{w}(\vec{x})=B2U_{w}(\vec{x})-x_{w-1}\cdot 2^{w}

代入U2T定义式

U2T_{w}(u)=B2T_{w}(U2B_{w}(u))-u_{w-1}\cdot 2^{w}=u-u_{w-1}\cdot 2^{w}

也就是说u的最高位若为0,则补码相同,为1则需要减去2^{w}

C语言中的有符号数和无符号数

C语言中默认数字是有符号的

int c = 1;//c是有符号数

 加上后缀字符‘U’或‘u’即可创建无符号数。

如12345u

当有符号数赋值给无符号数或无符号数赋值给有符号数时就会发生隐式类型转换。

C语言中在执行一个运算时,若有无符号数,会隐式地将有符号数转为无符号数。

扩展数字位

无符号数拓展直接最高位补0,补码拓展补符号位。

截断数字

对于位向量\vec{x}=[x_{w-1},x_{w-2},...,x_{0}],将其截断为k位时,高w-k被舍弃,得到新的位向量\vec{x}{}'=[x_{k-1},x_{k-2},...,x_{0}]

无符号数的截断

x=B2U_{w}(\vec{x})x'=B2U_{w}(\vec{x}'),则x'=x mod 2^{k}

补码截断

x=B2U_w(\vec{x})x'=B2T_w(\vec{x}'),则x'=U2T_k(xmod2^k)

\vec{x}视作无符号数解析出x,将x作为无符号数截断后得到阶段后的无符号数,把新得到的无符号数转换成有符号数,最终得到截断结果。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词