• 现代计算机存储和处理以二值信号表示的信息。这些普通的二进制数字,或者位(bit),形成了数字革命的基础。大家熟悉地使用了1000多年的十进制(以10为基数,base-10)起源于印度,在12世纪被阿拉伯数学家所改进,并在13世纪被意大利数学家Leonardo Pisano(更有名的叫法是Fibonacci)带到西方。使用十进制表示法对于有十个手指头的人类来说是很自然的事情,但是当构造存储和处理信息的机器时,二进制值工作得更好。二值信号能够很容易地表示、存储和传输,例如,可以表示为穿孔卡片上有洞或无洞、导线上的高电压或低电压,或者磁场引起的顺时针或逆时针。基于二值信号的存储和执行计算的电子电路非常简单和可靠,使得制造商能够在一个单独的硅片上集成百万个这样的电路;
  • 单独地来说,单个的位不是非常有用。然而,当我们把位组合在一起,再加上某种解释(interpretation),即给予不同的可能位模式以含义,我们就能够表示任何有限集合的元素。比如,使用一个二进制数字系统,我们能够用位组来编码非负数。通过使用标准的字符码,我们能够对一份文档中的字母和符号进行编码;
  • 我们考虑三中最重要的数字编码。无符号(unsigned)编码是基于传统的二进制表示法的,表示大于或等于零的数字。二进制编码(two’s-complement)编码是表示有符号整数的最常见的方式,有符号整数就是为正或者为负的数字。浮点数(floating-point)编码是表示实数的科学计数法的以二为基数的版本。计算机用这些不同的表示方法实现算术运算,例如加法和乘法,类似于相应的整数和实数运算;
  • 计算机的表示法用有限的位数来对一个数字编码,因此,当结果太大以至不能表示时,某些运算就会溢出(overflow)。这会导致某些令人吃惊的后果。例如,在大多数今天的计算机上,计算表达式200×300×400×500会得出-884,901,888。这违背了整数运算的属性——计算一组正数的乘积产生了一个为负的结果;
  • 另一方面,整数的计算机运算满足了真正整数运算的许多普通的属性。例如,乘法是可结合的和可交换的,这样一来计算下面任何一个C表达式,都会得出884,901,888
    • (500×400)×(300×200)
    • ((500×400)×300)×200
    • ((200×500)×300)×400
    • 400×(200×(300×500))
    • 计算机可能没有产生这个预期的结果,但至少它是一致的!
  • 浮点运算有完全不同的数学属性。但是溢出会产生特殊的值+∞,但是一组正数的乘积总是正的。另一方面,由于表示的精度有限,浮点运算时不可结合的。例如,在大多数机器上,C表达式(3.14+1e20)-1e20求得的值会是0.0,而3.14+(1e20-1e20)求得的值会是3.14;
  • 通过研究实际数字的表示,我们能够了解可以表示的值得范围和不同运算的属性。对于编写在全部数值范围内都能正常工作,而且可以跨越不同机器、操作系统和编译器组合的可移植的程序来说,这种了解是非常重要的;
  • 计算机用几种不同的二进制表示来编码数值;
  • 通过直接操作位级的数字表示,我们得到了几种进行算术运算的方式。理解这些技术对于理解编译算术表达式时产生的机器级代码是很重要的;
  • 对这些内容的处理是非常精确的。我们从编码的基本定义开始,然后得出一些属性,例如可表示的数字的范围、它们的位级表示以及算术运算的属性。从这样一个抽象的观点来分析这些内容是很重要的,因为程序员需要对计算机运算和更为人熟悉的整数和实数运算之间的关系有牢固的理解。尽管这看起来很吓人,但精确的处理只需要了解基本的代数知识;
  • C编程语言建立在C之上,使用完全相同的数字表示和运算。以下关于C的所有内容对C都有效。另一方面,Java语言创造了一套新的数字表示和运算标准。C标准被设计为允许多种实现方式,而Java标准在数据的格式和编码上是详细而精确的。

