第2章信息的表示和操作

本章的主要内容有：

2.1节信息的存储
2.2节整数的表示
2.3节整数的运算
2.4节浮点数
2.5节总结

现代计算机存储和处理表示为二值信号的信息。这些二进制数位形成了数字革命的基础。

我们熟悉的10进制数由印度人发明，已在印度使用了超过1千年，在12世纪阿拉伯数学家对其进行了改进，在13世纪意大利数学家Fibonacci将其引进西方。

对有10个手指的人类来说，使用十进制是很自然的事，但当建造存储和处理信息的机器时，二进制数更好用。二值信号容易表示、存储和传输，比如打孔卡上是否有洞、电线上的电压是高还是低、磁场的方向是顺时针还是逆时针等。基于二值信号的存储和执行计算的电路非常简单和可靠，使得制造商可在一个硅芯片上集成数百万甚至数十亿个这样的电路。

单独地看一个位并不是很有用。但是，当我们将位分组在一起，并进行某种解释时，就让不同的位模式有了含义，这样我们就能表示任意一个有限集的元素。比如，使用一个二进制数系统，我们能使用位组来编码非负整数。通过使用一个标准的字符码，我们能对一个文档里的字符和符号进行编码。我们在本章里会覆盖这两部分编码方式，以及非负数的编码表示和实数的近似表示等。

我们考虑3种重要的数字表示方法：

无符号数表示法
基于传统的二进制记号，表示大于等于0的整数。
补码表示法
最常用的表示有符号整数的方法。
浮点数表示法
使用二进制记号的科学计数法来表示实数。

使用不同表示方法实现的计算机整数算术运算跟数学上的整数算术运算类似。

计算机上的整数算术运算满足数学上的整数算术运算的大部分性质，比如乘法满足结合律、交换律等。

(500*400)*(300*200)=-884901888
((500*400)*300)*200=-884901888
((200*500)*300)*400=-884901888
400*(200*(300*500))=-884901888

由于计算机使用有限个位来编码一个数，因此当操作的结果太大而不能被表示时，则该操作就溢出了。这会导致一些令人惊讶的结果。比如，在今天的大部分计算机上，表达式200*300*400*500的值为-884901888。这个结果违背了数学上的整数运算的性质，即一组正整数的乘积是一个负数。

计算机上的浮点数算术运算跟数学上的实数的算术运算有着不同的性质。

一组正数的乘积会溢出会得到正无穷 $+\infty$ 。
一组正数的乘积乘积通常都是正数。
由于浮点数表示方法的精度有限，所以计算机上的浮点数运算不满足结合律，比如表达式(3.14+1e20)-1e20的值为0，表达式3.14+(1e20-1e20)的值为0。

计算机的整数运算和浮点数运算有着不同的数学性质源于它们处理表示有限性的方式不同：整数的表示能精确地编码相对小范围的数值，而浮点数的表示能近似地编码相对大范围的数值。

通过研究计算机上数的实际表示方法，我们能理解该方法可以表示的数值范围，以及不同算术运算的性质。这种理解对编写所有数值范围都正确运行的程序及可跨机器、操作系统及编译器等移植的程序是很关键的。如我们将要描述的那样，由于计算机算术运算跟数学运算间的微妙差别，所以出现了许多计算机安全漏洞。在早期，程序错误碰巧发生时只会给人们带来不便。现在有多个黑客团伙试图利用其发现的任何错误来获得对他人系统的非法访问。这就使得程序员有更高的义务来理解他们的程序如何执行，以及怎样使程序以不可期的方式运行。

计算机使用多种不同的二进制表示方式来编码数值。随着你在第3章里接触到机器语言编程，你需要熟悉这些表示方式。我们在本章里描述这些编码，向你展示如何合理分析数的二进制表示。通过直接操作数字的位表示，我们得出了许多方法来执行算术运算。理解这些技术对理解编译器在尝试优化算术表达式求值的性能时生成的机器码很重要。

我们是基于一组核心的数学原理来处理这份材料的。我们从编码的基本定义开始，然后导出一些性质，比如可表示的数的范围、它们的位级别表示、算术运算性质等。我们相信从这种抽象角度来学习这份材料对你来说很重要，因为程序员需要清楚地理解计算机算术运算跟我们熟悉的整数与实数运算之间的联系和区别。

C++是基于C构建的，跟C使用的是相同的数值表示方法和操作。在本章中对C讲述的理论对于C++同样成立。
Java语言定义创造一套新的数值表示和操作的标准。
C标准支持更多的实现，Java标准有着非常具体的数据格式和编码。
在本章里，我们会在多处重点介绍由Java支持的表示和操作。

第2.1节存储信息

不是访问内存中的单个位，大部分计算机使用字节(由8个位组成的块)作为内存访问的最小单元。

机器码程序将内存看成是一个非常大的字节数组，即虚拟内存。每一个内存字节都由一个地址(一个唯一的数)确定，所有可能的地址构成了虚拟地址空间。如名字所示，这个虚拟地址空间只是一个展示给机器码程序的概念上的视图。实际的实现(在第9章里)综合使用了DRAM、闪存、磁盘、特殊硬件以及操作系统来给程序提供看似是单个的字节数组。

在接下来的章节里，我们将描述编译器和运行时系统如何将这个内存空间划分成更多的可管理的单元来存储不同的程序对象，包括程序数据、指令、控制信息等。使用了各种各样的机制来分配和管理不同程序部分的存储。这种管理都是在虚拟地址空间中执行的。比如，在C语言中的指针的值(不管该指针指向的是一个整数还是结构体或者其他程序对象)是某个内存块的首个字节的虚拟地址。C编译器也给每个指针分配类型信息，以便能生成不同的机器码，根据值的类型来访问指针指向的地址中存储的值。虽然由C编译器来维护这种类型信息，但是实际生成的机器码程序却没有数据类型相关的任何信息。机器码程序简单地将每个程序对象看做是一个字节块，将程序自身看做是字节序列。

第2.1.1小节十六进制表示法

一个字节由8个位组成。使用二进制表示，一个字节的值的范围是从 $(00000000)_2$ 到 $(11111111)_2$ 。使用十进制表示，一个字节的范围是从 $0_{10}$ 到 $255_{10}$ 。注意：使用这两种进制表示来描述位模式不方便。二进制表示太冗长，十进制和二进制之间的转换太繁琐。相反，我们使用十六进制来描述位模式。

十六进制使用数字0到数字9、字符A到字符F来表示16个可能的值。图2.2里展示了16个16进制数及其对应的十进制数和二进制数。

图2.2 十六进制数.png

在C语言中，以0x或者0X开头的数值常数被解释成十六进制数。字符A和字符F可写成大写或者小写。比如我们写数字 $FA1D37B$ 为oxFA1D37B或者oxfa1d37b等。在本书中，将使用C语言的记号来表示16进制数。

机器码程序的常见的任务是手动在十进制、二进制、16进制间转换。二进制和16进制的转换非常直接，因为可一次对一个十六进制数做转换。可参考图2.2中的表格来对数字做转换。在脑海中做转换时的一个简单的技巧是：记住十六进制数A、C、F对应的十进制数。十六进制数B、D、F可通过计算其相对A、C、F的值来做转换。

比如，假设给你一个数0x173A4C。你可通过展开每个十六进制数来将该数转换成二进制格式，该十六进制数对应的二进制表示为000101110011101001001100。

0x173A4C.png

反过来，给定一个二进制数1111001010110110110011，通过按照每4位分成一组，你可以将该数转换成十六进制。注意，如果整个数的位数不是4的整数倍，则你应该给最左一组的数的前面补0。然后将每个位组转换成相应的十六进制数：

2to16.png

当x是2的幂次方时，即存在某个非负整数n使得 $x=2^n$ ，则x的十六进制形式很容易写：只要记住x的二进制表示是1后面跟n个0。由于十六进制的0表示4个二进制的0。所以，对可表示成i+4j的n，其中 $0\leq i\leq 3$ ，则 $x=2^{i+4j}=2^i\times (2^4)^j$ 的十六进制形式为开头数字为十六进制数1(i=0)或者2(i=1)或者4(i=2)或者8(i=3)，后跟j个十六进制的0。比如，对于 $x=2048=2^{11}$ ，有 $n=11=2\times 4+3$ ，则x的十六进制形式为0x800。

十进制跟十六进制之间的转换需要使用乘法或者除法来处理一般情形。为了将十进制数x转换成16进制，我们首先把x除以16，得商为q，余数为r，使得 $x=q\times 16+r$ 。然后使用r作为16进制表示的最低位，且对商q重复执行前述过程得到剩余的16进制数字。比如，将十进制数314,156转换为16进制的过程为：

