02 2.1 信息存储.txt

2.1 信息存储
大多数计算机使用8位的块，或者字节（byte），作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存（virtual memory）。内存的每个字节都由一个唯一的数字来标识，称为它的地址（ad-dress），所有可能地址的集合就称为虚拟地址空间（virtual address space）。顾名思义，这个虚拟地址空间只是一个展现给机器级程序的概念性映像。实际的实现（见第9章）是将动态随机访问存储器（DRAM）、闪存、磁盘存储器、特殊硬件和操作系统软件结合起来，为程序提供一个看上去统一的字节数组。
在接下来的几章中，我们将讲述编译器和运行时系统是如何将存储器空间划分为更可管理的单元，来存放不同的程序对象（program object），即程序数据、指令和控制信息。可以用各种机制来分配和管理程序不同部分的存储。这种管理完全是在虚拟地址空间里完成的。例如，C语言中一个指针的值（无论它指向一个整数、一个结构或是某个其他程序对象）都是某个存储块的第一个字节的虚拟地址。C编译器还把每个指针和类型信息联系起来，这样就可以根据指针值的类型，生成不同的机器级代码来访问存储在指针所指向位置处的值。尽管C编译器维护着这个类型信息，但是它生成的实际机器级程序并不包含关于数据类型的信息。每个程序对象可以简单地视为一个字节块，而程序本身就是一个字节序列。
阶C再初学者C 语言中指针的作用
指针是C语言的一个重要特性。它提供了引用数据结构（包括数组）的元素的机制。与变量类似，指针也有两个方面∶值和类型。它的值表示某个对象的位置，而它的类型表示那个位置上所存储对象的类型（比如整数或者浮点数）。
真正理解指针需要查看它们在机器级上的表示以及实现。这将是第3章的重点之一，3.10.1节将对其进行深入介绍。
2.1.1 十六进制表示法
一个字节由8位组成。在二进制表示法中，它的值域是0000002～1111112。如果看成十进制整数，它的值域就是0。～255。。两种符号表示法对于描述位模式来说都不是非常方便。二进制表示法太冗长，而十进制表示法与位模式的互相转化很麻烦。替代的方法是，以16为基数，或者叫做十六进制（hexadecimal）数，来表示位模式。十六进制（简写为"hex"）使用数字'0'～'9'以及字符'A'～'F'来表示16个可能的值。图2-2展示了16个十六进制数字对应的十进制值和二进制值。用十六进制书写，一个字节的值域为00%～FF;。

在C语言中，以0x或0x开头的数字常量被认为是十六进制的值。字符'A'～'F'既可以是大写，也可以是小写。例如，我们可以将数字FA1D37B。写作0xFA1D37B，或者0xfald37b，甚至是大小写混合，比如，0xFa1D37b。在本书中，我们将使用C表示法来表示十六进制值。
编写机器级程序的一个常见任务就是在位模式的十进制、二进制和十六进制表示之间人工转换。二进制和十六进制之间的转换比较简单直接，因为可以一次执行一个十六进制数字的转换。数字的转换可以参考如图2-2所示的表。一个简单的窍门是，记住十六进制数字A、C和F相应的十进制值。而对于把十六进制值B、D和E转换成十进制值，则可以通过计算它们与前三个值的相对关系来完成。
比如，假设给你一个数字0x173A4C。可以通过展开每个十六进制数字，将它转换为二进制格式，如下所示∶
十六进制
二进制0001 0111 0011 1010 0100 1100 这样就得到了二进制表示00010111001101001001100。
反过来，如果给定一个二进制数字1110010101101101001，可以通过首先把它分为每4位一组来转换为十六进制。不过要注意，如果位总数不是4的倍数，最左边的一组可以少于4位，前面用0补足。然后将每个4位组转换为相应的十六进制数字∶
制11 1100 1010 1101 1011 011 十六进制 3cA 

练习题2.1 完成下面的数字转换∶
26 第一部分 程序站构和执行
A.将 0x39A7F8转换为二进制。
B.将二进制110010010111011转换为十六进制。C.将0xD5E4C转换为二进制。
D.将二进制1001101110011110110101转换为十六进制。
当值x是2的非负整数n次幂时，也就是x=2"，我们可以很容易地将x写成十六进制形式，只要记住x的二进制表示就是1后面跟n个0。十六进制数字0代表4个二进制0。所以，当n表示成i+4j的形式，其中0≤i≤3，我们可以把x写成开头的十六进制数字为1（i=0）、2（i=1）、4（i=2）或者8（i=3），后面跟随着j个十六进制的0。比如，x=2048=2，我们有n=11=3＋4·2，从而得到十六进制表示0x800。
练习题2.2 填写下表中的空白项，给出2的不同次幂的二进制和十六进制表示∶