信息存储

  • 大多数计算机使用8位的块,或叫做字节(byte),来作为最小的可寻址的存储器单位,而不是访问存储器中单独的位。机器级程序将存储器视为一个非常大的字节数组,称为虚拟存储器(virtual memory)。存储器的每个字节都由一个唯一的数字来标识,称为它的地址(address),所有可能地址的集合就称为虚拟地址空间(virtual address space)。正如它的名字表明的,这个虚拟地址空间只是一个展现给机器程序的概念性映像(image)。实际的实现使用的是随机访问存储器RAM、磁盘存储、特殊硬件和操作系统软件的结合,来为程序提供一个看上去统一的字节数组;
  • 编译器和运行时系统的一个任务就是将这个存储器空间划分为更可管理的单元,来存放不同的程序对象(program object),也就是,程序数据、指令和控制信息。有各种机制可以用来分配和管理程序不同部分的存储。这种管理完全是在虚拟地址空间里完成的。例如,C中一个指针的值(无论它指向一个整数、一个结构或是某个其他程序单元)都是某个存储块的第一个字节的虚拟地址。C编译器还把每个指针和类型信息联系起来,这样它就可以根据指针值的类型,生成不同的机器级代码来访问存储在指针所指向位置处的值。尽管C的编译器维护着这个类型信息,但是它1生成的实际机器级程序并没有关于数据类型的信息。它简单地把每个程序对象视为一个字节块,而程序本身看做一个字节序列;

给C语言初学者:C中指针的角色

指针是C的一个重要特性,它提供了引用数据结构的元素(包括数组)的机制。就像一个变量,指针也有两个方面:它的值和它的类型,它的值表示的是某个对象的位置,而它的类型表示那个位置上所存储对象的类型(比如,整数或者浮点数)。

十六进制表示法

  • 一个字节包括8位。在二进制表示法中,它的值域是00000000211111111<sub>2</sub>。如果看成十进制整数,它的值域就是0<sub>10</sub>25510。两种符号表示法对于描述位模式来说都不是非常方便。二进制表示法太冗长,而使用十进制表示法,与位模式的相互转化很麻烦。替代的方法是,我们以16为基数,或者叫做十六进制(hexadecimal)数,来书写位模式。十六进制(简写“Hex”)使用数字"0"“9”,以及字符“A”“F”来表示16个可能的值。下表展示了16个十六进制数字对应的十进制值和二进制值

    十六进制数字 0 1 2 3 4 5 6 7
    十进制值 0 1 2 3 4 5 6 7
    二进制值 0000 0001 0010 0011 0100 0101 0110 0111
    十六进制数字 8 9 A B C D E F
    十进制值 8 9 10 11 12 13 14 15
    二进制值 1000 1001 1010 1011 1100 1101 1110 1111
  • 在C中,以0x或0X开头的数字常量被认为是十六进制的值。字符“A”~“F”既可以是大写,也可以是小写。例如,我们可以将数字FA1D37B16写作0xFA1D37B或者0xfa1d37b,甚至是大小写混合,比如0xFa1D37b;

  • 编写机器级程序的一个常见任务就是手工地在位模式的十进制、二进制和十六进制表示之间转换。二进制和十六进制之间的转换是简单直接的,因为可以一次执行一个十六进制数字的转换。数字的转换可以参考上表。

  • 每台计算机都有一个字长(word size),指明整数和指针数据的标称大小(nominal size)。因为虚拟地址是以这样的字来编码的,所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。也就是说,对于一个字长为n位的机器而言,虚拟地址的范围为0~2n-1,程序最多访问2n字节;
  • 今天大多数计算机的字长都是32位。这就限制了虚拟地址空间为4千兆字节(写作4GB),也就是说,刚刚超过4×109字节。虽然对大多数应用而言,这个空间足够大了,但是现在已经有许多大型的科学和数据库应用需要更大的存储了。因此,随着存储器价格的降低,字长为64位的高端机器正逐渐变得普遍起来。