314,156 = 19,634*16 + 12(C)
19634 = 1,227*16+2(2)
1,227 = 76*16+11(B)
76=4*16+12(C)
4=0*16+4(4)

从上可知：十进制数314,156的十六进制形式为0x4CB2C。

相反，为了将16进制数转成十进制数，则用每个16进制数乘以适当的16的幂次方。比如，对于16进制数0x7AF，相应的十进制数为 $7\times 16^2+10\times 16^1+15=7\times 256+10\times 16+15=1,967$ 。

第2.1.2小节数据大小

每台计算机都有一个字大小，用来表示指针类型数据的标准大小。因为一个虚拟地址是由一个字编码的，所以由字大小确定的最重要的系统参数就是虚拟地址空间的最大值。也就是说，对于一台字大小为w位的机器，它的虚拟地址的范围是从 $0$ 到 $2^{w}-1$ ，即一个程序最多能访问 $2^w$ 个字节。

最近这些年，有很多从32位字大小的机器到64位字大小机器的迁移。首先发生在为大规模科学计算应用和数据库应用上，然后是桌面机器和台式机器，最近发生在智能手机上。一台32位字长的机器限制了虚拟地址空间的大小为4GB，大约刚超过 $4\times 10^9$ 字节。一台64位字长的机器限制了虚拟地址空间的大小为16 exabytes，大约是 $1.84\times 10^{19}$ 字节。

大部分64位机器是向后兼容的，即也可以运行为32位机器编译的程序。比如，当一个程序prog.c是用下面指令编译的：

linux> gcc -m32 prog.c

然后该程序既能在32位机器上运行，也能在64位机器上运行。另一方面，使用如下指令编译的程序只能在64位机器上运行：

linux> gcc -m64 prog.c

由于区分是一个程序如何被编译，而不是它运行的机器类型，因此，我们将引用程序为32位程序或者64位程序。

计算机和编译器支持使用不同编码数据方式的多种数据格式，比如不同长度的整数、浮点数等。比如许多机器有操作单个字节的指令，也支持2字节整数、4字节整数、8字节整数，也支持4字节浮点数、8字节浮点数等。

C语言支持多种数据格式的整数、浮点数数据。图2.3展示了分配给C语言不同数据类型的字节的个数。某些数据类型的精确字节数取决于程序如何被编译。我们展示了典型的32位程序和64位程序。

C语言典型数据类型的大小.png

整数数据可以是能表示0、负数、正数的无符号数，也可以是仅允许非负数的无符号数。
char类型用一个字节表示。虽然名称char是从“char用来存储文本字符串中的单个字符”这个事实中推导出的，但是char类型也可用来存储整数值。
数据类型short、int、long旨在提供范围不同的数据。即使在64位机器上编译，数据类型int通常占4个字节。数据类型long在32位机器上是4个字节，在64位机器是8个字节。
为了避免依赖典型大小和不同编译器设置的麻烦，ISO C99标准引入了一类跟编译器和机器设置无关的、大小固定的数据类型，比如占4个字节的数据类型int32_t、占8个字节的数据类型int64_t等。对程序员来说，使用固定大小的数据类型是对数据格式进行严格控制的最好方式。
大部分机器也支持两种不同的浮点数格式：单精度和双精度，在C语言中分别声明为占4个字节的float、8个字节的double。
大部分数据类型都编码的是有符号整数，除非前缀有unsigned或者使用固定大小数据类型的具体无符号声明。此处有个例外：数据类型char。虽然大部分编译器和机器将数据类型char看做是有符号数据，但是C语言规范并没有提供这种保证。相反，根据方括号的提示，程序员应该使用声明signed char来保证一个字节的有符号值。但是，在许多上下文里，程序对数据类型char是有符号的还是无符号的并不敏感。
一个指针使用的是程序的整个字长。

C语言允许多多种方式来给关键字排序、包含或者省略可选关键字。比如，下面所有的声明都有相同的含义：

unsigned long
unsigned long int
long unsigned
long unsigned int

程序员应尽力使程序能跨平台和机器移植。可移植性的一个要求程序对不同数据类型的具体大小不敏感。

虽然C语言规范设置了不同数据类型的数值范围的下界，但是并没有设置上界，除了固定大小的数据类型外。从20世纪80年代到2010年，由于32位机器和32位程序是主流的组合，所以许多程序一直都是根据图2.3里的列出的32位假设分配而编写的。随着迁移程序到64位机器上，许多隐藏的字大小依赖会作为错误出现。比如，许多程序员历史性地假设一个声明为int数据类型的对象能用来存储指针。虽然这对于大部分32位程序是正确的，但是对64位程序会导致问题。

第2.1.3节地址和字节序

对于占据多个字节的程序对象，我们必须建立两个约定：

这个对象的地址是什么？
我们在内存中如何给字节排序？

从虚拟角度看，在所有机器上，一个多字节对象是作为连续的字节序列存储的，地址是所有字节地址的最小值。比如，假设变量x的类型为int，地址是0x100，即地址表达式&x的值是0x100。则x的4个字节依次被存储在内存位置0x100、0x101、0x102、0x103处。

对于表示对象的字节的顺序，有两种常用的约定。

小端机器
按照从最低有效字节到最高有效字节的顺序来在内存中存储对象；
大端机器
按照从最高有效字节到最低有效字节的在内存中存储对象；

假设一个有w位的整数，对应的二进制表示为 $[x_{w-1},x_{w-2},...,x_1,x_0]$ ，其中 $x_{w-1}$ 最高有效位， $x_0$ 是最低有效位。假设w是8的整数倍，则这些字节可按照字节分组，最高有效字节是 $[x_{w-1},x_{w-2},...,x_{w-8}]$ ，最低有效字节是 $[x_7,x_6,...,x_0]$ ，其他字节占据的是从中间开始的位。

示例

假设int类型的变量x的地址是0x100，x的十六进制值表示为0x01234567。从地址0x100到地址0x103存储的字节的顺序取决于机器类型：

大小端机器示例.png

注意：在字0x01234567中，最高序字节的16进制表示为0x01，最低序字节的16进制表示为0x67。

大部分兼容Intel处理器的机器都是小端机器。大部分IBM和Oracle机器都是大端机器。注意，我们说的是大部分。这种约定不是精确地按照公司为边界来划分的。比如，IBM和Oracle都制造使用兼容Intel处理器的机器，因此这些机器是小端机器。大部分最新代的微处理器都是大端的，意味着可通过配置来让它们运行在大端机器或者小端机器上。但是，在实践中，一旦某个操作系统被选定，字节序就确定下来了。比如，虽然ARM微处理器(被许多智能手机使用)有能以小端模式或者大端模式运行的硬件，但是适配这类芯片的两个最重要的操作系统(Android和IOS)只能以小端模式运行。

对大部分应用程序员来说，机器上的字节序对他们是不可见的；为任何一类机器编译的程序都给出同样的结果。但是，有时，字节序就会导致问题。

示例1 网络应用

当通过网络在不同类型的机器间来交流二进制数据时，字节序变得很重要。一种常见的问题就是将由小端机器产生的数据发送给大端机器，或者反过来。为了解决这类问题，为网络应用编写的应用必须遵守实现确定好的字节序约定，保证发送端将内部表示的数据转换成网络标准的数据，接收端机器将网络标准的数据转换成内部表示的数据。我们将在第11章里看到这种示例。

示例2 查看字节序列

当查看表示整数数据的字节序列时，字节的顺序变得很重要。当审视机器码程序时，这就会发生。下面一行文本表示的是针对Intel x86-64处理器生成的机器码：

  4004d3:  01 05 43 0b 20 00       add    %eax,0x200b43(%rip)

上面一行文本是由反汇编程序disassembler生成的。我们将在第3章中学习更多有关disassembler和如何解释这种机器码的知识。现在，我们简单地注意到：十六进制字节序列01 05 43 0b 20 00是add指令的字节级别的表示，这条add指令的操作是将一个字长的数据跟存储在当前PC值加上0x200b43的地址处的数据相加。如果将最后4个字节序列43 0b 20 00取反，则有00 20 0b 43。丢掉前面的0，则有0x200b43。当阅读为小端机器生成的机器码时，将字节逆序是一个常用的操作。写字节序列的自然方式是最低编号的字节在左，最高编号的字节在右，但这跟写数的顺序相反：最高有效数字位在左，最低有效位数字在右。

示例3 编写规避普通类型系统的程序

当编写需要规避普通类型系统的程序时，字节顺序就变得很重要。在C语言里，可通过强转cast或者联合union来允许根据一个对象创建时的不同数据类型来引用一个对象。虽然这种编程技巧令大部分应用程序员很失望，但是对系统级编程缺失非常有用且甚至是必要的。