十进制和十六进制表示之间的转换需要使用乘法或者除法来处理一般情况。将一个十进制数字x转换为十六进制，可以反复地用16除x，得到一个商q和一个余数r，也就是x=q·16＋r。然后，我们用十六进制数字表示的r作为最低位数字，并且通过对q反复进行这个过程得到剩下的数字。例如，考虑十进制314156的转换∶
314156=19634·16＋12 (C)19634= 1227·16+2 1227=76·16＋11 76= 4·16+12 4= 0·16+4
从这里，我们能读出十六进制表示为0x4CB2C。
反过来，将一个十六进制数字转换为十进制数字，我们可以用相应的16的幂乘以每个十六进制数字。比如，给定数字0x7AF，我们计算它对应的十进制值为7·16²＋10·16+15=7·256＋10·16＋15=1792＋160＋15=1967。
练习题2.3一个字节可以用两个十六进制数字来表示。填写下表中缺失的项，给出
不同字节模式的十进制、二进制和十六进制值

穿注十进制和十六进制间的转换
较大数值的十进制和十六进制之间的转换，最好是让计算机或者计算器来完成。有大量的工具可以完成这个工作。一个简单的方法就是利用任何标准的搜索引擎，比如查询∶
把 0xabcd转换为十进制数
把123用十六进制表示。
练习题2.4 不将数字转换为十进制或者二进制，试着解答下面的算术题，答案要用
十六进制表示。提示∶只要将执行十进制加法和减法所使用的方法改成以16为基数。A.0x503c+0x8-B.0x503c-0x40=C. 0x503c+64=D.0x50ea-0x503c
2.1.2 字数据大小
每台计算机都有一个字长（word size），指明指针数据的标称大小nominal size）。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。也就是说，对于一个字长为w位的机器而言，虚拟地址的范围为0～2"-1，程序最多访问2"个字节。
最近这些年，出现了大规模的从32位字长机器到64位字长机器的迁移。这种情况首先出现在为大型科学和数据库应用设计的高端机器上，之后是台式机和笔记本电脑，最近则出现在智能手机的处理器上。32位字长限制虚拟地址空间为4千兆字节（写作4GB），也就是说，刚刚超过4×10°字节。扩展到64位字长使得虚拟地址空间为16EB，大约是1.84×10"字节。
大多数64位机器也可以运行为32位机器编译的程序，这是一种向后兼容。因此，举例来说，当程序 prog.c用如下伪指令编译后
linux> gcc-m32 prog.c
该程序就可以在32 位或 64 位机器上正确运行。另一方面，若程序用下述伪指令编译
有符号[signed] char short
linux> gec-m64 prog.c
那就只能在64位机器上运行。因此，我们将程序称为"32位程序"或"64位程序"时，区别在于该程序是如何编译的，而不是其运行的机器类型。
int
long int32_t int64_t char·float double
计算机和编译器支持多种不同方式编码的数字格式，如不同长度的整数和浮点数。比如，许多机器都有处理单个字节的指令，也有处理表示为2字节、4字节或者8字节整数的指令，还有些指令支持表示为4字节和8字节的浮点数。

C语言支持整数和浮点数的多种数据格式。图2-3展示了为C语言各种数据类型分配的字节数。（我们在2.2节讨论C标准保证的字节数和典型的字节数之间的关系。）有些数据类型的确切字节数依赖于程序是如何被编译的。我们给出的是32位和64位程序的典型值。整数或者为有符号的，即可以表示负数、零和正数;或者为无符号的，即只能表示非负数。C的数据类型char表示一个单独的字节。尽管"char"是由于它被用来存储文本串中的单个字符这一事实而得名，但它也能被用来存储整数值。数据类型 short、int和long可以提供各种数据大小。即使是为64位系统编译，数据类型int通常也只有4个字节。数据类型long一般在32位程序中为4字节，在64位程序中则为8字节。
为了避免由于依赖"典型"大小和不同编译器设置带来的奇怪行为，ISOC99引入了一类数据类型，其数据大小是固定的，不随编译器和机器设置而变化。其中就有数据类型int32t和 int64t，它们分别为4个字节和8个字节。使用确定大小的整数类型是程序员准确控制数据表示的最佳途径。
大部分数据类型都编码为有符号数值，除非有前缀关键字 unsigned或对确定大小的数据类型使用了特定的无符号声明。数据类型char是一个例外。尽管大多数编译器和机器将它们视为有符号数，但C标准不保证这一点。相反，正如方括号指示的那样，程序员应该用有符号字符的声明来保证其为一个字节的有符号数值。不过，在很多情况下，程序行为对数据类型 char是有符号的还是无符号的并不敏感。
对关键字的顺序以及包括还是省略可选关键字来说，C语言允许存在多种形式。比如，下面所有的声明都是一个意思∶
unsigned long unsigned long int long unsigned long unsigned int
我们将始终使用图2-3给出的格式。
图2-3还展示了指针（例如一个被声明为类型为"char·"的变量）使用程序的全字长。大多数机器还支持两种不同的浮点数格式∶单精度（在C中声明为float）和双精度（在C中声明为double）。这些格式分别使用4字节和8字节。酷◎用言初学厂声明指针对于任何数据类型T，声明T *p;
表明p是一个指针变量，指向一个类型为T的对象。例如，
char *p;
就将一个指针声明为指向一个 char类型的对象。
程序员应该力图使他们的程序在不同的机器和编译器上可移植。可移植性的一个方面就是使程序对不同数据类型的确切大小不敏感。C语言标准对不同数据类型的数字范围设置了下界（这点在后面还将讲到），但是却没有上界。因为从1980年左右到2010年左右，32位机器和32位程序是主流的组合，许多程序的编写都假设为图2-3中32位程序的字节分配。随着64位机器的日益普及，在将这些程序移植到新机器上时，许多隐藏的对字长的依赖性就会显现出来，成为错误。比如，许多程序员假设一个声明为int类型的程序对象能被用来存储一个指针。这在大多数32 位的机器上能正常工作，但是在一台64位的机器上却会导致问题。