数据大小

  • 计算机和编译器使用不同的方式来编码数字,比如不同长度的整数和浮点数,从而支持多种数字格式。比如,许多机器都有处理单个字节的指令,也有处理表示为两字节、四字节或者八字节整数的指令,还有些指令表示为四字节和八字节的浮点数;

  • C语言支持整数和浮点数的多种数据格式。C的数据类型char表示一个单独的字节。尽管“char”这个名字是由于它被用来存储文本串中的单个字符这一事实而来的,但它也能被用来存储整数值。C的数据类型int之前还能加上限定词long和short,提供各种大小的整数表示。下表展示了为各种C数据类型分配的字节数

    C声明 典型的32位机器 Compaq Qlpha机器
    char 1 1
    short int 2 2
    int 4 4
    long int 4 8
    char * 4 8
    float 4 4
    double 8 8

    准确的字节数依赖于机器和编译器。我们展示了两个有代表性的例子:典型的32位机器和Compaq Alpha体系结构,其中Compaq Alpha是针对高端应用的64位机器,大多数32位机器使用“典型”的分配方式。可以观察到,“短”整数分配有两字节,而不加限制的int为四字节,“长”整数使用机器的全字长;

  • 上表也说明了指针(例如,一个被声明为类型为“char *”的变量)使用机器的全字长。大多数机器还支持两种不同的浮点格式:单精度(在C中声明为float)和双精度(在C中声明为double)。这些格式分别使用四字节和八字节;

  • 程序员应该力图使他们的程序在不同的机器和编译器上可移植。可移植性的一个方面就是使程序对不同数据类型的确切大小不敏感。C标准对不同数据类型的数字范围设置了下界,但是却没有上界。因为32位机器在过去20年里一直是标准,许多程序的编写都是以上表中“典型的32位机器”列出的分配原则为假设的。在不久的将来,随着64位机器越来越重要,在将这些程序移植到新机器上时,许多隐藏的对字长的依赖就会呈现出来,成为错误。比如,许多程序员假设一个声明为int类型的程序对象能被用来存储一个指针。这在大多数32位的机器上工作正常,但是在一台Alpha机器上却会导致问题。