图2.4展示了一段使用强转来访问和打印不同程序对象的字节表示的C代码。

#include <stdio.h>

typedef unsigned char *byte_pointer;

void test_show_bytes(int val);

int main()
{
    int val = 12345;
    test_show_bytes(val);
    return 0;
}

void show_bytes(byte_pointer start, size_t 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 *));
}

void test_show_bytes(int val){
    int ival = val;
    float fval = (float)val;
    int *pval = &ival;

    show_int(ival);
    show_float(fval);
    show_pointer(pval);
}

使用typedef定义了数据类型byte_pointer，该数据类型是一个指向unsigned char类型对象的指针。一个byte_pointer变量可引用一个字节序列，其中每个字节是一个非负数。
函数show_bytes的参数是一个字节序列的地址start，类型是byte_pointer以及字节计数，类型是size_t；
功能：以16进制打印单个字节；
.2x表示一个整数应该以16进制打印，至少得有两个数字；

函数show_int、show_float、show_pointer展示了如何使用函数show_bytes来打印C语言的int类型对象、float类型对象、void*类型对象的字节表示。观察到这三个函数传递给函数show_bytes的实参是指向参数x的指针&x，并将指针类型强转为类型unsigned char*。这里的强转给编译器透漏一个信号：程序应该考虑这个指针指向的是一个字节序列，而不是一个原数据类型的对象。然后这个指针指向的是程序对象占据的最低字节地址。

这3个函数使用C语言的sizeof运算符来判断程序对象占据的字节数。一般地，表达式sizeof(T)返回的是存储T类型对象所需的字节数。
使用sizeof而不是一个固定值，是朝着编写能跨不同机器类型移植的代码而跨出的一步。

我们使用如下的机器：

Linux 32
Windows
Sun
Linux 64

来运行图2.5给出的代码，然后结果在图2.6中给出。

图2.5 字节表示示例.png

图2.6 不同数据类型的字节表示.png

如图所示，我们使用的实参12345的16进制表示为0x00003039。

对于int类型数据，除了字节顺序外，我们在所有机器上得到的结果都一样。特别地是，我们能看到最低有效字节值0x39在Linux32/Windows/Linux64等小端机器上都是首先输出的，在Sun等大端机器上是最后被输出的。
对于float类型数据，除了字节顺序外，我们在所有机器上得到的结果都是相同的。
对于指针类型数据，在所有机器上的输出都不一样。不同的机器/操作系统配置使用了不同的存储分配约定。注意到：Linux32/Windows/Sun等机器使用的是4个字节的地址，而Linux64使用的是8个字节的地址。

观察到虽然附点数和整数数据都是对数值12345编码的，但是两者的字节模式却完全不同：整数字节模式为0x00003039，浮点数字节模式为0x4640E400。一般来说，这两种格式使用不同的编码格式。如果将这些十六进制模式拓展为二进制形式，并适当地平移，我们会发现有13个匹配的数位，如图所示：

模式匹配示例.png

注意这不是巧合。当我们研究浮点数格式时，我们将返回到这个示例。

第2.1.4小节字符串的表示

在C语言里的字符串被编码成一个字符数组后跟null字符(值为0)。每个字符使用某种标准编码表示，比如最常用的ASCII字符标准。

如果用参数"12345"和6调用show_bytes，则结果是31 32 33 34 35 00。

观察到：

十进制数x的ASCII码刚好就是0x3x；
结尾字节的十六进制表示为0x00；
在任何一个使用ASCII标准作为字符集的机器上，像上述调用都会得到相同的结果，跟字节序和字大小约定；

因此，文本数据要比二进制数据更具有可移植性。

第2.1.5 代码的表示

考虑如下的C函数：

int sum(int x, int y){
    return x + y;
}

在我们的样例机器上编译后，生成的机器码字节表示如下：

sum函数机器码.png

指令编码都是不同的；
不同的机器类型使用不同且不兼容的指令和编码；
即使在不同的操作系统上运行的一模一样的处理器在编码约定方面也是不同的，因此是二进制不兼容的；
二进制码很少能跨不同机器和操作系统的组合间可移植；

计算机系统的一个基本概念是从机器的角度看，程序就是字节序列。除可能有一些辅助表来帮助调试程序外，机器对源程序一无所知。

当在在第3章里研究机器码编程时，我们将更清晰地理解这一点。

第2.1.6节布尔代数简介

由于二进制数处在计算机如何编码、存储和操作信息的核心位置，所以围绕着0和1衍出了丰富的数学知识。这类知识从George Boole(1815-1864)在大约1850年的工作开始，因此称作布尔代数。布尔观察到通过将逻辑值TRUE和FALSE编码为1和0，他可以推导出一种能捕捉逻辑推断基本原理的代数。
最简单的布尔代数是基于集合 $\{0,1\}$ 。

图2.7里定义了布尔代数的若干种运算。我们选择的用于表示这些运算的符号是跟后面将要介绍的C语言的位级别运算相匹配的。

图2.7 布尔代数的4种运算.png

~p运算表示取反逻辑运算NOT
当p等于1时，~p的值是0；
当p等于0时，~p的值是1；
&运算表示逻辑运算与AND
有当p=1且q=1时，p&q的值是1
|运算表示或运算OR
当p=1或者q=1时，p|q值是1
^运算表示异或运算
当p=1，q=0或者p=0，q=1时，p^q的值是1

Claude Shannon(1916-2001)首次确立了布尔代数和数字逻辑之间的联系。在他1937年的硕士论文里，他展示了可将布尔代数应用到继电器网络的设计和分析中去。虽然从那时开始技术已取得了可观的进步，但是布尔代数仍在电子系统的设计和分析中扮演者核心的角色。

布尔代数拓展一：位向量运算

假设a表示 $[a_{w-1},a_{w-2},...,a_0]$ ，b表示 $[b_{w-1},b_{w-2},...,b_0]$ 。
定义a&b：

是一个长度为w的向量；
对于 $0\leq i< w$ ，有 $a_{i}\&b_{i}$ ；

定义a|b：

是一个长度为w的向量；
对于 $0\leq i< w$ ，有 $a_{i}|b_{i}$ ；

定义a^b：

是一个长度为w的向量；
对于 $0\leq i< w$ ，有 $a_i$ ^ $b_i$ ；

定义~a：

是一个长度为w的向量；
对于 $0\leq i< w$ ，有~ $~{a_i}$ ；

假设a=[0110]，b=[1100]，则a&b=[0100]，a|b=[1110]，a^b=[1010]，~ $~b$ =[0011]。

位向量的拓展一：表示有限集

使用位向量 $[a_{w-1},a_{w-2},...,a_1,a_0]$ 来对有限集合 $\{0,1,2,...,w-1\}$ 的任意一个子集A进行编码，满足： $a_i=1$ 当且仅当 $i\in A$ 。

假设位向量 $a=[01101001]$ 编码的集合 $A=\{0,3,5,6\}$ ，位向量 $b=[01010101]$ 编码的集合 $B=\{0,2,4,6\}$ 。

通过这种方式对集合编码，布尔代数运算|就表示集合的并，&运算表示集合的交，~ $~$ 运算表示集合的补。

则a&b=[01000001]就表示集合的交 $A\cap B=\{0,6\}$ 。

我们将看到使用位向量来编码集合的很多应用。

在第8章里，我们将看到若干个可以解释程序执行的信号。我们可通过设置一个掩码(在第i个位置有个1表明信号i有效，在第i个位置有个0表示信号i失效)位向量来有选择地使信号失效或者有效。

第2.1.7节在C语言中的位运算

与运算AND
运算符是&
或运算OR
运算符是|
非运算NOT
运算符是~
异或运算EXCLUSIVE-OR
运算符是^

位运算应用一：实现掩码操作

位运算常见的应用之一是实现掩码操作，其中掩码是一个位模式，表明目的是要选定一个字内的一组位。

掩码0xFF，即最低的8个有效位全是1，表明选定一个字的最低字节。位运算x&0xFF可产生一个由x的最低有效字节，且其他字节全是0的值。当x=0x89ABCDEF时，则x&0xFF的值就是0xEF。

问题2.12

假设x=0x87654321，w=32，
则：
A. 保留x的最低字节位，其余位都设置为0
x&0xFF
B. 除最低有效字节不变外，其余字节都取补

x^(~0xFF)

C.将x的最低有效位都设置为1，其余字节保持不变
x|0xFF

问题2.13

bis(x,y)等价于x|y
bic(x,y)等价于x&~y
根据x^y=(x&~y)|(y&~x)可知，x^y等价于bis(bic(x,y),bic(y,x))

示例1

位运算示例.png