2.1.3 寻址和字节顺序
对于跨越多字节的程序对象，我们必须建立两个规则∶这个对象的地址是什么，以及在内存中如何排列这些字节。在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。例如，假设一个类型为int的变量x的地址为0x100，也就是说，地址表达式sx的值为0x100。那么，（假设数据类型int为32位表示）x的4个字节将被存储在内存的0x100、0x101、0x102和0x103位置。
排列表示一个对象的字节有两个通用的规则。考虑一个w位的整数，其位表示为【x-，r一，…·x1，o6】，其中r一）是最高有效位，而x。是最低有效位。假设w是8的倍数，这些位就能被分组成为字节，其中最高有效字节包含位【x一1，工u一，…，r。一】，而最低有效字节包含位【x，，x，…，x6】，其他字节包含中间的位。某些机器选择在内存中按照从最低有效字节到最高有效字节的顺序存储对象，而另一些机器则按照从最高有效字节到最低有效字节的顺序存储。前一种规则——最低有效字节在最前面的方式，称为小端法（little endian）。后一种规则——最高有效字节在最前面的方式，称为大端法（big endian）。
假设变量 x的类型为int，位于地址0x100处，它的十六进制值为0x01234567。地址范围 0x100～0x103的字节顺序依赖于机器的类型

注意，在字0x01234567中，高位字节的十六进制值为0x01，而低位字节值为0x67。.大多数Intel兼容机都只用小端模式。另一方面，IBM和Oracle（从其2010年收购Sun Microsystems开始）的大多数机器则是按大端模式操作。注意我们说的是"大多数"。这些规则并没有严格按照企业界限来划分。比如，IBM和Oracle制造的个人计算机使用的是 Intel兼容的处理器，因此使用小端法。许多比较新的微处理器是双城法（bi-endian），也就是说可以把它们配置成作为大端或者小端的机器运行。然而，实际情况是∶一旦选择了特定操作系统，那么字节顺序也就固定下来。比如，用于许多移动电话的ARM微处理器，其硬件可以按小端或大端两种模式操作，但是这些芯片上最常见的两种操作系统——Android（来自Google）和IOS（来自Apple）———却只能运行于小端模式。
令人吃惊的是，在哪种字节顺序是合适的这个问题上，人们表现得非常情绪化。实际上，术语"litle endian（小端）"和"big endian（大端）"出自Jonathan Swit的《格利佛游记》（Gulliver'sTravels）一书，其中交战的两个派别无法就应该从哪一端（小端还是大端）打开一个半熟的鸡蛋达成一致。就像鸡蛋的问题一样，选择何种字节顺序没有技术上的理由，因此争论沦为关于社会政治论题的争论。只要选择了一种规则并且始终如一地坚持，对于哪种字节排序的选择都是任意的。废戏"W"的起源
以下是Jonathan Swift在1726年关于大小端之争历史的描述∶

