深入理解计算机系统(2.4)------整数的表示(无符号编码和补码编码)

  上一篇博客我们主要介绍了布尔代数和C语言当中的几个运算符。那么这一篇博客我们主要介绍在计算机中整数是如何表示的,诸如我们在编码过程中遇到的对数据类型进行强制转换可能会得到意想不到的结果在这篇博客里你会得到解答。

1、什么是整数?

  整数包含正整数,0,负整数。我们从小的数学常识,整数是无穷无尽的,即整数的大小没有限制。

  但是在计算机中则不能这样理解,因为计算机是靠数字信号来表示数,计算机所能处理的整数的长度是由计算机的字长来决定的,所以,在计算机中,我们必须制定一个规则来表示整数。

2、C 语言中的整型数据类型

  C 语言是支持多种整型数据类型的,下面我们看一下在 32 位机器和 64 位机器中,C 语言整型数据类型的取值范围。

   我们可以看到 :

  ①、C 语言数据类型是可以用来指定大小,同时还可以指示表示的数是非负数(声明为 unsigned),或者负数(默认)。

  ②、数据类型分配的字节数会根据机器的字长和编译器有所不同,不同的大小所表示的范围是不同的。上图唯一一个与机器有关的取值范围是 long 类型的,64位机器使用8个字节(264),而32位机器使用4个字节(232)。

  ③、负数的范围要比正数的范围大1。这是为什么呢,请接着往下面看。

  下面我们看一下 C 语言标准所定义的每种数据类型所能表示的最小的取值范围。

  C 语言标准我们可以从上图得到:

  ①、正数和负数的取值范围是对称的。

  ②、int 数据类型可以用 2 个字节来实现。(216)

  ③、long 数据类型用4 个字节来实现。(232)

3、无符号数的编码

     无符号数,在C语言中,即用 unsigned 声明的整数。

  定义:假设对于一个w位的无符号整数,用二进制比特位可以表示为[xw-1 , xw-2 , … , x2 , x1 , x0]。那么我们可以用一个函数表示如下:

  这个函数可以举几个简单的例子来看:

  那么很显然,对于一个无符号编码的数,由 w 位的二进制序列构成,那么它的最小值,即所有位都为 0 ,用位向量表示即:【000......000】。

UMinw = 0

  最大值即所有位都为 1,用位向量表示即:【111......111】

UMaxw = 1 * (1-2w) / 1 - 2 = 2w - 1

   我们可以得出一个结论:无符号的二进制,对于任意一个w位的二进制序列,都存在唯一一个整数介于0 到 2w-1之间,与这个二进制序列对应。反过来,在0 到 2w-1之间的每一个整数,存在唯一的二进制序列与其对应。

4、补码编码 

  上面我们讲解了正整数的编码,那么在实际应用中,是存在负数的。而在计算机中,最常见的表示有符号的数就是补码。补码的定义如下:

  其中最高有效位 xw-1 也称为符号位,符号位为 1 时表示负数,当设置为 0 时,表示非负数。下面我们看几个例子:

   那么我们可以得出:当最高位为1,其余为全部是 0 的时候,即【1000......000】,表示补码格式的最小值:

TMinw = -2w-1

当最高位为 0,其余为全部是 1 时,即【0111......111】,表示补码格式的最大值:

TMaxw = 1 * (1 - 2w-1) / 1 - 2 = 2w-1-1

   通过上面的两个公式,我们就很好理解为什么上面C语言数据类型负数的范围要比正数的范围大1。

  和上面无符号编码一样,我们对于补码格式编码也可以得到一个结论:

对于任意一个w位的二进制序列,都存在唯一一个介于-2w-1 到 2w-1-1的整数,与这个二进制序列对应。反过来,对于任意介于-2w-1 到 2w-1-1的整数,存在唯一的长度为w二进制序列与其对应。

   那么你就应该明白了为什么十进制 -1,在计算机中二进制表示为 1111 1111,而不是1000 0001,因为计算机是以补码的形式表示的。

 5、反码和原码

  反码定义:除了最高有效位的权是-2w-1-1,而不是-2w-1其余的和补码表示方式一样

  原码定义:最高有效位是符号位,用来确定剩下的位是正还是负

  我们可以和补码的定义进行对比:

  原码:一个整数,按照绝对值大小转换为二进制数,最高位为符号位。

  反码:将原码除最高位(符号位)外,其余各位按位取反,所得到的二进制码。正数的反码为原码。

  补码:反码最低位加1即为补码。

  对于正整数,原码、反码、补码完全一样,即符号位固定为0,数值位相同。

  对于负整数,原码和补码互相转换的简便方法:从数的右边往左开始数,遇到“0”不理它,直到遇到第一个“1”为止,以后的每一位数取反即是它的原码或补码,符号位不变,还是“1”(补码的补码是原码)。

  比如:11010100 ----- 从右往左数,第一位是0,不理它,第二位还是0不理它,第三位是1,那么从此以后的每位取反,即为它的补码了.答案为:10101100

  事实上,程序员如果希望代码具有最大的可移植性,能够在所有可能的机器上运行,就应该用补码的形式来表示有符号整数。虽然过去生产过基于反码表示的机器,但是几乎所有的现代机器都是使用补码。

  注意:浮点数有使用原码编码。

  关于整型数据类型的表示和取值范围,Java标准是非常明确的,它要求采用补码形式,取值范围和C语言在64位机器中的情况一样。在Java中,单字节数据类型称为 byte,而不是char,而且没有long long 数据类型。这些具体的要求都是为了保证无论在什么机器上,Java程序运行的表现都能完全一样。

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

  在 信息的存储和表示 这篇博客中我们讲过计算机在解释一个数据类型的值时主要有四个因素:位排列规则(大端或者小端)、起始位置、数据类型的字节数、数据类型的解释方式。对于特定的系统来说,前两种因素都是特定的,而对于后两种因素的改变,则可以改变一个数据类型的值的最终计算结果,这就是强制类型转换

  那么考虑相同整数类型的无符号编码和补码编码,数据类型的大小是没有任何变化的,变化的就是它们的解释方式。比如1000这个二进制序列,如果用无符号编码解释的话就是表示8,而若采用补码编码解释的话,则是表示-8。

①、有符号数强转为无符号数

  前面我们说过:无论是无符号编码还是补码编码,其映射方式都是双射,因此它们都一定存在逆映射。如果我们定义U2Bw(x)为B2Uw(x)的逆映射,则对于任意一个整数x,如果0 =< x < 2w,经过U2Bw(x)的计算之后,将得到唯一一个二进制序列。同样的,如果我们定义T2Bw(x)为B2Tw(x)的逆映射,则对于任意一个整数x,如果-2w-1 =< x < 2w-1,经过T2Bw(x)的计算之后,也将得到唯一一个二进制序列。

  可以很明显的看出,对于0到2w-1-1这个区间内的整数来说,两种编码得到的二进制序列是一样的。为了得到其它区间里的整数的映射关系,我们定义:

T2Uw(x) = B2Uw(T2Bw(x))

这个函数代表的含义是补码编码转换为无符号编码的时候,先将补码编码转换为二进制序列,再将二进制序列转换为无符号编码,最终也就是补码编码转为无符号编码的计算。

下面我们简单的推算一下上面的定义,究竟是如何转换的,也就是有符号数 x 和与之对应的无符号数T2Uw(x) 的关系。我们将上面无符号编码和补码编码的公式相减,

  将0到w-2的位的加权和互相抵消),即                             B2Uw(x) - B2Tw(x) = xw-12w-1 - (-xw-12w-1) = xw-12w

  将等式左边的B2Tw(x)移到等式右边,即                                           B2Uw(x) = xw-12w + B2Tw(x)

  此处我们令x为T2Bw(x),则          B2Uw(T2Bw(x)) = xw-12w + B2Tw(T2Bw(x)) = xw-12w + x

  即                                            T2Uw(x) = xw-12w + x

  此时考虑xw-1的情况,当xw-1为1时,也就是补码编码表示负数的时候,T2Uw(x)则为2w + x 。(此时x为负数,也就是说2w + x < 2w)

  若xw-1为0时,则补码编码为正数,此时T2Uw(x) = x 。

  综上可知,有下列式子成立

  从这个式子中可以很明显的看出,最终得到的无符号数范围为0 =< x < 2w。

  下图为表示补码编码与无符号编码的对应关系,可以看出在0至2w-1-1之间,两者是相等的,而其余区间则不同。

   从上图我们也可以得出:当将一个有符号数映射为它相应的无符号数时,负数就被转换成了大的正数;而非负数会保持不变。

   这里我们看一个小例子来理解一下:

#include <stdio.h>