寻址和字节顺序

  • 对于跨越多字节的程序对象,我们必须建立两个规则:这个对象的地址是什么和我们在存储器中如何对这些字节排序。在几乎所有的机器上,多字节对象都被存储为连续的字节序列,对象的地址为所使用字节序列中最小的地址。例如,假设一个类型为int的变量x的地址为0x100,也就是说,地址表达式&x的值为0x100.那么,x的四字节将被存储在存储器的0x100、0x101、0x102和0x103位置;

  • 对表示一个对象的字节序列排序,有两个通用的规则。考虑一个w位的整数,有位表示[xw-1,xw-2,…,x1,x0],其中xw-1是最高有效位,而x0是最低有效位。假设w是8的倍数,这些位就能被分组成为字节,其中最高有效字节包含位[xw-1,xw-2,…,xw-8],而最低有效字节包含位[x7,x6,…,x0],其他字节包含中间的位。某些机器选择在存储器中按照从最低有效字节到最高有效字节的顺序存储对象,而另一些机器则按照从最高有效字节到最低有效字节的顺序存储。前一种规则——最低有效字节在最前面的方式称为小端法(little endian)。大多数源自以前的Digital Equipment公司(现在是Compaq公司的一部分)的机器,以及Intel的机器都采用这种规则。后一种规则——最高有效字节在最前面的方式称为大端法(big endian)。IBM、Motorola和Sun Microsystem的大多数机器都采用这种规则。注意我们说的是“大多数”。这些规则并没有严格按照企业界限来划分。比如,IBM制造的个人计算机使用的是Intel兼容的处理器,因此就是小端法。许多微处理器芯片,包括Alpha和Motorola和PowerPC,能够运行在任一种模式中,其取决于芯片加电启动时确定的字节顺序规则;

  • 继续我们前面的示例,假设变量x类型为int,位于地址0x100处,有一个十六进制值为0x01234567.地址范围0x100~0x103的字节顺序依赖于机器的类型

    大端法

    0x100 0x101 0x102 0x103
    01 23 45 67

    小端法

    0x100 0x101 0x102 0x103
    67 45 23 01

    注意,在字0x01234567中,高位字节的十六进制值为0x01,而低位字节值为0x67;

  • 令人吃惊的是,在哪种字节顺序是合适的这个问题上,人们表现得非常情绪化。实际上,术语"little endian(小端)"和"big endian(大端)"来自于Jonathan Swift的《格利弗游记(Gulliver’s Travels)》,其中交战的两个派别无法就应该从哪一端——小端还是大端——打开一个半熟的鸡蛋达成一致。就像鸡蛋的问题一样,没有技术原因来选择字节顺序规则,因此争论退化成为关于社会政治论题的口角。对于哪种字节排序的选择是任意的;

  • 对于大多数应用程序员来说,他们机器的字节顺序是完全不可见的。无论为哪种类型的机器所编译的程序都会得到同样的结果。不过有时候,字节顺序会成为问题,首先是在不同类型的机器之间通过网络传送二进制数据时,一个常见的问题是当小端法机器产生的数据被发送到大端法机器或者反之时,接收程序会发现,字里的字节成了反序的。为了避免这类问题,网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则,以确保发送方机器将它的内部表示转换成网络标准,而接收方机器则将网络标准转换为它的内部表示;

  • 字节顺序变得重要的第二种情况是当阅读表示整数数据的字节序列时。这通常发生在检查机器级程序时。作为一个示例,从某个文件中摘出了下面这行代码,该文件给出了一个针对Intel处理器的机器级代码的文本表示

    1
    80483bd:01 05 64 94 04 08	add %eax,0x8049464

    这一行是由反汇编器(disassembler)生成的,反汇编器是一种确定可执行程序文件所表示的指令序列的工具。现在,我们只是注意这行表述了十六进制字节串01 05 64 94 04 08是一条指令的字节级表示,这条指令是增加一个字宽的数据到存储在主存地址0x8049464的值上,如果我们取出这个序列的最后四字节:64 94 04 08,并且按照相反的顺序写出,我们得到08 04 94 64,去掉开头的零,我们就得到值0x8049464,就是右边写着的数值。当阅读像此例中一样的小端法机器生成的机器级程序表示时,经尝会将字节按照相反的顺序显示。书写字节序列的自然方式是最低位字节在左边,而最高位字节在右边,但是这和书写数字时最高有效位在左边,最低有效位在右边的通常方式是相反的;

  • 字节顺序变得可见的第三种情况是当编写规避正常的类型系统的程序时。在C语言中,可以通过使用**强制类型转换(cast)**来允许以一种不同于它被创造时的数据类型来引用一个对象。大多数应用编程都强烈不推荐这种编码技巧,但是它们对系统级编程来说是非常有用,甚至是必须的;

  • 下面展示了一段C代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    #include <stdio.h>

    typedef unsigned char *byte_pointer;

    void show_bytes(byte_pointer start,int len)
    {
    int i;
    for(i=0;i<len;i++)
    printf("%.2x",start[i]);
    printf("\n");
    }

    void show_int(int x)
    {
    show_bytes((byte_pointer)&x,sizeof(int));
    }

    void show_float(float x)
    {
    show_bytes((byte_pointer)&x,sizeof(float));
    }

    void show_pointer(void *x)
    {
    show_bytes((byte_pointer)&x,sizeof(void *));
    }

    它使用强制类型转换来访问和打印不同程序对象的字节表示。

整数表示

整数运算

浮点

小结