"…我下面要告诉你的是，Lillput和Blefuscu这两大强国在过去36个月里一直在苦战。战争开始是由于以下的原因∶我们大家都认为，吃鸡蛋前，原始的方法是打破鸡蛋较大的一端，可是当今皇帝的祖父小时候吃鸡蛋，一次按古法打鸡蛋时碰巧将一个
手指弄破了，因此他的父亲，当时的皇帝，就下了一道救令，命令全体臣民吃鸡蛋时打破鸡蛋较小的一端，违令者重罚。老百姓们对这项命令极为反感。历史告诉我们，由此曾发生过六次短乱，其中一个皇帝送了命，另一个丢了王位。这些叛乱大多都是由Ble-fuscu的国王大臣们煽动起来的。叛乱平息后，流亡的人总是速到那个帝国去寻救避难。据估计，先后几次有11000人情愿受死也不肯去打破鸡蛋较小的一端。关于这一争端，曾出版过几百本大部著作，不过大端派的书一直是受禁的，法律也规定该派的任何人不
得做官。"（此段译文摘自网上蒋剑锋译的《格利佛游记》第一卷第4章。）
在他那个时代，Swift是在讽刺英国（Lilliput）和法国（Blefuscu）之间持续的冲突。Danny Cohen，一位网络协议的早期开创者，第一次使用这两个术语来指代字节顺序【24】，后来这个术语被广泛接纳了，
对于大多数应用程序员来说，其机器所使用的字节顺序是完全不可见的。无论为哪种类型的机器所编译的程序都会得到同样的结果。不过有时候，字节顺序会成为问题。首先是在不同类型的机器之间通过网络传送二进制数据时，一个常见的问题是当小端法机器产生的数据被发送到大端法机器或者反过来时，接收程序会发现，字里的字节成了反序的。为了避免这类问题，网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则，以确保发送方机器将它的内部表示转换成网络标准，而接收方机器则将网络标准转换为它的内部表示。我们将在第11章中看到这种转换的例子。
第二种情况是，当阅读表示整数数据的字节序列时字节顺序也很重要。这通常发生在检查机器级程序时。作为一个示例，从某个文件中摘出了下面这行代码，该文件给出了一个针对 Intel x86-64 处理器的机器级代码的文本表示∶
4004d3: 01 05 43 Ob 20 00add Weax,0x200b43(Xrip)
这一行是由反汇编器（disassembler）生成的，反汇编器是一种确定可执行程序文件所表示的指令序列的工具。我们将在第3章中学习有关这些工具的更多知识，以及怎样解释像这样的行。而现在，我们只是注意这行表述的意思是∶十六进制字节串0105430b2000是一条指令的字节级表示，这条指令是把一个字长的数据加到一个值上，该值的存储地址由0x20b43加上当前程序计数器的值得到，当前程序计数器的值即为下一条将要执行指令的地址。如果取出这个序列的最后4个字节∶430b 20 00，并且按照相反的顺序写出，我们得到00 20 0b43。去掉开头的0，得到值 0x200b43，这就是右边的数值。当阅读像此类小端法机器生成的机器级程序表示时，经常会将字节按照相反的顺序显示。书写字节序列的自然方式是最低位字节在左边，而最高位字节在右边，这正好和通常书写数字时最高有效位在左边，最低有效位在右边的方式相反。
字节顺序变得重要的第三种情况是当编写规避正常的类型系统的程序时。在C语言中，可以通过使用强制类型转换（cast）或联合（union）来允许以一种数据类型引用一个对象，而这种数据类型与创建这个对象时定义的数据类型不同。大多数应用编程都强烈不推荐这种编码技巧，但是它们对系统级编程来说是非常有用，甚至是必需的。
图2-4展示了一段C代码，它使用强制类型转换来访问和打印不同程序对象的字节表示。我们用typedef将数据类型byte_pointer定义为一个指向类型为"unsignedchar"的对象的指针。这样一个字节指针引用一个字节序列，其中每个字节都被认为是一个非负整数。第一个例程 showbytes的输入是一个字节序列的地址，它用一个字节指针以及一个字节数来指示。该字节数指定为数据类型size_t，表示数据结构大小的首选数据类型。showbytes打印出每个以十六进制表示的字节。C格式化指令"8.2x"表明整数必须用至少两个数字的十六进制格式输出。

过程 show_int、show_float和show_pointer展示了如何使用程序 show_bytes来分别输出类型为int、float和 void*的C程序对象的字节表示。可以观察到它们仅仅传递给 showbytes一个指向它们参数x的指针sx，且这个指针被强制类型转换为"un-signed char*"。这种强制类型转换告诉编译器，程序应该把这个指针看成指向一个字节序列，而不是指向一个原始数据类型的对象。然后，这个指针会被看成是对象使用的最低字节地址.
这些过程使用C语言的运算符 sizeof来确定对象使用的字节数。一般来说，表达式sizeof（T）返回存储一个类型为T的对象所需要的字节数。使用sizeof而不是一个固定的值，是向编写在不同机器类型上可移植的代码迈进了一步。
在几种不同的机器上运行如图2-5所示的代码，得到如图2-6所示的结果。我们使用了以下几种机器∶
Linux 32∶运行Linux 的Intel IA32处理器。Windows∶运行 Windows 的 Intel IA32处理器。
Sun∶运行 Solaris的 Sun Microsystems SPARC处理器。（这些机器现在由Orale生产。）Linax64∶运行Linux的 Intel x86-64处理器。


参数12345的十六进制表示为0x0003039。对于int类型的数据，除了字节顺序以外，我们在所有机器上都得到相同的结果。特别地，我们可以看到在Linux32、Windows 和Linux64上，最低有效字节值0x39最先输出，这说明它们是小端法机器;而在Sun上最后输出，这说明Sun是大端法机器。同样地，float数据的字节，除了字节顺序以外，也都是相同的。另一方面，指针值却是完全不同的。不同的机器/操作系统配置使用不同的存储分配规则。一个值得注意的特性是Linux32、Windows和Sun的机器使用4字节
地址，而Linux 64使用8字节地址。
诰C语初学考使用 typedor来命名数据类型
C 语言中的typedef声明提供了一种给数据类型命名的方式。这能够极大地改善代码的可读性，因为深度嵌套的类型声明很难读懂。
typedef的语法与声明变量的语法十分相像，除了它使用的是类型名，而不是变量名。因此，图24中bytepointer的声明和将一个变量声明为类型"unsigned char · "有相同的形式。
例如，声明∶typedef int *int_pointer;int_pointer Ap;
将类型"int_pointer"定义为一个指向int的指针，并且声明了一个这种类型的变量 ip。我们还可以将这个变量直接声明为∶
int *ip;