根据示例可知，确定一个位级别表达式的效果的最好方法：

先将16进制转换成二进制
对二进制执行位运算
后将结果转换成16进制

问题2.10

对于任何一个位向量a有a^a=0成立。

void inplace_swap(int *x, int *y){
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

如名字所示，我们断言：该函数的作用是交换由指针变量x和y指向的位置存储的值。
注意：

跟通常使用的交换两个值的方式不一样，这个函数不需要第3个位置来临时存储值；
这种交换两个值的方式并没有性能上的优势；

问题2.11

源文件reverse_array.c

#include<stdio.h>

void inplace_swap(int *x, int *y);
void reverse_array(int a[], int cnt);

int main(void){
    // int i;
    // int a[] = {1,2,3,4};
    // int size = sizeof(a)/sizeof(a[0]);
    // for(i=0;i<size;i++){
    //  printf("%d ", a[i]);
    // }
    // printf("\n");

    // reverse_array(a, size);

    // for(i=0;i<size;i++){
    //  printf("%d ", a[i]);
    // }
    // printf("\n");

    int i;
    int a[] = {1,2,3,4,5};
    int size = sizeof(a)/sizeof(a[0]);
    for(i=0;i<size;i++){
        printf("%d ", a[i]);
    }
    printf("\n");

    reverse_array(a, size);

    for(i=0;i<size;i++){
        printf("%d ", a[i]);
    }
    printf("\n");
    // int i;
    // int a[] = {1,2,3,4};
    // for(i=0;i<4;i++){
    //  printf("%d ", a[i]);
    // }
    // printf("\n");

    // reverse_array(a, 4);

    // for(i=0;i<4;i++){
    //  printf("%d ", a[i]);
    // }
    // printf("\n");

    // int i;
    // int a[] = {1,2,3,4,5};
    // for(i=0;i<5;i++){
    //  printf("%d ", a[i]);
    // }
    // printf("\n");

    // reverse_array(a, 5);

    // for(i=0;i<5;i++){
    //  printf("%d ", a[i]);
    // }
    // printf("\n");
    return 0;
}

void inplace_swap(int *x, int *y){
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

void reverse_array(int a[], int cnt){
    int first, last;

    for(first=0,last=cnt-1;first<=last;first++,last--){
        if (first != last) {
            inplace_swap(&a[first], &a[last]);
        }

    }
}

第2.1.8节 C语言中的逻辑运算

C语言提供了逻辑运算符：

或运算||
且运算&&
非运算!

C语言的逻辑运算很容易跟位运算混淆，但是两者的行为是不同的。

逻辑运算用任何一个非0实际参数来表示TRUE，用0来表示FALSE。

逻辑运算返回1表示TRUE，0表示FALSE。

逻辑运算示例

逻辑运算示例.png

注意到：

仅当参数是0或者1时，逻辑运算的行为跟位运算与一致；
&&跟&、||跟|之间的区别是如果表达式的值可通过第一个参数确定下来，则逻辑运算符就不会对第二个参数求值。比如，a && 5/a永远不会出现对0做除法，p && *p++永远不会出现对空指针的反解析。

问题2.14

a=0x55=0101 0101，b=0x46=0100 0110，则：
a & b = 0x44
a | b = 0x57
~a | ~b = 0xBB
a & !b = 0x00
a&&b=0x01
a||b=0x01
!a||!b = 0x00
a&&~b=0x01

问题2.15

x==y等价于!(x^y)

第2.1.9节 C语言中的移位运算

C语言也提供用于将位模式向左和向右移动的移位操作：

左移操作<<
右移操作>>

左移操作

假设操作数x的位模式为 $[x_{w-1},x_{w-2},...,x_0]$ ，则C表达式x<<k的结果是 $[x_{w-k-1},x_{w-k-2},...,x_0,0,...,0]$ 。意味着

将x向左移动k位：丢掉原左边最有效的k个位，且在右边补上k个0。
平移量k的范围在0到w-1之间。
平移操作满足结合律，x<<j<<k等价于(x<<j)<<k

右移操作

假设操作数x的位模式为 $[x_{w-1},x_{w-2},...,x_0]$ ，则C表达式x<<k的结果有两种形式：

逻辑右移
一次逻辑右移操作会在左端填充k个0，结果是 $[0,..,0,x_{w-1},...,x_k]$ 。
算术右移
一次算术右移操作在左端填充的是原数的最高有效位，结果是 $[x_{w-1},...,x_{w-1},x_{w-1},x_{w-2},...,x_{k}]$ 。

平移操作示例

平移操作示例.png

其中斜体的数字表示的是左移填充在右边的值，或者右移填充在左边的值。
观察到除了一项，所有的数填充的都是0。例外的是算术右移[10010101]。因为该数最高有效位是1，填充使用的值将是1。

C语言规范没有精确定义有符号数的右移操作类型。在实践中，几乎所有的编译器/机器组合对有符号数都使用算术右移，且许多程序员都是这么假设的。对于无符号数，必须使用逻辑右移。

Java语言规范明确定义右移操作的类型。

x>>k表示将x算术右移k位；
x>>>k表示将x逻辑右移k位；

第2.2节整数的表示

在这一节里，我们描述两种用来编码整数的方法：一种仅能表示非负整数，一种可表示负整数、0、正整数。后面我们将看到整数在计算机中表示的方式，跟计算机中整数的数学性质、机器实现紧密相关。我们也研究拓展或者截断一个编码整数来满足一个不同长度的表示。

图2.8列出了我们介绍的数学术语，用来精确定义和规范计算机如何编码和操作整数数据。

图2.8 整数数据和算术操作的数学术语.png

第2.2.1 整数数据类型

C语言支持多种整数数据类型，注意是一种能表示有限范围整数的数据类型。

图2.9展示的是32位程序的整数数据类型和范围。

用于32位程序的典型整数数据范围.png

图2.10展示的是64位程序的整数据类型和范围。

用于64位程序的典型整数数据范围.png

每种类型使用关键字char/short/int/long来指定大小，
默认的是有符号数，也可以使用unsigned来表明是无符号数，或者默认的是有符号数。

根据程序是被编译成32位还是64位，分配给不同大小的字节的个数是不一样的。

基于分配的字节数，不同的大小允许不同的数值范围。

唯一跟机器有关的范围是大小指示符long。大部分64位程序使用8个字节来表示long，比32位程序使用的4个字节表示的数值范围更广。

图2.9和图2.10展示的一个重要特征是数值范围不是对称的，负整数的范围要比正整数大1。当我们考虑如何表示负整数时，我们将看到数值范围不对称的原因。

C语言规范定义了每种数据类型必须能表示的数值的最小范围。

如图2.11所示的数值范围是小于等于图2.9和图2.10中的。特别的是，除了大小固定的数据类型外，我们看到的正整数和负整数的范围是对称的。

C语言规范提供的整数数据类型范围保证.png

回溯到16位机器的时代，数据类型int能用2个字节的数来实现。

long能用4个字节的数来实现，常见于32位程序。

大小固定的数据类型保证了数值范围刚好跟图2.9中给出的一样，包括负整数和正整数范围的对称。

第2.2.2小节无符号数编码

定理无符号数编码定义

对于向量 $\vec{x}=[x_{w-1},x_{w-2},...,x_0]$ ，有 $B2U_w=\sum_{i=0}^{w-1}x_i2^i$ 。

函数 $B2U_w$ 的作用是映射0和1组成的、长度为w的字符串为一个非负整数。

性质1 w个bit位能表示的无符号数值范围有多大？

最小的数是 $0$ ，位向量为 $[00...0]$ 。
最大的数是 $2^w-1$ ，位向量为 $[11...1]$ 。

因此，定义函数 $B2U_w$ 是映射 $B2U_w:\{0,1\}^w\rightarrow \{UMax_w\}$ ，其中 $UMax_w=\sum_0^{w-1}2^i=2^w-1$ 。

定理无符号数编码的唯一性

函数 $B2U_w$ 是一个双射。

二进制补码编码

对许多应用来说，我们希望能表示负数。有符号数最常见的计算机表示是二进制补码。

画外音：负数还有其他的表示形式。

通过将最高有效位解释为有负的权重，可定义有符号数的二进制补码形式。

记这种解释为函数 $B2T_w$ ，其中 $B2T$ 表示binary to two's complement。

定理二进制补码编码定义

对向量 $\vec{x}=[x_{w-1},x_{w-2},...,x_0]$ ，有 $B2T_w=x_{w-1}\times (-2^{w-1})+\sum_0^{w-2}x_i\times 2^i$

最高有效位 $x_{w-1}$ 是符号位，其权重为 $-2^{w-1}$ 。当符号位是1时，被表示的值是负整数。当符号位为0时，被表示的值为正整数。

性质1 使用w个位能表示的有符号数值范围有多大？

最小数为 $[10...0]$ ，即 $TMin_w=-2^{w-1}$ 。
最大数为 $[01...1]$ ，即 $TMax_w=2^{w-1}-1$ 。

因此，定义函数 $B2T_w$ 为映射 $B2T_w:\{0,1\}^w\rightarrow \{TMin_w,...,TMax_w\}$ 。

定理二进制补码的唯一性

函数 $B2T_w$ 是双射。

图2.14展示了若干种不同字大小的位模式和数值范围。

重要的数.png

前3行以 $UMax_w$ 、 $TMin_w$ 、 $TMax_w$ 的形式给出了能表示的数值范围。
后两行展示了 $-1$ 和 $0$ 的所有表示。注意， $-1$ 的位模式跟 $UMax$ 的位模式一模一样，数值 $0$ 在两种表示方法下的位模式都一样。

几个重要的观察：

二进制补码的数值范围不是对称的，即 $|TMin|=|TMax|+1$ ，其中 $TMin$ 没有对应的正整数。

这会导致二进制补码算术运算的一些奇怪的性质，可能会导致一些微秒的程序bug；
这种不对称的出现是因为一半的位模式(符号位为1的那些整数)用来表示负数，另一半的位模式(符号位为0的那些整数)用来表示非负数。因为0也是非负整数，所以二进制补码能表示的正整数的个数就比负整数少1。

无符号数的最大值=二进制补码最大值的2倍+1，即 $UMax=2TMax+1$ 。

可移植性建议：
虽然C语言规范并没有要求用二进制补码来表示有符号数，但几乎所有的机器都是这么做的。

不应该假定编码方式确定的任何一种特定数值范围，也不应该假定有符号数的某种特定表示。
编写许多程序都假设使用二进制补码来表示有符号数，且使用图2.9和2.10中展示的典型数值范围，且这些程序是能跨很大范围的机器和编译器移植的。
在C语言的头文件limit.h中定义了一系列的常数，用来限定编译器运行的特定机器上的不同整数数据类型的范围。比如limit.h定义了常数INT_MAX、INT_MIN、UINT_MAX分别描述了有符号数和无符号数的数值范围。
对于使用了二进制补码的机器，如果整数数据类型有w位，则INT_MAX、INT_MIN、UINT_MAX对应的值就是 $TMAX_w$ 、 $TMin_w$ 、 $UMax_w$ 。

Java有关整数数据类型范围和表示：

Java要求使用二进制补码表示整数数据类型，且范围跟如图2.10所示的64位机器一致；
在Java中，单字节的数据类型叫byte而不是char；
前述具体的规定是为了使得Java程序不论运行其的机器或者操作系统是什么行为都是一致的；

二进制补码示例

#include <stdio.h>

typedef unsigned char *byte_pointer;

void test_show_bytes(int val);
void show_bytes(byte_pointer start, size_t len);

int main()
{
    short x = 12345;
    short mx = -x;

    show_bytes((byte_pointer)&x, sizeof(short));
    show_bytes((byte_pointer)&mx, sizeof(short));
    return 0;
}

void show_bytes(byte_pointer start, size_t 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 *));
}

