【计算机系统导论】2.4 整型与基本运算


  • 整数表示(符号-幅值表示法、2的补码表示法、不同位长之间的转换、定点表示法)
  • 整数算术(取负、加法和减法、乘法、除法)

2.4.1 比特心生

研究问题有两种方法,一种是自顶向下,另一种是自底向上。对于设计来说,很多时候是自顶向下的,从一个整体想法出发,然后慢慢细化;而在学习化学的时候,往往是自底向上的,比方说先去了解组成元素的基本粒子,然后在这些粒子的基础上进行更加抽象的研究。从这个角度看,学习计算机系统,自底向上可能是一个好的方向。

在计算机中,我们看到的一切,归根到底,都是比特,每个比特不是 0 就是 1。计算机就是通过对比特进行不同方式的编码和描述,来完成执行不同的任务。那么问题来了,为什么是比特而不是其他呢?这就要从模拟电路讲起,一言以蔽之就是,比特这种描述方式很好存储,并且在有噪声或者传输不那么准确的情况下,也能保持比较高的可靠度(电压值有一定的容错范围)。

在这样的物理基础上,计算机就是一个二进制系统,我们通过下面这个表格来把二进制、十进制和十六进制一一对应起来,这三种数字表示形式在今后的学习过程中会反复出现,可以把这个表格当做九九乘法表来看:

十六进制 十进制 二进制 十六进制 十进制 二进制
0 0 0000 8 8 1000
1 1 0001 9 9 1001
2 2 0010 A 10 1010
3 3 0011 B 11 1011
4 4 0100 C 12 1100
5 5 0101 D 13 1101
6 6 0110 E 14 1110
7 7 0111 F 15 1111

正如加减乘除,关于比特的基本逻辑运算也有四种,可以看做是布尔代数[8]的子集。对于 0 和 1 来说,是这样的:

  • 与 And:A=1B=1 时,A&B = 1
  • 或 Or:A=1B=1 时,A|B = 1
  • 非 Not:A=1 时,~A=0A=0 时,~A=1
  • 异或 Exclusive-Or(Xor):A=1B=1 时,A^B = 1A=1B=1 时,A^B = 0

对应与集合运算则是交集、并集、差集和补集,假设集合 A 是 {0, 3, 5, 6},集合 B 是 {0, 2, 4, 6},全集为 {0, 1, 2, 3, 4, 5, 6, 7}那么:

  • & 交集 Intersection {0, 6}
  • | 并集 Union {0, 2, 3, 4, 5, 6}
  • ^ 差集 Symmetric difference {2, 3, 4, 5}
  • ~ 补集 Complement {1, 3, 5, 7}

有了这些知识,我们就可以来具体看看不同类型的数据在计算机中是如何存储和进行运算的了。

2.4.2 整型 Integer

C 语言之所以效率高,很大程度上是因为抽象程度较低,很多关键字和计算机系统中的概念是一一对应的。比方说 signedunsigned,就表示有符号数和无符号数。假设字长(word size)为 w,那么二进制向十进制的转换分别是:

  • 无符号数:$B2U(X)=\sum_{i=0}^{w-1}x_i·2^i$
  • 有符号数: $B2T(X)=-x_{w-1}·2^{w-1}+\sum_{i=0}^{w-2}x_i·2^i$

有符号数和无符号数的区别主要在于有没有最高位的符号位,以及由此带来的计算方式的不同。符号位中,0 表示非负数,1 表示负数。具体的表示方法如下

十进制 十六进制 二进制
15213 3B 6D 00111011 01101101
-15213 C4 93 11000100 10010011

对于二进制数字来说,还有两种常用操作:左移和右移。左移比较简单,在右边补 0 即可。右移的话有两种类型,一种是逻辑右移(左边补 0),另一种是算术右移(左边补符号位)。为什么会有这两种,因为对应无符号数和有符号数的运算,有符号数的最高位(最左边)是符号位在负数的时候需要进行算术右移

整型表示的特点

接下来我们看看这种表示形式的特点,以及溢出的集中情况,假设字长为 w,定义如下的常量:

  • UMin = 0 即 000…0
  • UMax = $2^w-1$ 即 111…1
  • TMin = $-2^{w-1}$ 即 100…0
  • TMax = $2^{w-1}-1$ 即 011…1
  • Minus 1 即 111…1

这里的 U 表示无符号数,T 表示补码(Two’s Complement),对于字长为 16 的情况来说,我们有:

\ Decimal Hex Binary
UMax 65535 FF FF 11111111 11111111
TMax 32767 7F FF 01111111 11111111
TMin -32768 80 00 10000000 00000000
-1 -1 FF FF 11111111 11111111
0 0 00 00 00000000 00000000

对于不同的 word size,数值也会有很大的变化

w 8 16 32 64
UMax 255 65,535 4,294,967,295 18,446,744,073,709,551,615
TMax 127 32,767 2,147,483,647 9,223,372,036,854,775,807
TMin -128 -32,768 -2,147,483,648 -9223,372,036,854,775,808

观察可以得知两个很重要的特性

  • |TMin| = TMax + 1 (范围并不是对称的)
  • UMax = 2*TMax + 1

有符号数和无符号数在非负数的编码是一样的,每一个数字的编码是唯一的,这两者可以互换:

  • $U2B(x)=B2U^{-1}(x)$
  • $T2B(x)=B2T^{-1}(x)$

类型转换

我们在数轴上把有符号数和无符号数画出来的话,就能很清晰的看出相对的关系:

在 C 语言中,如果不加关键字限制,默认的整型是有符号的。如果想要无符号数的话,需要在数字后面加 U,例如下面的代码段