第2章信息的表示和处理33
件C语葺初学著使用 printf格式化输田
printf函数（还有它的同类fprintf和sprintf）提供了一种打印信息的方式，这种方式对格式化细节有相当大的控制能力。第一个参数是格式串（format string），而其余的参数都是要打印的值。在格式串里，每个以""开始的字符序列都表示如何格式化下一个参数。典型的示例包括∶'%d'是输出一个十进制整数，'%f'是输出一个浮点数，而'8c'是输出一个宇符，其编码由参数给出。
指定确定大小数据类型的格式，如int32_t，要更复杂一些，相关内容参见2.2.3 节的旁注。
可以观察到，尽管浮点型和整型数据都是对数值12345 编码，但是它们有截然不同的字节模式∶整型为0x0003039，而浮点数为0x4640E400。一般而言，这两种格式使用不同的编码方法。如果我们将这些十六进制模式扩展为二进制形式，并且适当地将它们移位，就会发现一个有13个相匹配的位的序列，用一串星号标识出来∶o o 0 03 0 3 9 o00o00o0000110000111001
4 6 4 0 E4 0 01000100100011100000
这并不是巧合。当我们研究浮点数格式时，还将再回到这个例子。铅C话工别学厂指针和数组
在函数 showbytes（图2-4）中，我们看到指针和数组之间紧密的联系，这将在3.8节中详细描述。这个函数有一个类型为bytepolinter（被定义为一个指向 unsigned char的指针）的参数start，但是我们在第8行上看到数组引用start【i】。在C语言中，我们能够用数组表示法来引用指针，同时我们也能用指针表示法来引用数组元素。在这个例子中，引用start【1】表示我们想要读取以start指向的位置为起始的第i个位置处的字节。
昏 联C罢丁指针的创建和间接T用
在图2-4的第13、17和21行，我们看到对C和C++中两种独有操作的使用。C的"取地址"运算符s创建一个指针。在这三行中，表达式6x创建了一个指向保存变量x的位置的指针。这个指针的类型取决于x的类型，因此这三个指针的类型分别为int*、f1oat*和void*。（数据类型 void*是一种特殊类型的指针，没有相关联的类型信息。）
强制类型转换运算符可以将一种数据类型转换为另一种。因此，强制类型转换（（bytepointer）x表明无论指针6x以前是什么类型，它现在就是一个指向数据类型为unsigned char的指针。这里给出的这些强制类型转换不会改变真实的指针，它们只是告诉编译器以新的数据类型来看待被指向的数据。用 生成一张ASCT表
可以通过执行命令 man asci来得到一张 ASCII字符码的表。练习题2.5 思考下面对 show_bytes 的三次调用∶
show_bytes(valp,1);/*A.*/show_bytes(valp,2);/*B.*/sho_bytes(valp,3);/*C.*/
指出在小端法机器和大端法机器上，每次调用的输出值。大端法∶A.小端法∶B.小端法∶大端法∶
C. 小端法∶
大端法∶
练习题2.6 使用show_int和show_float，我们确定整数3510593的十六进制表示
为0x00359141，而浮点数 3510593.0的十六进制表示为0x4A564504。A.写出这两个十六进制值的二进制表示。
B.移动这两个二进制串的相对位置，使得它们相匹配的位数最多。有多少位相匹配呢?C.串中的什么部分不相匹配?2.1.4 表示字符串
C语言中字符串被编码为一个以 null（其值为0）字符结尾的字符数组。每个字符都由某个标准编码来表示，最常见的是ASCI字符码。因此，如果我们以参数"12345"和6 （包括终止符）来运行例程 showbytes，我们得到结果313233435 00。请注意，十进制数字x的ASCI码正好是0x3x，而终止字节的十六进制表示为0x00。在使用ASCI码作为字符码的任何系统上都将得到相同的结果，与字节顺序和字大小规则无关。因而，文本数据比二进制数据具有更强的平台独立性。
练习题 2.7 下面对show_bytes的调用将输出什么结果?
const char *s ="abcdef";
show_bytea((byte pointer) a,strlan(a);注意字母'a'～''的ASCII码为0x61～0x7A. 费注 文字编码的 Unicodoe标准
ASCI字符集适合于编码英语文档，但是在表达一些特殊字符方面并没有太多办法，例如法语的"C"。它完全不适合编码希腊语、俄语和中文等语言的文档。这些年，提出了很多方法来对不同语言的文字进行编码。Unicode联合会（Unicode Consortium）修订了最全面且广泛接受的文字编码标准。当前的Unicode标准（7.0版）的字库包括将近10000个字
符，支持广泛的语言种类，包括古埃及和巴比伦的语言。为了保持信用，Unicode技术委员会否决了为Klingon（即电视连续剧《星际迷航》中的虚构文明）编写语言标准的提议。基本编码，称为Unicode的"统一字符集"，使用32位来表示字符。这好像要求文本串中每个字符要占用4个字节。不过，可以有一些替代编码，常见的字符只需要1个或2个字节，而不太常用的字符需要多一些的字节数。特别地，UTF-8表示将每个字#编码为一个字节序列，这样标准ASCI字符还是使用和它们在ASCI中一样的单字节
编码，这也就意味着所有的ASCII字节序列用ASCI马表示和用UTF-8表示是一样的。Java编程语言使用 Unicode来表示字符串。对于C语言也有支持Unicode的程序库。2.1.5 表示代码
考虑下面的C函数∶

第2章 信息的表示和处理35
int gua(int x,int y)(return x + y;3 )
当我们在示例机器上编译时，生成如下字节表示的机器代码∶Limux 32 5589 e5 8b 45 0c0345 08 c9 c3 Windows 55 89 e5 8b 45 Oc 03 45 08 5d ca Sum81 c3 e0 08 90 02 00 09
我们发现指令编码是不同的。不同的机器类型使用不同的且不兼容的指令和编码方式。即使是完全一样的进程，运行在不同的操作系统上也会有不同的编码规则，因此二进制代码是不兼容的。二进制代码很少能在不同机器和操作系统组合之间移植。
计算机系统的一个基本概念就是，从机器的角度来看，程序仅仅只是字节序列。机器没有关于原始源程序的任何信息，除了可能有些用来帮助调试的辅助表以外。在第3章学习机器级编程时，我们将更清楚地看到这一点。2.1.6 布尔代数简介
二进制值是计算机编码、存储和操作信息的核心，所以围绕数值0和1的研究已经演化出了丰富的数学知识体系。这起源于1850年前后乔治·布尔（George Boole，1815—1864）的工作，因此也称为布尔代数（Bolan algebra）。布尔注意到通过将逻辑值 TRUE（真）和FALSE（假）编码为二进制值1和O，能够设计出一种代数，以研究逻辑推理的基本原则。
最简单的布尔代数是在二元集合{0，1）┌基础上的定义。图2-7定义了这种布尔代数中的几种运算。我们用来表示这些运算的符 L 号与C语言位级运算使用的符号是相匹配图27 布尔代数的运算。二进制值1和0表示
的，这些将在后面讨论到。布尔运算~对应逻辑值TRUE或者FALSE，而运算符-、&、l和^分别表示逻辑运算 NOT、
于逻辑运算NOT，在命题逻辑中用符号一
AND、OR和EXCLUSIVEOR
表示。也就是说，当P不是真的时候，我
们就说P是真的，反之亦然。相应地，当P等于0时，~P等于1，反之亦然。布尔运算&.对应于逻辑运算 AND，在命题逻辑中用符号A表示。当P和Q都为真时，我们说PA Q为真。相应地，只有当p=1且q=1时，p&q才等于1。布尔运算对应于逻辑运算OR，在命题逻辑中用符号V表示。当P或者Q为真时，我们说PVQ成立。相应地，当p=1或者q=1时，plg等于1。布尔运算-对应于逻辑运算异或，在命题逻辑中用符号表示。当P或者Q为真但不同时为真时，我们说P④Q成立。相应地，当p=1且q=0，
或者p=0且q=1时，p^q等于1
后来创立信息论领域的Claude Shannon（1916—2001）首先建立了布尔代数和数字逻辑之间的联系。他在1937年的硕士论文中表明了布尔代数可以用来设计和分析机电继电器网络。尽管那时计算机技术已经取得了相当的发展，但是布尔代数仍然在数字系统的设计和分析中扮演着重要的角色。
我们可以将上述4个布尔运算扩展到位向量的运算，位向量就是固定长度为w、由0 和1组成的串。位向量的运算可以定义成参数的每个对应元素之间的运算。假设a和b分别表示位向量【a一，a一，…a0】和【b，b一，…b】。我们将a&b也定义为一个长度为w的位向量，其中第i个元素等于a&b，0≤i<w。可以用类似的方式将运算、
和~扩展到位向量上。
举个例子，假设w=4，参数a=【0110】，b=【1100】。那么4种运算a&b、ab、a-b 和~b分别得到以下结果

网经浸注DATEOOL 厂关于布尔代数和布尔环的更多内容
对于任意整数w>0，长度为w的位向量上的布尔运算、&和-形成了一个布尔代数。最简单的情况是w=1时，只有2个元素;但是对于更普遍的情况，有2"个长度为w的位向量。布尔代数和整数算术运算有很多相似之处。例如，乘法对加法的分配律，写为a·（b+c）=（a·b）+（a·c），而布尔运算&对的分配律，写为a&（bc）=（a&b（a&c）。此外，布尔运算对&也有分配律，写为al（b&c）=（alb）&（alc），但是对于整数我们不能说a+（b·c）=（a+b）·（a+c）。
当考虑长度为w的位向量上的、&和~运算时，会得到一种不同的数学形式，我们称为布尔环（Booleanring）。布尔环与整数运算有很多相同的属性。例如，整数运算的一个属性是每个值x都有一个加法递元（additive inverse）-r，使得x+（-x）=0。布尔环也有类似的属性，这里的"加法"运算是，不过这时每个元素的加法逆元是它自已本身。也就是说，对于任何值a来说，aa=0，这里我们用0来表示全0的位向量。可以看到对单个位来说这是成立的，即0~0=1×1=0，将这个扩展到位向量也是成立
的。当我们重新排列组合顺序，这个属性也仍然成立，因此有（a~b）a=b。这个属性会引起一些很有趣的结果和聪明的技巧，在练习题2.10中我们会有所探讨。
位向量一个很有用的应用就是表示有限集合。我们可以用位向量【a一1，…，a，a】编码任何子集A二（0，1，，…，w-1），其中a，=1当且仅当i∈A。例如（记住我们是把a一写在左边，而将a。写在右边），位向量a=【01101001】表示集合A=（0，3，5，6），而b=【01010101】表示集合B=（0，2，4，61。使用这种编码集合的方法，布尔运算和&分别对应于集合的并和交，而-对应于于集合的补。还是用前面那个例子，运算a&b 得到位向量【010000】，而 A门B={0，6）。
在大量实际应用中，我们都能看到用位向量来对集合编码。例如，在第8章，我们会看到有很多不同的信号会中断程序执行。我们能够通过指定一个位向量掩码，有选择地使能或是屏蔽一些信号，其中某一位位置上为1时，表明信号i是有效的（使能），而0表明该信号是被屏蔽的。因而，这个掩码表示的就是设置为有效信号的集合。

练习题2.9 通过混合三种不同颜色的光（红色、绿色和蓝色），计算机可以在视频屏幕或者液晶显示器上产生彩色的画面。设想一种简单的方法，使用三种不同颜色的光，每种光都能打开或关闭，投射到玻璃屏幕上，如图所示;
玻璃焊幕
少
那么基于光源R（红）、G（绿）、B（蓝）的关闭（0））或打开（1），我们就能够创建8 种不同的颜色颜色红紫色蓝色
白色
蓝绿色
这些颜色中的每一种都能用一个长度为3的位向量来表示，我们可以对它们进行布尔运算。
A.一种颜色的补是通过关掉打开的光源，且打开关闭的光源而形成的。那么上面列
出的8种颜色每一种的补是什么?B.描述下列颜色应用布尔运算的结果∶
蓝色 绿色黄色 8. 蓝绿色红色  红y

2.1.7C语言中的位级运算
C语言的一个很有用的特性就是它支持按位布尔运算。事实上，我们在布尔运算中使用的那些符号就是C语言所使用的∶就是OR（或），&.就是AND（与），-就是 NOT（取反），而·就是 EXCLUSIVEOR（异或）。这些运算能运用到任何"整型"的数据类型上，包括图2-3所示内容。以下是一些对 char数据类型表达式求值的例子∶

正如示例说明的那样，确定一个位级表达式的结果最好的方法，就是将十六进制的参数扩展成二进制表示并执行二进制运算，然后再转换回十六进制。

练习题2.10 对于任一位向量a，有aca=0。应用这一属性，考虑下面的程序∶

正如程序名字所暗示的那样，我们认为这个过程的效果是交换指针变量x和y所指向
的存储位置处存放的值。注意，与通常的交换两个数值的技术不一样，当移动一个值时，我们不需要第三个位置来临时存储另一个值。这种交换方式并没有性能上的优势，它仅仅是一个智力游戏。
以指针x和y指向的位置存储的值分别是a和b作为开始，填写下表，给出在程序的每一步之后，存储在这两个位置中的值。利用入的属性证明达到了所希望的效果。回想一下，每个元素就是它自身的加法进元（a-a=0）。步骤初始第1步
练习题2.11 在练习题2.10中的inplace_swap函数的基础上，你决定写一段代码，
实现将一个数组中的元素头尾两端依次对调。你写出下面这个函数∶

当你对一个包含元素1、2、3和4的数组使用这个函数时，正如预期的那样，现在数组的元素变成了4、3、2和1。不过，当你对一个包含元素1、2、3、4和5的数组使用这个函数时，你会很惊奇地看到得到数字的元素为5、4、0、2和1。实际上，你会发现这段代码对所有偶数长度的数组都能正确地工作，但是当数组的长度为奇数时，它就会把中间的元素设置成0。
A.对于一个长度为奇数的数组，长度cnt=2k＋1，函数reverse_array最后一次循环中，变量first和last的值分别是什么?
B.为什么这时调用函数inplace_swap会将数组元素设置为0?C.对reverse_array的代码做哪些简单改动就能消除这个问题?
位级运算的一个常见用法就是实现掩码运算，这里掩码是一个位模式，表示从一个字中选出的位的集合。让我们来看一个例子，掩码 oxFF（最低的8位为1））表示一个字的低位字节。位级运算x60xFF生成一个由x的最低有效字节组成的值，而其他的字节就被置为0。比如，对于x= 0x89ABCDEF，其表达式将得到0x0000EF。表达式-0将生成一个全1的掩码，不管机器的字大小是多少。尽管对于一个32位机器来说，同样的掩码可以写成0xFFFFFE，但是这样的代码不是可移植的。

练习题2.12 对于下面的值，写出变量x的C语言表达式。你的代码应该对任何字
长w≥8都能工作。我们给出了当x=0x87654321以及w=32时表达式求值的结果，仅供参考。
A.x的最低有效字节，其他位均置为0。【0x000021】。
B. 除了×的最低有效字节外，其他的位都取补，最低有效字节保持不变。【0x78ABC2】。C.x的最低有效字节设置成全1，其他字节都保持不变。【0x876543FF】。
练习题2.13 从20世纪70年代末到80年代末，Digital Equipment的VAX计算机是一种非常流行的机型。它没有布尔运算AND和OR指令，只有bis（位设置）和bic（位清除）这两种指令。两种指令的输入都是一个数据字x和一个掩码字m。它们生成一个结果z，2是由根据掩码m的位来修改×的位得到的。使用bis指令，这种修改就是在m为1的每个位置上，将z对应的位设置为1。使用bic指令，这种修改就是在m为1 的每个位暨，将z对应的位设置为0。
为了看清楚这些运算与C语言位级运算的关系，假设我们有两个函数bis和bic来实现位设置和位清除操作。只想用这两个函数，而不使用任何其他C语言运算，来实现按位和运算。填写下列代码中缺失的代码。提示∶写出bis和bic运算的C语言表达式。

2.1.8 C 语言中的逻辑运算
C语言还提供了一组逻辑运算符、&&和!，分别对应于命题逻辑中的OR、AND 和NOT运算。逻辑运算很容易和位级运算相混淆，但是它们的功能是完全不同的。逻辑运算认为所有非零的参数都表示TRUE，而参数0表示FALSE。它们返回1或者0，分别表示结果为TRUE或者为FALSE。以下是一些表达式求值的示例。

可以观察到，按位运算只有在特殊情况下，也就是参数被限制为0或者1时，才和与
40第一部分 程序结构和执行
其对应的逻辑运算有相同的行为。
逻辑运算符&&.和与它们对应的位级运算&.和之间第二个重要的区别是，如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。因此，例如，表达式as5/a将不会造成被零除，而表达式ps*p+也不会导致间接引用空指针。三 练习题2.14 假设x和y的字节值分别为0x66和0x39。填写下表，指明各个C表达
式的字节值。表达式
表达式x 6 y
xy
xI y x I -y :xIy x 4s "y x s !y
练习题2.15 只使用位级和逻辑运算，编写一个C表达式，它等价于x==y。换句话
说，当x和y相等时它将返回1，否则就返回0。2.1.9C 语言中的移位运算
C语言还提供了一组移位运算，向左或者向右移动位模式。对于一个位表示为【r一，五一，…x6】的操作数x，C表达式x<k会生成一个值，其位表示为【1，z--2，·…，x。，0，…0】。也就是说，x向左移动k位，丢弃最高的k位，并在右端补k个0.移位量应该是一个0～w-1之间的值。移位运算是从左至右可结合的，所以x<<j<<k等价于(x<3)<<k。
有一个相应的右移运算 x>k，但是它的行为有点微妙。一般而言，机器支持两种形式的右移∶逻辑右移和算术右移。逻辑右移在左端补k个0，得到的结果是【0，…0，x1，工一…xa】。算术右移是在左端补k个最高有效位的值，得到的结果是【z一，…，工一1，工-1，工-2，…，z】】。这种做法看上去可能有点奇特，但是我们会发现它对有符号整数数据的运算非常有用。
让我们来看一个例子，下面的表给出了对一个8位参数×的两个不同的值做不同的移位操作得到的结果·

斜体的数字表示的是最右端（左移）或最左端（右移）填充的值。可以看到除了一个条目之外，其他的都包含填充0。唯一的例外是算术右移【10010101】的情况。因为操作数的最高位是1，填充的值就是1。
C语言标准并没有明确定义对于有符号数应该使用哪种类型的右移——算术右移或者逻辑右移都可以。不幸地，这就意味着任何假设一种或者另一种右移形式的代码都可能会遇到可移植性问题。然而，实际上，几乎所有的编译器/机器组合都对有符号数使用算术右移，且许多程序员也都假设机器会使用这种右移。另一方面，对于无符号数，右移必须是逻辑的。与C相比，Java对于如何进行右移有明确的定义。表达是x>k会将x算术右移k个位置，而 x>>>k 会对 x 做逻辑右移。柱移动 k 位，这里k 很天
对于一个由w位组成的数据类型，如果要移动k≥w位会得到什么结果呢?例如，计算下面的表达式会得到什么结果，假设数据类型int为w=32∶
t1val·OXFEDCBA98< 32;umsiged uvai-OxFEDCBA06u3>46;
C语言标准很小心地规避了说明在这种情况下该如何做。在许多机器上，当移动一个w位的值时，移位指令只考虑位移量的低logw位，因此实际上位移量就是通过计算kmod w得到的。例知，当w=32时，上面三个移位运算分别是移动0、4和8位，得到结果∶
lval 0xFEDCBA98 aval 0xFFEDCBA9 uval ox0OFEDCBA
不过这种行为对于C程序来说是没有保证的，所以应该保持位移量小于待移位值的位数。另一方面，Java特别要求位移数量应该按照我们前面所讲的求模的方法来计算。注 与移位运算有关的操作符优先级问题
常常有人会写这样的表达式1<<2+3<<4，本意是（1<<2）+（3<<4）。但是在C语言中，前面的表达式等价于1<<（2+3）<<4，这是由于加法（和减法）的优先级比移位运算要高。然后，按照从左至右结合性规则，括号应该是这样打的（1<<（2+3））<<4，得到的结果是512，而不是期望的52。
在C表达式中搞错优先级是一种常见的程序错误原因，而且常常很难检查出来。所z当你拿不准的时候，请加上括号!
练习题2.16 填写下表，展示不同移位运算对单字节数的影响。思考移位运算的最好方式是使用二进制表示。将最初的值转换为二进制，执行移位运算，然后再转换回十六进制。每个答案都应该是8个二进制数字或者2个十六进制数字。
o>2（算术的）十天进制二进制
十六进制
十六进制三进制制十六进制二进制0x75 0xB7