void test_show_bytes(int val){
    int ival = val;
    float fval = (float)val;
    int *pval = &ival;

    show_int(ival);
    show_float(fval);
    show_pointer(pval);
}

2.2.4小节无符号数和有符号数互转

C语言允许不同数值类型之间的强转。比如，假设声明变量x是int类型，u是unsigned类型。则表达式(unsigned)x的效果是将x的值转换成无符号值，表达式(int)u的效果是将u的值转换成有符号值。

问题1 有符号数转换成无符号数的效果是什么？
问题2 无符号数转换成有符号数的效果是什么？

从数学的角度看，一个人可以想象出若干种不同的转换方式。首先，我们希望保留两种形式能表示的任何一个值。其次，将一个负整数转换成无符号值可能会产生0。将一个太大而不能用二进制补码表示的无符号数转换可能会产生 $TMax$ 。

但是，对大部分的C语言实现来说，无符号数和有符号数之间的转换是基于位，而不是数值的。

示例1 short转成unsigned short

#include<stdio.h>

int main(void){
    short int v = -12345;
    unsigned short uv = (unsigned short)v;

    printf("v=%d, uv=%u\n", v, uv);

    return 0;
}

输出：

v=-12345, uv=53191

效果是保持位模式不变，修改位解释的方式；
从short到unsigned short的转换改变的是数值，无改变的是位模式；

示例2 unsigned转成signed

#include<stdio.h>

int main(void){
    unsigned u = 4294967295u;
    int tu = (int)u;

    printf("u=%u, tu=%d\n", u, tu);

    return 0;
}

输出：

u=4294967295, tu=-1

效果是位模式保持不变，改变的是位解释的方式；

大部分C语言实现在同样字长的条件下处理有符号数和无符号数之间转换的一般规则是数值可能改变，但位模式不变。

从数学角度分析下这种思想：
假设 $U2B_w$ 表示无符号数到二进制表示的映射， $T2B_w$ 表示有符号数到二进制表示的映射。

给定一个在 $0\leq x< UMax_w$ 中的x，则函数 $U2B_w$ 可唯一确定x的w位无符号表示。

给定一个在 $TMin_w\leq x\leq TMax_w$ 中的x，则函数 $T2B_w$ 可唯一确定x的w位二进制补码表示。

定义函数 $T2U_w=B2U_w(T2B_w(x))$ ，定义域是 $\{TMin_w,...,TMax_w\}$ ，值域是 $\{0,...,UMax_w\}$ 。

定义函数 $U2T_w=B2T_w(U2B_w(x))$ ，定义域是 $\{0,...,UMax_w\}$ ，值域是 $\{0,...,UMax_w\}$ 。

则 $T2U_{16}(-12345)=53,191$ ， $U2T_{16}=-12345$ 。
用十六进制表示16位模式 $0xCFC7$ 是 $-12345$ 的二进制补码表示，也是 $53191$ 的无符号表示。
$12345+53191=65536$ ，揭示了同一个位模式表示的有符号数和无符号数之间的关系。

$T2U_{32}(-1)=4,294,967,295$ ， $U2T_{32}(4,294,967,295)=-1$ 。即 $UMax$ 跟 $-1$ 有相同的位模式， $1+UMax_w=2^w$ 。

函数 $T2$ 描述了二进制补码数到无符号数的转换，函数 $U2T$ 表示无符号数到二进制补码数的转换。这两个函数描述了大部分C语言实现中的有符号数和无符号数之间的转换效果。

定理有符号数到无符号的转换

对于x满足 $TMin_w\leq x\leq TMax_w$ ，

当 $x<0$ 时， $T2U_w(x)=x+2^w$ ；

当 $x\geq 0$ 时， $T2U_w(x)=x$ ；

证明：
对位模式 $\vec{x}$ 来说，有 $B2U_w(\vec{x})-B2T_w(\vec{x})=x_{w-1}(2^{w-1}-(-2^{w-1}))=x_{w-1}2^w$ ，即 $B2U_w(\vec{x})=B2T_w(\vec{x})+x_{w-1}2^w$ 。因此，有： $T2U_w(x)=B2U_w(T2B_w(x))=x+x_{w-1}2^w$ ，其中当 $x$ 是负整数时， $x_{w-1}=1$ ；当 $x$ 是正整数时， $x=0$ 。

定理无符号数到有符号数的转换

对于 $u$ 满足 $0\leq u\leq UMax_w$ ，有：
当 $u\leq TMax_w$ 时，有 $U2T_w(u)=u$ ；
当 $u>TMax_w$ 时，有 $U2T_w(u)=u-2^w$ ；

证明：
根据方程2.1有：
$B2U=u_{w-1}\times(2^{w-1})+\sum_{i=0}^{w-2}u_i2^i$
根据方程2.3有：
$B2T=u_{w-1}\times(-2^{w-1})+\sum_{i=0}^{w-2}u_i2^i$
则有：
$U2T=B2U-u_{w-1}2^w=u_{w-1}\times(-2^w)+u$
即当 $u_{w-1}$ 是1时，表明 $u>TMax_w$ ；当 $u_{w-1}$ 是0时，表明 $u\leq TMax_w$ 。

总结一下：