int main()
{
	char t = 0xFF;
	unsigned char u = (unsigned char)t;
	//%d把对应的整数按有符号十进制输出,%u把对应的整数按无符号十进制输出
	printf("t=%d,t2u=%u\n",t,u);
	return 0;//c标准规定建议main函数返回值为int 
}

  输出结果为:

   这个结果怎么解释呢,首先有符号char t=0xFFFF。这是因为C语言在64位系统中占用一个字节,转换成二进制数即:1111 1111,转换为补码也是:1111 1111,我们套用下面补码的公式可以得到:

  1111 1111的值为 -1。然后根据我们上面的转换公式:

  可以得到转换之后的值为 -1+28=255。也就是上面打印的结果。

②、无符号数转换为有符号数

  相反,我们用同样的方式也可以证明从无符号编码到补码编码的公式,我们依然将无符号编码和补码编码的公式相减

             即                              B2Uw(u) - B2Tw(u) = uw-12w-1 - (-uw-12w-1) = uw-12w

             即                                           B2Tw(u) = B2Uw(u) - uw-12w

             此时我们令u为U2Bw(u),则    B2Tw(U2Bw(u)) = B2Uw(U2Bw(u)) - uw-12w = u - uw-12w

             即                                           U2Tw(u) = u - uw-12w

             此时考虑uw-1的情况,当uw-1为0时,也就是无符号编码数值小于2w-1的时候,U2Tw(u)则为u 。

             若uw-1为1时,也就是无符号编码数值大于或等于2w-1的时候,此时U2Tw(u)= u - 2w。(此时U2Tw(u)为负数,因为 u < 2w)

             综上,我们可以得到无符号编码转换为补码编码的公式

  同样的,在0至2w-1-1之间,两者依然是相等的,而其余区间则不同。

  还是看一下下面的例子来理解:

#include <stdio.h>

int main()
{
	unsigned char u = 0xFF;
	char t = (char)u;
	//%d把对应的整数按有符号十进制输出,%u把对应的整数按无符号十进制输出
	printf("u=%u,u2t=%d\n",u,t);
	return 0;//c标准规定建议main函数返回值为int 
}

  输出结果:

   这应该很好理解了,无符号 0xFF,即1111 1111,采用的是无符号编码,第一位不是符号位,那么转换为十进制就是255,然后套用上面的公式:u-2w=255-28=-1

7、总结

  本篇博客主要讲解了有符号数和无符号数之间的转换,我们需要明白它的原理,这篇博客也涉及到很多公式推导证明,LZ也是看了好几遍才理解这些,大家如果第一遍看不懂也没关系,多看几遍,然后多用笔推导推导,还是不难理解的。下一章会介绍C语言中的有符号数和无符号数以及扩展和截断数字。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序猿DD

第二章 正则表达式位置匹配攻略

第二章 正则表达式位置匹配攻略 正则表达式是匹配模式,要么匹配字符,要么匹配位置。请记住这句话。 然而大部分人学习正则时,对于匹配位置的重视程度没有那么高。 本...

18110
来自专栏人工智能LeadAI

为什么算法容易忘记之插入排序

在学习常用的排序算法时,常有这样的感觉,一看就懂,过眼就忘。原因在于没有将排序的基本思想与代码中各个循环控制变量的意义联系起来进行理解记忆。 插入排序 首先,我...

3395
来自专栏坚毅的PHP

python的数学函数(1)-python组合函数模块itertools

要解决的问题: 输出n个 ['A','T','C','G'] 所有的排列组合。 比如n=2 时,输出为 AA,AT,AC,AG,TA,TT,TC,TG,……...

3654
来自专栏大数据挖掘DT机器学习

Python爬虫(urllib2+bs4)数据采集:分析找出百度贴吧谁是水贴王

问题描述 ? 对于这个题目, 书上给出了三种思路 第一种 : 先遍历一次所有的帖子, 统计出 <发帖人, 发帖次数>, 然后在遍历一次映射, 找出发帖次数超...

3195
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

741
来自专栏用户画像

C语言测试题

2. 假设已指定i为整型变量,f为float变量,d为double型变量,e为long型,有下面式子:

605
来自专栏猿人谷

字符串反转问题

首先是我之前写的程序,同时这也是处理第一类的字符串反转问题,也就是输入This is a string., 输出为.gnirts a si sihT: #inc...

1697
来自专栏数据小魔方

求和函数系列——sum函数家族

今天要跟大家分享的是一组求和函数系列——sum函数家族! excel中最长用到的求和函数就是sum函数系列了,sum函数系列一共有三组函数: sum sumif...

2624
来自专栏海天一树

字符串匹配:KMP算法

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特—莫里斯—普拉特算法。KMP算...

30310
来自专栏无所事事者爱嘲笑

js float运算精度问题

1295

扫码关注云+社区