int a_signed_number = -15213;
unsigned int a_unsigned_number = 15213U;

在进行有符号和无符号数的互相转换时:

  • 具体每一个字节的值不会改变,改变的是计算机解释当前值的方式
  • 如果一个表达式既包含有符号数也包含无符号数,那么会被隐式转换成无符号数进行比较

下面用字长 w = 32 为例,来进行说明,注意这里的每个表达式都是成立的,其中 TMin = -2,147,483,648, TMax = 2,147,483,647

表达式 比较对象
0 == 0U 无符号数
-1 < 0 有符号数
-1 > 0U 无符号数
2147483647 > (-2147483647-1) 有符号数
2147483647U < (-2147483647-1) 无符号数
-1 > -2 有符号数
(unsigned)-1 > -2 无符号数
2147483647 < 2147483648U 无符号数
2147483647 > (int)2147483648U 有符号数

类型扩展与截取

具体需要分情况讨论,如:

  • 扩展(例如从 short intint),都可以得到预期的结果
    • 无符号数:加 0
    • 有符号数:加符号位
  • 截取(例如 unsignedunsigned short),对于小的数字可以得到预期的结果
    • 无符号数:mod 操作
    • 有符号数:近似 mod 操作

举个例子

short int x = 15213;
int ix = (int) x;
short int y = -15213;
int iy = (int) y;

C 语言会自动做符号拓展,把小的数据类型转换成大的,如下表所示

十进制 十六进制 二进制
x=15213 3B 6D 00111011 01101101
ix=15213 00 00 3B 6D 00000000 00000000 00111011 01101101
y=-15213 C4 93 11000100 10010011
iy=-15213 FF FF C4 93 11111111 11111111 11000100 10010011

2.4.3 整型运算与溢出

无论是无符号数还是有符号数,一旦用来表示数值的最高位发生了进位,超出了表达形式或者改变了符号位,就会发生溢出。

对于无符号数加法,如果两个 w 位的数字相加,结果是 w+1 位的话,那么就会丢弃掉最高位,实际上是做了一个 mod 操作(公式为 $s=UAdd_w(u,v)=u+v \; mod \; 2^w$)

假设 w=3,那么能够表达的数字范围是 000~111(0~7)(括号内为二进制对应的十进制数值,后同),那么如果一个表达式是 110+111(6+7),原本应该等于 1101(13),但是由于 w=3,所以最终的结果是 101(5),也就是发生了溢出,两个无符号数相加,有可能反而变『小』。

对于有符号的加法(Two’s Complement Addition),操作过程和无符号加法一样,只是解释的时候会有不同,因此会得到正溢出(positive overflow)和负溢出(negative overflow)两种。正溢出就是数值太大把原来为 0 的符号位修改成了 1,反而成了负数;负溢出是数值太小,把原来为 1 的符号位修改成了 0,反而成了正数。

还是用刚才 w=3 作为例子,能够表达的数字范围是 100~011(-4~3),如果一个表达式是 011+010(3+2),理论上应该等于 5,但是相加之后变成了 101(-3),也就是发生了正溢出。如果一个表达式是 100+101(-4+(-3)),理论上应该等于 -7,但是相加后进位截取变成了 001(1),也就是发生了负溢出。

对于乘法来说,值的范围会大很多,这里分情况讨论一下,假设两个乘数是 x,y 并且都是 w 位的:

  • 无符号数:至多 2w 位
    • 范围 $0 \le x \times y \le (2^w-1)^2 = 2^{2w}-2^{w+1}+1$
  • 有符号数,最小的负数:至多 2w - 1 位
    • 范围 $x \times y \ge (-2^{w-1})\times(2^{w-1}-1)=-2^{2w-2}+2^{w-1}$
  • 有符号数,最大的正数:至多 2w 位,只有 $(TMin_w)^2$ 一种情况
    • 范围 $x \times y \le (-2^{w-1})^2=2^{2w-2}$

如果需要保证精度,就需要用软件来实现了。另外,计算的无符号乘法的时候,会忽略最高的 w 位,相当于 $UMult_w(u,v)=u·v\;mod\;2^w$

2.4.4 数据在内存中的形式

后续章节会有关于内存的详细介绍,这里我们只要知道不同数据类型所占据的字节数,以及大端-小端规则即可。

操作系统会给每个进程提供私有的虚拟内存地址空间,一个进程可以访问自己的数据,但是不能访问别人的数据。在虚拟内存中地址是连续的,对应物理内存则不一定,根据字长的不同,有不同的间隔,如下图所示

然后我们来看看常见数据类型所需要的字节数:

数据类型 32 位 64 位 x86-64
char 1 1 1
short 2 2 2
int 4 4 4
long 4 8 8
float 4 4 4
double 8 8 8
long double - - 10/16
指针 4 8 8

数据具体的排列也有两种方式:大端(Big Endian)与小端(Little Endian),区别在于高位地址的位置。Internet 数据采用大端规则,而我们常见的 x86 或 ARM 处理器都采用小端规则。

举个例子,假如变量 x 是 4 字节,值为 0x01234567。用 &x 索引的地址是 0x100,那么大端和小端的表示形式是

如何检查数据的表示呢,可以用下面的代码

typedef unsigned char *pointer;
void show_bytes(pointer start, size_t len) {
size_t i;
for (i = 0; i < len; i++)
printf("%p\t0x%.2x\n", start+i, start[i]);
printf("\n");
}

这里 %p 用来输出指针,%x 用来输出 16 进制数据。执行可用:

int a = 15213;
printf("int a = 15213;\n");
show_bytes((pointer) &a, sizeof(int));

在我的电脑上,测试如下:

csapp12

捧个钱场?