当 $0\leq x<TMax_w$ 时，有 $T2U_w(x)=x$ ， $U2T_w(x)=x$ 。
在范围 $0\leq x<TMax_w$ 内的非负整数有相同的无符号表示和二进制补码表示。
对于不在该范围内的整数，转换要么是加上，要么是减去。
- $T2U_w(-1)=-1+2^w=UMax_w$ ，即映射离0最近的负整数为最大的无符号数。
- $T2U_w(TMin_w)=-2^{w-1}+2^w=2^{w-1}=TMax_w+1$ ，即映射最小的负整数为最大的正二进制补码数+1。
- $T2U_{16}(-12345)=-12345+65536=53191$ 。

第2.2.5小节在C语言中比较有符号数和无符号数

C语言规范不仅支持所有整数数据类型的无符号表示算术运算，也支持所有整数数据类型的二进制补码表示算术运算。

虽然C语言规范没有具体指定无符号数的表示方式，但是几乎所有的机器都使用二进制补码表示。

通常大部分数都默认是有符号的，比如声明常数12345或者0x1A2B等。
添加字母U或者u作为后缀会创造一个无符号数，比如12345U或者0x1A2Bu。

C语言规范允许无符号数和有符号数之间互转。

虽然C语言规范没有具体定义这种转换该如何进行，但是大部分系统都遵循“保持底层的位表示不变”这一规则。这一规则的效果相当于：

从无符号数到有符号数，使用函数 $U2T_w$ ；
从有符号数到无符号数，使用函数 $T2U_w$ ；

无符号数和有符号数之间的互转有两种形式：

显式强转
隐式转换

代码示例：显式强转

int tx, ty;
unsigned ux, uy;

tx = (int)ux;
uy = (unsigned) ty;

代码示例：隐式转换

当一个类型数赋值给另一个类型的数时，发生隐式转换：

int tx, ty;
unsigned ux, uy;

tx = ux;
uy = ty;

如何输出有符号数、无符号数？

%d：表示有符号数；
%i：表示无符号数；
%x：表示16进制表示；

注意：
由于函数printf不知道类型信息，所以可以使用%u来输出一个int类型值，使用%d来输出一个unsigned类型值。

代码示例：混合输出

#include<stdio.h>

int main(void){
    int x = -1;
    unsigned u = 2147483648;

    printf("x = %u = %d\n", x, x);
    printf("u = %u = %d\n", u, u);

    return 0;
}

输出：

x = 4294967295 = -1
u = 2147483648 = -2147483648

C语言处理包含有有符号数和无符号数组合的表达式的方式会导致若干个可能反直觉的结果。
当对一个有符号数和一个无符号数执行某个操作时，C语言约定：

先隐式地将有符号数强制转换成无符号数，然后假设操作数都是非负数来执行操作。

注意，虽然C语言的这个类型提升约定对标准算术运算没有影响，但是会导致诸如关系运算出现反直觉的结果。图2.9中展示了一些示例关系运算及其结果，当使用32位二进制补码形式表示数据类型int时。

C语言提升规则的效果示例.png

-1<0U的结果是0；
2147483647U>-2147483647-1；
2147483647>(int)2147483648U的结果是1；

第2.2.6小节拓展一个数的位表示

一种常见的操作是在不同字大小的整数间转换时，保留相同的数值。

当目标数据类型太小而不能表示源数据类型值时，就无法保证转换前后有相同的值。

但是，当从较小的字大小整数转换成较大的字大小整数时，通常都会保持转换前后有相同的值。

如何将无符号数转换成较大的数据类型？
定理使用0来拓展无符号数

定义 $\vec{u}=[u_{w-1},u_{w-2},...,u_0]$ 是长度为 $w$ 的向量， $\vec{u}'=[0,...,0,u_{w-1},u_{w-2},...,u_0]$ 是长度为 $w'$ 的向量，其中 $w'>w$ ，则 $B2U_w(\vec{u})=B2U_{w'}(\vec{u}')$

如何将二进制补码数转换成较大数据类型的数？
定理符号拓展

定义 $\vec{x}=[x_{w-1},x_{w-2},...,x_0]$ 是长度为 $w$ 的向量， $\vec{x}'=[x_{w-1},...,x_{w-1},x_{w-1},x_{w-2},...,x_0]$ 是长度为 $w'$ 的向量，其中 $w'>w$ ，则 $B2T_w(\vec{x})=B2T_{w'}(\vec{x'})$ 。

示例符号拓展和0拓展

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len);

int main()
{
    short sx = -12345;
    unsigned short usx = sx;
    int x = sx;
    unsigned ux = usx;

    printf("sx = %d:\t", sx);
    show_bytes((byte_pointer) &sx, sizeof(short));
    printf("usx = %u:\t", usx);
    show_bytes((byte_pointer)&usx, sizeof(unsigned short));
    
    printf("x = %d:\t", x);
    show_bytes((byte_pointer) &x, sizeof(int));
    printf("ux = %u:\t", ux);
    show_bytes((byte_pointer) &ux, sizeof(unsigned));
    return 0;
}

void show_bytes(byte_pointer start, size_t 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 *));
}

输出

sx = -12345:     c7 cf
usx = 53191:     c7 cf
x = -12345:  c7 cf ff ff
ux = 53191:  c7 cf 00 00

注意：
不同字大小的数据类型之间的转换和无符号数跟有符号数之间转换的顺序会影响程序的值。

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len);

int main()
{
    short sx = -12345;
    unsigned uy = sx;

    printf("uy = %u:\t", uy);
    show_bytes((byte_pointer) &uy, sizeof(unsigned));
    return 0;
}

void show_bytes(byte_pointer start, size_t 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 *));
}

输出

uy = 4294954951:     c7 cf ff ff

第2.2.7小节截断一个数的表示

定理无符号数的截断

假设 $\vec{u}=[u_{w-1},u_{w-2},...,u_0]$ 是一个长度为 $w$ 的位向量， $\vec{u}'=[u_{k-1},u_{k-2},...,u_0)]$ 是将向量 $\vec{u}$ 截断为长度为 $k$ 的
位向量；
假设 $u=B2U_w(\vec{u})$ ， $u'=B2U_w(\vec{u}')$ ；
则有 $u'=u\ mod\ 2^k$

定理二进制补码数的截断

假设 $\vec{x}=[x_{w-1},x_{w-2},...,x_0]$ 是一个长度为 $w$ 的位向量， $\vec{x}'=[x_{k-1},x_{k-2},...,x_0)]$ 是将向量 $\vec{x}$ 截断为长度为 $k$ 的
位向量；
假设 $x=B2T_w(\vec{x})$ ， $x'=B2T_w(\vec{x}')$ ；
则有 $x'=U2T_k(x\ mod\ 2^k)$

数的截断示例

#include<stdio.h>

int main(void){
    int x = 53191;
    short sx = (short) x;
    int y = sx;

    printf("sx = %d\n", sx);
    printf("y = %d\n", y);
}

输出

sx = -12345
y = -12345

第2.2.8小节对无符号数和有符号数的使用建议

如您所见，有符号数到无符号的隐式地转换会导致一些违反直觉的结果。违反直觉的特征通常会导致程序出错。看出与隐式转换相关的bug是极其困难的。原因是这种转换在代码中是没有明显的指示的，程序员经常忽略这种隐式转换效果。

我们已看到多个由无符号数算术运算的微秒特征以及有符号数到无符号数的隐式转换等导致的bug和漏洞。

避免这类bug的方法之一就是永远不要使用无符号数。实际上，除了C语言之外，很少有语言支持无符号数。显然，这些语言的设计者认为无符号数带来的麻烦会比价值跟多。比如，

Java仅支持有符号数，要求使用二进制补码算术来表示有符号数；
在Java中，通常的右移操作符>>表示算术右移操作，单独使用>>>表示逻辑右移操作。

无符号数的适用场合：

系统编程
由于地址通常也是无符号的，所以系统程序员发现无符号类型很有用。
不关心二进制位向量的数值解释
我们有时需要将一个单词打包成由多个布尔条件值的标记。
实现取模运算及多精度运算的数学包
当实现用于取模运算及多精度运算的数学包时，数字通常是用词数组来表示的。

第2.3节整数的算术运算

许多新手程序员惊讶地发现：

两个正数相加得出一个负数；
表达式x<y的结果跟x-y<0的结果不一样等；

这些看似违反直觉的性质都是由计算机做算术运算的有限性产生的。

第2.3.1小节无符号数加法

考虑两个非负整数 $x$ 和 $y$ ，满足 $0\leq x,y<2^w$ 。每个值都可用 $w$ 位的无符号数来表示。则和 $x+y$ 满足 $0\leq x+y\leq2^{w+1}-2$ ，完整表示和 $x+y$ 需要 $w+1$ 位。

比如，用4位来表示 $x$ 和 $y$ ，满足 $0\leq x,y\leq 15$ 。则x+y满足 $0\leq x+y\leq 30$ ，需要5位来表示。如果使用5位来表示 $x+y$ ，数 $z$ 满足 $0\leq z\leq 15$ ，则和 $x+y+z$ 满足 $0\leq x+y+z\leq 45$ ，完整表示需要6位来表示，以此类推。

数学上的加法运算导致的这种字大小不断变大的性质意味着不能对完整表示加法运算结果的字大小做限制。虽然诸如Lisp等编程语言，就支持任意大小的算术运算来允许任意大小的整数。但是更为常见的是，编程语言支持固定大小的算术运算，导致计算机上的诸如加法和乘法等算术运算是不同于数学上的整数算术运算的。

定义计算机上无符号数的加法运算

假设实参 $x$ 和 $y$ 满足 $0\leq x,y<2^w$ ， $+^u_w$ 表示将和 $x+y$ 截断为 $w$ 位长的结果的加法运算，且是一个无符号数。

定义 $+^u_w=(x+y)\ mod\ 2^w$ ，则 $+^u_w$ 的效果就是简单地丢弃掉和 $x+y$ 中所有权重大于 $2^{w-1}$ 的位。

比如， $x=9$ ，对应的4位表示为 $[1001]$ 。 $y=12$ ，对应的4位表示为 $[1100]$ 。则和 $x+y=21$ ，需要5位来表示 $[10101]$ 。如果丢掉最高位，则有 $[0101]=5$ ，等价于 $21\ mod\ 16=5$ 。

定理无符号数加法

假设x和y满足 $0\leq x,y<2^w$ ，则有：
当 $x+y<2^w$ 时，有 $x+^u_wy=x+y$ ；
当 $2^w\leq x+y<2^{w+1}$ ，有 $x+^u_wy=x+y-2^w$ ；

证明：

如果 $x+y<2^w$ ，则和 $x+y$ 的 $w+1$ 位表示的最高位是0，因此丢掉最高位的0，不会改变数值x+y。

如果 $2^w\leq x+y<2^{w+1}$ ，则和 $x+y$ 的 $w+1$ 位表示的最高位是1，因此丢掉最高位的0，等价于从和中减去 $2^w$ 。

定义溢出

如果整个整数结果不能适配数据类型的字大小限制，则表示发生了运算结果溢出。

当两个 $w$ 位的操作数的和大于等于 $2^w$ 时，则表示发生了溢出。

溢出示例：4位二进制表示

当 $x+y<16$ 时，没有溢出，即 $x+^u_4y=x+y$ ；
当 $x+y\geq 16$ 时，加法运算发生了溢出，结果等价于完整和减去16。

注意：执行C程序时，溢出通常不会认为是错误。

定理无符号数加法运算的溢出检测

假设 $x$ 和 $y$ 满足 $0\leq x,y\leq UMax_w$ ，令 $s=x+^u_wy$ ，则和 $s$ 发生溢出当且仅当 $s<x$ 或者 $x<y$ 。

证明：

如果和 $s=x+^u_wy$ 发生了溢出，则和 $x=x+y-2^w$ 。因为 $0\leq y<2^w$ ，所以 $(y-2^w)<0$ ，进而有 $s=x+(y-2^w)<x$
同理， $0\leq x<2^w$ ，所以 $(x-2^w)<0$ ，进而有 $s=y+(x-2^w)<y$

利用阿贝尔群的元素的逆的定义来看待无符号数的加法的逆运算：减法运算。

性质无符号数加法运算的性质
集合 $A=\{x是一个无符号整数:0\leq x<2^w\}$ 和运算 $+^u_w$ 一起构成了一个阿贝尔群。

证明：

封闭性
采用固定字长来表示无符号数加法运算的结果，保证了封闭性；
结合律
显然成立；
交换律
显然成立；
单位元
0
逆元
对于任何一个 $x$ 满足 $0\leq x<2^w$ ，存在逆元 $-^u_wx$ 满足：
当 $x=0$ 时， $-^u_wx=0$ ；
当 $0<x<2^w$ 时， $-^u_wx=2^w-x$ ；
因为 $0<2^w-x<2^w$ ，所以 $(2^w-x)+x=2^w=2^w-2^w=0$ 。

第2.3.2小节二进制补码加法运算

定义二进制补码加法

假设 $x$ 和 $y$ 满足 $-2^{w-1}\leq x,y\leq 2^{w-1}-1$ ， $x+^t_wy$ 表示将和 $x+y$ 截断为w位长的二进制补码数，则：
当 $x+y\geq 2^{w-1}$ 时，有 $x+^t_wy=x+y-2^w$ ；
当 $-2^{w-1}\leq x+y<2^{w-1}$ 时，有 $x+^t_wy=x+y$ ；
当 $x+y<-2^{w-1}$ 时，有 $x+^t_wy=x+y+2^w$ ；

第2.3.3小节二进制补码数的逆元

定义二进制补码数的逆元

假设 $x$ 满足 $TMin_w\leq x\leq TMax_w$ ， $-^t_wx$ 表示二进制补码数 $x$ 的逆元，则：
如果 $x=TMin_w$ ，则有： $-^t_wx=TMin_w$ ；
如果 $TMin_w<x\leq TMax_w$ ，则有： $-^t_wx=-x$ ；

第2.3.4小节无符号数的乘法运算

假设整数 $x$ 和 $y$ 满足 $0\leq x,y\leq 2^w-1$ ，可被表示成w位的无符号数，

则乘积 $x\cdot y$ 的范围是 $0$ 到 $(2^w-1)^2=2^{2w}-2^{w+1}+1$ ，最多需要 $2w$ 位来表示。

在C语言规范里，记 $x*^u_wy$ 表示无符号数的乘法的结果，取 $2w$ 位乘积的低 $w$ 位得到的值。

截断一个二进制补码数为w位等价于该值对 $2^w$ 取模。

定义无符号数的乘法 $x*^u_wy$

假设整数 $x$ 和 $y$ 满足 $0\leq x,y\leq UMax_w$ ，则：
$x*^u_wy=(x\cdot y)\ mod\ 2^w$

第2.3.5小节二进制补码数的乘法

假设整数 $x$ 和 $y$ 是 $w$ 位的二进制补码数，满足 $-2^{w-1}\leq x,y\leq 2^{w-1}-1$ ，则乘积 $x\cdot y$ 的范围在 $-2^{2w-2}+2^{w-1}$ 到 $2^{2w-2}$ 之间，其中 $-2^{2w-2}+2^{w-1}=-2^{w-1}\cdot (2^{w-1}-1)$ ， $2^{2w-2}=(-2^{w-1})\cdot (-2^{w-1})$ ，最多要用 $2w$ 位的二进制补码来表示。

在C语言规范里，定义有符号整数的乘积 $x*^t_wy$ 为一个 $w$ 位的二进制补码数，通过将 $2w$ 位的乘积截断为w位得到。

截断一个二进制补码数为 $w$ 位等价于首先计算该值对 $2^w$ 取模的值，然后将该无符号值转换成二进制补码数。

定义二进制补码数乘法

假设整数 $x$ 和 $y$ 是 $w$ 位的二进制补码数，满足 $TMin_w\leq x,y\leq TMax_w$ ，则有
$x*^t_wy=U2T_w((x\cdot y)\ mod \ 2^w)$

第2.3.6小节乘以常数

历史上，许多机器的整数乘法指令都是相当的慢，需要至少10个时钟周期，甚至在Intel i7 Haswell处理器上也需要3个时钟周期。
作为对比，诸如加法、减法、位运算、平移运算等整数运算都仅需要一个时钟周期。

因此，编译器使用的一项重要优化措施是使用平移和加法运算的组合来替换乘以常数因子。

思路是：首先考虑乘以2的幂次方的情况，然后推广到任意常数。

定义乘以2的幂次方

假设 $x$ 是一个无符号整数，可用位模式 $[x_{w-1},x_{w-2},...,x_0]$ 来表示，则乘积 $x2^k$ 可用 $[x_{w-1},x_{w-2},...,x_0,0,...,0]$ 来表示，其中右边有k个0。

推导

$B2U_{w+k}([x_{w-1},x_{w-2},...,x_0,0,...,0])=x_{w-1}2^{k+(w-1)}+x_{w-2}2^{k+(w-2)}+...+x_02^{k+0}+02^k+...+02^0$
$=\sum_{i=0}^{w-1}x_i2^{i+k}=[\sum_{i=0}^{w-1}x_i2^{i}]2^k=x2^k$

定理无符号数乘以2的幂次方

假设x和k是无符号的C变量，满足 $0\leq k<w$ ，则 $x*^u_w2^k=x<<k$ 。

定理二进制补码数乘以2的幂次方

假设x是C里的二进制补码数，k是无符号C变量，满足 $0\leq k<w$ ，则 $x*^t_w2^k=x<<k$ 。

鉴于整数乘法比平移和加法的开销大，所以许多C编译器尝试用平移、加法、减法等运算来替换常数乘以整数。

示例：x*14

$14=2^3+2^2+2^1$
$x*14=(x<<3)+(x<<2)+(x<<1)$ 用了3次平移和2次加法
$14=2^4-2^1$
$x*14=(x<<4)-(x<<1)$ 用了两次平移和一次减法

编译器是如何生成表达式`x*K`的代码的？

编译器将 $K$ 的二进制表示组织成交替出现的0和1： $[(0..0)(1...1)(0...0)\cdots(1...1))]$

考虑一组连续的1，开始位置是n，结束位置m，其中 $n\geq m$ 。如何计算这些位对乘积的影响？

形式A
$(x<<n)+(x<<(n-1))+\cdots (x<<m)$
形式B
$(x<<(n+1))-(x<<m)$

规律：

当 $n=m$ 时，选择形式A；
当 $n=m+1$ 时，随便选择；
当 $n>m+1$ 时，选择形式B；

第2.3.7小节除以2的幂次方

定义向下取整函数RoundDown

RoundDown(3.14)=3，RoundDown(-3.14)=-4，RoundDown(3)=3；

定义向上取整函数RoundUp

RoundUp(3.14)=4，RoundUp(-3.14)=-3，RoundUp(3)=3；

在大部分机器上的整数除法甚至比整数乘法还慢，需要至少30个时钟周期。

除以2的幂次方也能使用平移操作来实现，注意我们使用的是右平移而不是左平移，其中无符号数使用的是逻辑右移，二进制补码数使用的是算术右移。

整数除法经常是朝着0的方向四舍五入。

定理无符号数除以2的幂次方逻辑右移

对于无符号C变量x和k，满足 $0\leq k< w$ ，有：
$RoundDown(x/2^w)=x>>k$

图2.28展示了对无符号数 $12340$ 除以 $1=2^0$ 、除以 $2=2^1$ 、除以 $4=2^2$ 、除以 $16=2^4$ 、除以 $256=2^8$ 后的结果。

无符号数除以2的幂次方.png

定理二进制补码数除以2的幂次方算术右移向下取整

假设C变量x有二进制补码值x，变量k有无符号值k，满足 $0\leq k<w$ ，有：
$RoundDown(x/2^k)=x>>k$

图2.29展示了对负数 $-12340$ 应用算术右移不同的量并向下取整得到的结果。

二进制补码数算术右移向下取整.png

当k=1时，没有四舍五入；
当需要四舍五入时，平移导致的结果是向下取整；
当k=4时，结果是对 $-771.25$ 向下取整到 $-772$ ；

定理二进制补码数除以2的幂次方算术右移向上取整

假设C变量x有二进制补码值x，变量k有无符号值k，满足 $0\leq k<w$ ，有：
$RoundUp(x/2^k)=(x+(1<<k)-1)>>k$
核心思想：在平移前加上一个偏移量

图2.30展示了在执行算术右移操作前如何加上合适的偏移量会导致结果被正确的四舍五入。

二进制补码数除以2的幂次方.png

总结一下：

在一台使用算术右移的二进制补码机器上，可用C表达式(x<0 ? x+(1<<k)-1 : x) >> k来计算 $x/2^k$ 的值。

为什么大多数机器上既有逻辑右移，又有算术右移？
答：由于在大部分机器上的整数除法甚至比整数乘法还慢，需要至少30个时钟周期，需要用逻辑右移和算术右移来表示除以2的幂次方来减少开销。

注意：

跟乘法不一样，不能用除以2的幂次方来表示除以常数K；

第2.3.8小节对整数运算的最后想法

计算机执行的整数运算本质上是取模运算。
用来表示数的有限字长限制了可能的数值范围，运算结果可能会溢出。
二进制补码表示提供了一种巧妙的方式来表示负整数和正整数，同时跟执行无符号数运算有着相同的位级别实现：无论操作数是无符号形式还是二进制补码形式，诸如加法、减法、乘法甚至除法都有相同或者非常相似的位级别行为。
在C语言中有些约定会产生奇怪的结果，这些约定会导致一些难于识别和理解的程序错误。
unsigned数据类型虽然概念上很直接，但是可导致一些甚至不在有经验的程序员期望内的行为。
unsigned数据类型可能会以不期望的方式出现，比如编写整数常数、调用库函数等。

第2.4节浮点数

浮点数表示：

对诸如 $V=x\times 2^y$ 形式的有理数进行编码；
对于执行有非常大的数和非常接近0的数参与的计算很有用；
对实数运算的近似表示；

截止20世纪80年代，每家计算机制造商都针对附点数表示和浮点数运算制定了自己的约定，不是很担心运算的精确性，因为它们认为速度和容易实现要比数值精确更关键。

所有这些都随着1985年IEEE标准754的出现而发生改变，其中IEEE标准754是一个精心设计的、用于表示浮点数及其运算的标准。这项工作始于1976年：在Intel的赞助下设计8087芯片，为8086处理器提供浮点数支持。Intel雇佣了加利福尼亚大学伯克利分校的教授William Kahan作为顾问，来为未来的处理器设计浮点数标准。Intel允许Kahan加入IEEE。IEEE最终采取了跟Kahan为Intel设计的接近的标准。今天，几乎所有的计算机都支持IEEE浮点数标准。这极大地提高了科学计算应用程序的跨不同机器的可移植性。

在这一节里，我们

将看到如何将实数表示成IEEE浮点数形式；
将研究舍入问题，即当数字不能精确地用IEEE浮点数格式来表示，必须向上或者向下调整；
将研究浮点数加法、乘法、关系运算符的数学性质；
将看到IEEE浮点数是基于小型且一致的原理设计的，因此IEEE浮点数实际上是非常优雅，且容易理解的；

第2.4.4小节四舍五入

由于浮点数表示的数值范围和精度有限，所以浮点数运算只能近似于实数运算。

对于数 $x$ ，我们需要的是一种系统的方法，来查找可用所需的浮点数格式表示的、最接近 $x$ 的匹配值 $x'$ 的方法。这就是舍入操作。

舍入操作是一种查找用所需的浮点数格式表示、最接近 $x$ 的匹配值 $x'$ 的系统的方法。

一个关键的问题是定义介于两种可能性的中间值的舍入方向。比如现在有 $1.5$ 美元，想把它舍入到最近的美元，那么结果应该是 $1$ 美元还是 $2$ 美元。

一种替代的方法是维护实际数的下界和上界。比如可确定两个表示值 $x^-$ 和 $x^+$ 使得 $x$ 满足 $x^-\leq x\leq x^+$ 。

IEEE浮点数格式定义了四种不同的舍入模式。默认模式是寻找最近的匹配值，其他3种用于计算上界和下界。

舍入到偶数
朝0舍入
向上舍入
向下舍入

第2.4.5小节浮点数运算

第2.5节总结

计算机将信息编码成比特，通常组织成字节序列。
计算机使用不同的编码方法来表示整数、实数、字符串。
不同的计算机型号使用不同的约定来编码数、对多个字节数据内的字节进行排序。

C语言旨在容纳不同的字大小和数值编码。

大部分机器使用二进制补码表示来编码有符号数，使用IEEE标准754来编码浮点数。

从位级别上理解这些编码方法，以及算术运算的数学性质，对编写在全数值范围都能正确运行的程序非常重要。

由于编码使用的是有限长度，则计算机算术运算跟数学上的整数和实数运算有着不同的性质。编码的长度有限意味着：当结果超出表示范围时，结果就会溢出；当结果跟0.0如此的接近以致于被改成0时，浮点数值就发生了下溢。

跟真实的整数运算相比，C语言实现的有限整数运算有着奇怪的性质：

表达式 $x*x$ 的值可能是负数，因为溢出。

无符号数和有符号数的运算满足整数运算的大部分性质：

结合律；
交换律；
分配律；
允许编译器做许多优化，比如用平移操作、加法操作、减法操作来替换乘法运算；

浮点数表示通过将数编码成 $x\times 2^y$ 形式来近似表示实数。
IEEE 754标准提供了若干种不同的精度，其中最常用的是单精度和双精度。IEEE浮点数标准用特殊值来表示正负无穷、非数字。

使用浮点数算术必须非常小心，因为浮点数的范围有限、精度有限，且不遵守常用的数学性质，比如结合律(加法和乘法均不满足)、分配律(乘法不满足)。

第2章 信息的表示和操作

第2.1节 存储信息

第2.1.1小节 十六进制表示法

第2.1.2小节 数据大小

第2.1.3节 地址和字节序

示例