Chapter 2 - Representing and Manipulating Information

0 写在前面

应该是要开始第一个lab了

2026/08/21 终于看完了第一遍

2026/08/22 开始做Data Lab！

2026/08/25 做完Data Lab了，技巧要求确实比较高，不过总算是做完了，之后写一篇总结（希望别鸽

---

现代计算机存储并处理信息，这些信息以二值信号表示。这些二进制数字，或者bits(位)，形成了数字革命的基础。

人类有十个手指头，用十进制是很自然的（原来还有这层解释），但是在构建能存储并处理信息的机器上，二进制值做得更好。二值信号能够很容易地被表示、存储和传输，比如，可以表示为穿孔卡片上有没有洞、导线上是高电压还是低电压、磁场是顺时针还是逆时针。

对二值信号进行存储和执行运算的电子电路很简单且可靠，使得制造厂可以集成百万甚至数十亿这样的电路到一个单独的硅片上。

单个的bit并不是很有用，当我们把bit组合到一起并应用一些interpretation(解释)，即赋予不同的可能的bit的组合以含义，我们就能表示任意一个有限集里的元素（怎么感觉是离散数学的结论）。比如，用一个二进制数系统，我们可以用几组bit来编码非负数，使用标准的字符码，我们可以能对文档中的字母和符号纪念性编码，我们后面会讨论。

我们考虑三种重要的数字的表示方法，unsigned(无符号) 编码基于传统的二进制表示法，表示大于等于0的数字；two’s-complement(补码) 编码是表示 signed(有符号) 整数的普遍方式。floating-point(浮点数) 编码是表示实数的科学计数法的以2为基数的版本。计算机用这些不同的表示方法实现算术运算。

计算机的表示方法使用有限数量的bit去编码一个数字，因此导致了当结果太大而不能被表示时，一些操作可能会overflow(溢出)，例如，使用4个byte表示int类型的计算机，如果计算
200 * 300 * 400 * 500
就会得到-884901888

不过，整数的计算机运算满足许多整数运算的性质，比如乘法的结合律和交换律

int main()
{
	int a = (500 * 400) * (300 * 200);
	int b = ((500 * 400) * 300) * 200;
	int c = ((200 * 500) * 300) * 400;
	int d = 400 * (200 * (300 * 500));
	printf("a=%d\nb=%d\nc=%d\nd=%d", a, b, c, d);
	return 0;
}

虽然结果是错的，但都是-884901888

浮点运算有完全不同的数学性质，虽然溢出会产生特殊的值(正无穷)，但一组正数的乘积总是正的

// 以下代码来自ai
#include <stdio.h>
#include <math.h>   // 为了使用 isinf() 函数判断是否为无穷大

/*
浮点数在内存里由三部分组成：符号位 + 阶码（指数）+ 尾数（小数）。
IEEE 标准规定：当阶码（指数）全部为 1，且尾数全部为 0 时，
这个二进制串不再代表具体的数值，而是被硬件解读为“无穷大（Infinity）”
*/
int main() {
    // double 能表示的最大有限值大约是 1.8e308
    double a = 1e200;  // 10的200次方（极大）
    double b = 1e200;  // 10的200次方
    double c = a * b;  // 数学结果是 10的400次方，远超 double 上限！

    printf("浮点数实验：\n");
    printf("a = %e\n", a);
    printf("b = %e\n", b);
    printf("a * b = %e\n", c);   // 注意：这里打印出来的会是 "inf"

    // 检查一下它到底是不是正无穷
    if (isinf(c) && c > 0) {
        printf("✅ 结果确实是 +∞ （正无穷大）！\n\n");
    }
    return 0;
}

浮点数的表示的精度是有限的，所以浮点运算不可结合

int main()
{
	double b = 3.14 + 1e20 - 1e20;
	double c = 3.14 + (1e20 - 1e20);
	printf("b=%lf\nc=%lf", b, c);
    // b=0.000000
    // c=3.140000
	return 0;
}

整数运算和浮点数运算有不同数学性质是因为它们处理数字表示有限性的方式不同，整数的表示虽然只能编码一个相对较小的数值范围但表示是精确的，浮点数的表示只是近似的

1 Information Storage

Rather than accessing individual bits in memory, most computers use blocks of 8 bits, or bytes, as the smallest addressable unit of memory.

A machine-level program views memory as a very large array of bytes, referred to as virtual memory. Every byte of memory is identified by a unique number, known as its address, and the set of all possible addresses is known as the virtual address space. This virtual address space is just a conceptual image presented to the machine-level program.

In subsequent chapters, we will cover how the compiler and run-time system partitions this memory space into more manageable units to store the different program objects, that is, program data, instructions, and control information. Various mechanisms are used to allocate and manage the storage for different parts of the program This management is all performed within the virtual address space.

1.1 Hexadecimal Notation

1个字节由8个bit组成，二进制中，它的范围是00000000到11111111，十进制中是0到255

用十六进制表示比较方便，即00到FF

在C语言中，以0x或0X开头的数字常量被认为是十六进制的值，比如0xFA1D37B

二进制转十六进制，整数部分从右往左四个一组，不够可以补0，然后对应到十六进制，小数部分从左往右四个一组，不够可以补0，然后对应到十六进制

例1
已知$x=2^n$，将$x$写成十六进制的形式，其中$n=i+4j, 0\le i\le 3$

$x$的二进制形式是1后面跟$n$个0，所以$x$的十六进制是$2^i$后面跟$j$个0

例如，$2^{11}$写成十六进制是$0x800$

例2
将188转为十六进制

和十进制转二进制一样，一直除以16，直到余数为0，倒着读得到$0xBC$

1.2 Data Sizes

Every computer has a word size(字长), indicating the nominal(标称) size of pointer data. Since a virtual address is encoded by such a word, the most important system parameter determined by the word size is the maximum size of the virtual address space.

对于一个字长为$w$位的机器，虚拟地址的范围就是0到$2^w-1$，程序最多能访问$2^w$个字节。我们平常说的64位机器，就是指64位字长机器。

大多数64位机器也可以运行为32位机器编译的程序，这是一种向后兼容。

计算机和编译器支持使用不同方式编码（或者不同长度编码）数据的多种数据形式，比如整数和浮点数。
例如，许多机器有能处理单个字节(比如C语言的char)的指令，也有能处理用2个、4个或8个byte表示的整数的指令，也有处理用4个、8个byte表示的浮点数的指令。

在C语言中，整数可以是signed，也可以是unsigned，前者可以表示正数、0、负数，后者只能表示非负数。数据类型char表示一个单独的字节，虽然char这个名字源于它用来存储一个字符，但它也可以存整数。

int, short, long提供各种数据的不同大小，即使是为64位系统编译，int类型通常只有4个字节，long一般在32位程序中为4字节，在64位程序中为8字节。

To avoid the vagaries(奇怪行为) of relying on “typical” sizes and different compiler settings, ISO C99 introduced a class of data types where the data sizes are fixed regardless of compiler and machine settings.

Among these are data types int32_t and int64_t, having exactly 4 and 8 bytes, respectively. Using fixed-size integer types is the best way for programmers to have close control over data representations.

大部分数据类型都编码为有符号数值，除非前面有关键字unsigned，例外是char，尽管大多数编译器和机器将大部分数据类型视为有符号数，不过对于char，这点并不保证，即默认下有可能是无符号也可能是有符号的，可以用signed char或unsigned char明确指出，不过一般char有无符号没什么关系。

程序员应力图使他们的程序在不同的机器和编译器上可移植(portable)，可移植性的一个特点就是程序对不同数据类型的确切大小不敏感。

比如，之前32位机器广泛使用，许多程序员以为一个int类型的对象可以存储指针，这在64位的机器上会导致问题。

1.3 Addressing and Byte Ordering

For program objects that span multiple bytes, we must establish two conventions: what the address of the object will be, and how wewill order the bytes in memory. In virtually all machines, a multi-byte object is stored as a contiguous sequence of bytes, with the address of the object given by the smallest address of the bytes
used.

For example, suppose a variable x of type int has address 0x100; that is, the value of the address expression &x is 0x100. Then (assuming data type int has a 32-bit representation) the 4 bytes of x would be stored in memory locations 0x100, 0x101, 0x102, and 0x103.

排列用于表示对象的字节，有两种方式。
考虑一个$w$位的整数，用bit表示，即[$x_{w-1}, x_{w-2}, ... , x_1, x_0$]
$x_{w-1}$是最高位，$x_0$是最低位，假设$w$是8的倍数，那么最高字节包含位[$x_{w-1}, ... , x_{w-8}$]

一些机器选择在内存中按照从最低字节到最高字节的顺序存储对象，另一些机器按照从最高字节到最低字节的顺序存储，前者称为little endian(小端法)，后者称为big endian(大端法)

对大多数程序员来说，机器所使用的字节顺序是不可见的，无论为哪种类型的机器所编译的程序都会得到同样的结果，不过有时候字节顺序会成为问题

1. 不同类型的机器间通过网络传送二进制数据式，小端法机器产生的数据被发送到大端法机器或者反过来时，接收程序会发现字里的字节是反序的
2. 阅读表示整数数据的字节序列时，字节顺序也很重要，先省略，如果后面没讲再写
3. 当编写规避正常的类型系统的程序时，比如C语言中强制类型转换等，这种编码技巧及其不推荐，但它们对系统级编程是非常有用的

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    // size_t expresses the sizes of data structures(单位：byte)
    for(i = 0; i < len; ++i)
    {
        printf(" %.2x", start[i]);
        // %.2x indicates that an integer should be printed in hexadecimal with at least 2 digits
    }
    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 *));
}

int main()
{
    int value = 12345;
    float fvalue = (float) value;
    int *pvalue = &value;
    show_int(value);
    show_float(fvalue);
    show_pointer(pvalue);
    return 0;
}

12345的十六进制表示是0x00003039
可以看到Sun是一个采用大端法的机器，其余都是使用小端法，先存储最低字节

1.4 Representing Strings

A string in C is encoded by an array of characters terminated by the null(having value 0) character.Each character is represented by some standard encoding, with the most common being the ASCII character code.

注意字符串的存储没有最高字节最低字节之分，字节顺序是固定的，例如，在使用ASCII码作为字符码的任何系统上，show_bytes("12345", 6);得到的结果都是31 32 33 34 35 00

1.5 Representing Code

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

When compiled on different machines, the generated machine codes are different.

Different machine types use different and incompatible(不兼容的) instructions and encodings. Even identical processors running different operating systems have differences in their coding conventions and hence are not binary compatible.

Binary code is seldom portable across different combinations of machine and operating system. A fundamental concept of computer systems is that a program, from the perspective of the machine, is simply a sequence of bytes. The machine has no information about the original source program, except perhaps some auxiliary(辅助的) tables maintained to aid in debugging.

1.6 Introduction to Boolean Algebra

Since binary values are at the core of how computers encode, store, and manipu
late information, a rich body of mathematical knowledge has evolved around the study of the values 0 and 1.

The simplest Boolean algebra is defined over the two-element set {0, 1}.

与、或、非、异或

We can extend the four Boolean operations to also operate on bit vectors, strings of zeros and ones of some fixed length $w$.

The Boolean operations |, &, and ~ operating on bit vectors of length $w (w > 0)$ form a Boolean algebra.

布尔代数也有很多和对整数运算相同的性质，比如分配律

When we consider operations ^, &, and ~ operating on bit vectors of length $w$, we get a different mathematical form, known as a Boolean ring(布尔环). Boolean rings have many properties in common with integer arithmetic. For example, one property of integer arithmetic is that every value $x$ has an additive inverse $−x$, such that $x + −x =0$. A similar property holds for Boolean rings, where ^ is the “addition” operation, but in this case each element is its own additive inverse. That is, a ^ a = 0 for any value $a$, where we use 0 here to represent a bit vector of all zeros. We can see this holds for single bits, since 0^0 = 1^1 = 0, and it extends to bit vectors as well. This property holds even when we rearrange terms and combine them in a different order, and so (a ^ b)^ a = b.

1.7 Bit-Level Operations in C

One useful feature of C is that it supports bitwise(按位的) Boolean operations.

例1

利用a^a=0，我们可以设计一个不需要第三个变量的交换函数

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

Step	*x	*y
Initially	a	b
Step 1	a	a^b
Step 2	a^a^b = 0^b = b	a^b
Step 3	b	b^a^b = (b^b)^a = a

其实异或符合交换律

例2

利用例1的函数，我们设计一个将数组元素倒置的函数

void reverse_array(int a[], int cnt)
{
    int first. last;
    for (first=0, last=cnt-1; first <= last; first++, last--)
    {
        inplace_swap(&a[first], &a[last]);
    }
}

如果数组的元素个数是偶数个，最中间的元素由于自己和自已异或，会变成0，所以应该修改为first < last

One common use of bit-level operations is to implement masking(掩码) operations, where a mask is a bit pattern that indicates a selected set of bits within a word. As an example,the mask 0xFF (having ones for the least significant 8 bits) indicates the low-order byte of a word. The bit-level operation x & 0xFF yields a value consisting of the least significant byte of x, but with all other bytes set to 0. For example, with x = 0x89ABCDEF, the expression would yield 0x000000EF.

The expression ~0 will yield a mask of all ones, regardless of the size of the data representation(即不管字的大小是多少). The same mask can be written 0xFFFFFFFF when data type int is 32 bits, but it would not be as portable.

Problem 1
写出关于x的C语言表达式，x = 0x87654321
你的代码对于字长大于等于8 bit的机器都要成立，方括号以字长为32 bit为例

A. All but the least significant byte of x complemented, with the least significant byte left unchanged. [0x789ABC21]

B. The least significant byte set to all ones, and all other bytes of x left un
changed. [0x876543FF]

A. x ^ ~0xFF
B. x | 0xFF

1.8 Logical Operations in C

C also provides a set of logical operators ||, &&, and !. These can easily be confused with the bit-level operations, but their behavior is quite different. The logical operations treat
any nonzero argument as representing TRUE and argument 0 as representing FALSE. They return either 1 or 0, indicating a result of either TRUE or FALSE, respectively.

The logical operators do not
evaluate their second argument if the result of the expression can be determined
by evaluating the first argument. Thus, for example, the expression a && 5/a will never cause a division by zero, and the expression p && *p++ will never cause the dereferencing(解引用) of a null pointer.

Problem 2
Using only bit-level and logical operations, write a C expression that is equivalent to x == y.In other words, it will return 1 when x and y are equal and 0 otherwise.

! (x ^ y)
因为如果x和y相同，那么x^y就会得到全0，也就是0，!0得到1

1.9 Shift Operations in C

C also provides a set of shift(移位) operations for shifting bit patterns to the left and to the right.

For an operand x having bit representation [$x_{w−1},x_{w−2},...,x_0$], the C expression x << k yields a value with bit representation [$x_{w−k−1},x_{w−k−2},...,x_0,0,...,0$]. That is, x is shifted k bits to the left, dropping off the k most significant bits and filling the right end with k zeros. The shift amount should be a value between 0 and $w−1$. Shift operations associate from left to right, so x << j << k is equivalent to (x << j) << k.

Generally, machines support two forms of right shift.

1. Logical. A logical right shift fills the left end with $k$ zeros.
2. Arithmetic. An arithmetic right shift fills the left end with $k$ repetitions of the most significant bit.

C语言标准没有明确定义对于有符号数应该使用哪种类型的右移，所以如果假设一种或者另一种右移形式的代码可能会遇到可移植性问题。实际上，几乎所有的编译器/机器组合都对有符号数使用算术右移。对无符号数，一定是逻辑右移。

如果移位数值很大会怎么样
对于$w$位的数据类型，如果要移动$k\ge w$位会怎么样呢？
C语言标准规避了说明这种情况下该如何做，在许多机器上，移动一个$w$位的值时，移位指令只考虑位移量的低$log_2w$位，比如$w=32$时，只考虑位移量的低5位，也就是只可能移动0~31位，如果$k=40$，即101000，只看01000，即移动8位，这等效于移动$k mod w$位。
不过这种行为对于C程序是没有保证的，而Java就是按这种行为计算。

移位运算的操作符优先级
加减法的优先级比移位运算高，不确定时可以加上括号。

2 Integer Representations

In this section, we describe two different ways bits can be used to encode integers — one that can only represent nonnegative numbers, and one that can represent negative, zero, and positive numbers.

2.1 Integral Data Types

C supports a variety of integral data types — ones that represent finite ranges of integers.

Each type can specify a size with keyword char, short, long, as well as an indication of whether the represented numbers are all nonnegative (declared as unsigned), or possibly negative (the default.)

2.2 Unsigned Encodings

Let us consider an integer data type of $w$ bits. We write a bit vector as either $\vec{x}$ to denote the entire vector, or as [$x_{w−1},x_{w−2},...,x_0$] to denote the individual bits within the vector. Treating $\vec{x}$ as a number written in binary notation, we obtain the unsigned interpretation of $\vec{x}$.

等号上加一个点意思是左边被定义成等于右边，函数$B2U_w$是Binary to Unsigned的缩写，长度为$w$，它将一个长度为$w$的0、1串映射到非负整数，计算方法就是把0、1串看作二进制表示，例如$B2U_4([0101]) = 2^2 + 2^0 = 5$

Function $B2U_w$ is a bijection.
双射的意思是一一对应，不了解的读者可以自行搜索了解，即在$0$到$2^w-1$之间的整数的$w$位无符号编码是独一的

2.3 Two’s-Complement Encodings

For many applications, we wish to represent negative values as well. The most common computer representation of signed numbers is known as two’s-complement(补码) form. This is defined by interpreting the most significant bit of the word to have negative weight. We express this interpretation as a function $B2T_w$ (for “binary to two’s complement” length $w$).

For $\vec{x} = [x_{w-1}, x_{w-2}, ..., x_0]$ :

$$B2T_w(\vec{x})\doteq -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2} x_i2^i$$

The most significant bit $x_{w-1}$ is also called the sign bit(符号位)

例如，$$B2T_4([1011]) = -2^3 + 2^1 + 2^0 = -5$$
同样地，$B2T_w$也是个双射，它的范围是$-2^{w-1}$到$2^{w-1}-1$，我们定义$T2B_w$作为它的反函数

补码编码中，符号位为1的编码表示负数，符号位为0的编码表示非负数，所以负数的范围比正数多一个数，而无符号数和补码在位一样的情况下表示的数的个数是一样多的，所以补码中的负数在无符号表示中都变成了正数有$UMax_w = | TMin_w | + TMax_w = 2TMax_w + 1$

The C standards do not require signed integers to be represented in two’s
complementform, but nearly all machines do so.

There are two other standard representations for signed numbers.

One’s complement(反码).

$$B2O_w(\vec{x}) \doteq -x_{w-1}(2^{w-1}-1) + \sum_{i=0}^{w-2} x_i 2^i$$

可以看到，反码表示下，正数的反码表示逐位取反就是相反数的反码表示，比如0111表示7，1000表示-7

Sign-Magnitude(原码)
最高有效位是符号位，来决定是正数还是负数

$$B2S_w(\vec{x}) \doteq (-1)^{x_{w-1}}\sum_{i=0}^{w-2} x_i 2^i$$

但这两种表示方法都有一个奇怪的属性，就是0有两种编码方式，以4位为例，反码中，0000和1111都是0，原码中，0000和1000都是0，更准确地说，后面那个(1111和1000)是-0

2.4 Conversions between Signed and Unsigned

C allows casting between different numeric data types. For example, suppose variable x is declared as int and u as unsigned. The expression (unsigned)x converts the value of x to an unsigned value, and (int)u converts the value of u to a signed integer.

For most implementations of C, the effect of casting is to keep the bit values identical but change how these bits are interpreted.

short int v = -12345;
unsigned short uv = (unsigned short) v;
printf("v = %d, uv = %u\n", v, uv);
// Output:
// v = -12345, uv = 53191

unsigned int u = 4294967295u; /* UMax */
int tu = (int)u;
printf("u = %u, tu = %d\n", u, tu);
// Output:
// u = 4294967295, tu = -1

int x = 0xffffffffu;
printf("%u %d", x, x);
// Output:
// 4294967295 -1

For $x$ such that $TMin_w\le x\le TMax_w$ :

$$T2U_w(x) = x, x\ge 0$$

$$T2U_w(x) = x + 2^w, x < 0$$

如果$x$是正数，补码表示下最高位一定是0，和无符号编码一样，如果$x$是负数，$x = -2^{w-1} + y$，而同样的二进制表示下，无符号编码的解释下，$x = 2^{w-1} + y$，于是$x_U = x_T + 2^w$

For $u$ such that $0\le u\le UMax_w$ :

$$U2T_w(u) = u, u\le TMax_w$$

$$U2T_w(x) = u - 2^w, u > TMax_w$$

2.5 Signed versus Unsigned in C

Although the C standard does not specify a particular representation of signed numbers, almost all machines use two’s
complement. Generally, most numbers are signed by default. For example, when declaring a constant such as 12345 or 0x1A2B, the value is considered signed. Adding character ‘U’ or ‘u’ as a suffix creates an unsigned constant; for example, 12345U or 0x1A2Bu.

When printing numeric values with printf, the directives %d, %u, and %x are used to print a number as a signed decimal, an unsigned decimal, and in hexadecimal format, respectively. Note that printf does not make use of any type information, and so it is possible to print a value of type int with directive %u and a value of type unsigned with directive %d.

int tx, ty;
unsigned ux, uy;
ty = -1;
ux = pow(2, 31);

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

tx = ux; /*Cast to signed*/
uy = ty; /*Cast to unsigned*/

printf("tx = %d, uy = %u", tx, uy);

// Output:
// ux = 2147483648 = -2147483648
// tx = -2147483648, uy = 4294967295

In printf("ux = %u = %d\n", ux, ux);, printf prints the word first as if it represented an unsigned number and second as if it represented a signed number.

---

When an operation is performed where one operand is signed and the other is unsigned, C implicitly casts the signed argument to unsigned and performs the operations assuming the numbers are nonnegative.

It leads to nonintuitive results for relational operators such as < and >.

Looking at the C header file limits.h, we see that they use a similar method as we have to write $TMin_{32}$ and $TMax_{32}$ :

/* Minimum and maximum values a 'signed int' can hold. */
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX-1)

2.6 Expanding the Bit Representation of a Number

One common operation is to convert between integers having different word sizes while retaining the same numeric value. Of course, this may not be possible when the destination data type is too small to represent the desired value. Converting from a smaller to a larger data type, however, should always be possible.

To convert an unsigned number to a larger data type, we can simply add leading zeros to the representation; this operation is known as zero extension(零扩展).

For converting a two’s-complement number to a larger data type, the rule is to perform a sign extension(符号扩展), adding copies of the most significant bit to the representation.

short sx = -12345;       /*-12345*/
unsigned short usx = sx; /* 53191*/
int x = sx;              /*-12345*/
unsigned ux = usx;       /* 53191*/

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 int));

// Output:
/* 
When run as a 64-bit program on a little-endian machine
that uses a two's complement representation.
*/
// sx = -12345:     c7 cf
// usx = 53191:     c7 cf
// x = -12345:      c7 cf ff ff
// ux = 53191:      c7 cf 00 00

可以用数学归纳法证明符号扩展不改变数值

需要注意的是，一个数据大小到另一个数据大小的转换以及无符号和有符号数间的转换，转换的相对顺序能影响一个程序的行为

short sx = -12345;
unsigned uy = sx;
printf("uy = %u:\t", uy);
show_bytes((byte_pointer)&uy, sizeof(unsigned));

// Output:
// uy = 4294954951:         c7 cf ff ff

这表明把short转换成unsigned时，先改变大小变为int，再从有符号数转为无符号数
即(unsigned) sx等价于(unsigned) (int) sx

2.7 Truncating Numbers

int x = 53191;        /* c7 cf 00 00 */
short sx = (short) x; /* -12345 */
int y = sx;           /* -12345 */

Casting x to be short will truncate(截断) a 32-bit int to a 16-bit short. As we saw before, this 16-bit pattern is the two’s-complement representation of −12,345. When casting this back to int, sign extension will set the high-order 16 bits to ones, yielding the 32-bit two’s-complement representation of −12,345.

当将一个$w$位的数截断成一个$k$位数时，我们会丢弃高位的$w-k$位

截断无符号数
对于$w$位的数$\vec{x}$，截断成$k$位的$\vec{x'}$，令$x = B2U_w(\vec{x}), x' = B2U_k(\vec{x'})$，则

$$x' = x \ mod \ 2^k$$

截断补码数
对于$w$位的数$\vec{x}$，截断成$k$位的$\vec{x'}$，令$x = B2U_w(\vec{x}), x' = B2T_k(\vec{x'})$，则

$$x' = U2T_k(x \ mod \ 2^k)$$

对于截断剩下的bit串（或者说位向量$\vec{x'}$），把它先转成无符号数，再转成补码表示的数，实际上是

$$x' = B2T_k(\vec{x'}) = U2T_k(B2U_k(\vec{x'})) = U2T_k(x\ mod\ 2^k)$$

2.8 Advice on Signed versus Unsigned

Problem 3
考虑下面的代码，当length等于0时，会出现内存错误，为什么？

/* This is buggy code */
float sum_elements(float a[], unsigned length) {
    int i;
    float result = 0;
    for (i = 0; i <= length - 1; i++) {
        result += a[i];
    }
    return result;
}

当length等于0时，length - 1是用无符号数的算术方法来计算的，0 - 1会得到$UMax$，而比较也是用无符号数的方式来比较，所以i <= length - 1总是成立，应该改为i < length

3 Integer Arithmetic

3.1 Unsigned Addition

如果两个非负整数$x, y$，它们大于等于0小于$2^w$，那么它们的和可能为$2^{w+1} - 2$，因此，无符号数作加法时，位数不能有上限

我们为参数$x, y$定义运算$+^u_w$，其中$0\le x, y < 2^w$，这个运算是把整数和$x+y$截断为$w$位，然后把它看作无符号数得到结果，这实际上是种模运算，即对$x+y$模$2^w$，例如，用4个bit表示数字，x = 9, y = 12
即[1001]和[1100]，它们的和为21，即[10101]但我们得到的结果是[0101] = 5
而$21 mod 16 = 5$

Unsigned Addition
对于整数$0\le x, y < 2^w$，若$x+y < 2^w$，则

$$x +^u_w y = x + y\ (Normal)$$

若$2^w \le x+y< 2^{w+1}$，则

$$x +^u_w y = x + y - 2^w\ (Overflow)$$

首先，x+y的结果用$w+1$位足以表示，在Normal对应的条件下，最高位(假设用$w+1$位表示)是0，所以截断后就是x+y，在Overflow对应的条件下，最高位为1，所以舍弃最高位等于减去$2^w$

An arithmetic operation is said to overflow when the full integer result cannot fit within the word size limits of the data type.

Detecting overflow of unsigned addition
对于$0\le x, y\le UMax_w$，设$s = x +^u_w y$，那么计算$s$时发生溢出当且仅当$s < x$(或者$s < y$，这两者等价)

这是因为如果溢出，则$s = x + y - 2^w$，而$y - 2^w < 0$

比如我们可以写一个判断加法计算是否发生溢出的函数

/* Determine whether arguments can be added without overflow */
int uadd_ok(unsigned x, unsigned y) {
    unsigned sum = x + y;
    return sum >= x;
}

Modular addition forms a mathematical structure known as an abelian group(阿贝尔群)
That is, it is commutative(可交换的) and associative(可结合的); it has an identity element 0, and every element has an additive inverse(加法逆元). Let us consider the set of w-bit unsigned numbers with addition operation $+^u_w$. For every value $x$, there must be some value $-^u_w x$ such that $-^u_w x +^u_w x = 0$

Unsigned Negation
For any number $x$ such that $0\le x < 2^w$, its $w$-bit unsigned negation $-^u_w x$ is:

$$x,\ \ x=0$$

$$2^w-x,\ \ x>0$$

如果x=0，那么0+0=0。逆元是0，如果x>0，我们之前说过，$+^u_w$实际上就是对整数x+y对$2^w$取模的一个运算，$0< 2^w-x < 2^w$且$2^w-x+x\ mod\ 2^w = 0$，因此$2^w-x$是$x$的逆元

3.2 Two’s-Complement Addition

Given integer values $x$ and $y$ in the range $−2^{w-1}\le x, y\le 2^{w−1}−1$, their sum is in the range $−2^w ≤x +y≤2^w−2$, potentially requiring $w+1$ bits to represent exactly.

Let us define $x+^t_w y$ to be the result of truncating the integer sum $x + y$ to be $w$ bits long and then viewing the result as a two’s-complement number.

Two’s-complement addition
For integer values $x, y$ in the range $−2^{w-1}\le x, y\le 2^{w−1}−1$, $x+^t_w y =$

$$x + y - 2^w,\ \ \ 2^{w-1}\le x+y$$

$$x + y,\ \ \ -2^{w-1}\le x+y< 2^{w-1}$$

$$x + y + 2^w,\ \ \ x+y< -2^{w-1}$$

根据$x+y$的取值，如果超过$TMax_w$，即上面第一种情况，称为positive overflow
如果小于$TMin_w$，我们称为negative overflow

从bit串的角度去看，两个数的$w$位补码之和和无符号之和是完全一样的，只是理解方式不一样
因此

$$x+^t_w y = U2T_w(T2U_w(x)+^u_w T2U_w(y))$$

$$= U2T_w((x_{w-1}2^w+x+y_{w-1}2^w+y)\ mod\ 2^w)$$

$$= U2T_w((x+y)\ mod\ 2^w)$$

Detecting overflow of two’s-complement addition
For $x$ and $y$ in the range $TMin_w\le x, y\le TMax_w,\ \ s = x+^t_w y$
Then the computation of $s$ has had positive overflow if and only if $x>0$ and $y>0$ but $s\le 0$. The computation has had negative overflow if and only if $x<0$ and $y<0$ but $s\ge 0$

3.3 Two’s-Complement Negation

Every number $x$ in the range $TMin_w\le x\le TMax_w$ has an additive inverse under $+^t_w$, which we denote $-^t_w x$

$$-^t_w x = \begin{cases} TMin_w,\ x=TMin_w\\ -x,\ x > TMin_w \end{cases}$$

当$x=TMin_w$时，$TMin_w + TMin_w = -2^w$，导致negative overflow，所以$TMin_w +^t_w TMin_w = -2^w + 2^w = 0$
而$x>TMin_w$时，$-x$都可以用一个$w$位的补码数来表示，它们的和是$-x+x=0$，故$-x +^t_w x = 0$

Problem 4
下面的代码判断是否发生补码加法的溢出，它错在哪里？

int tadd_ok(int x, int y) {
    int sum = x + y;
    return (sum - x == y) && (sum - y == x);
}

这本书似乎都没讲补码的减法，减法应该就是$-^t_2$，减去一个数就等于加上它的逆元

我们不要被底层的二进制加法打乱了，我们前面得到的公式，就是底层进行二进制加法后截断成$w$位并按补码的方式计算得到的数值，所以直接利用那个公式是没问题的

$$sum -^t_w x = sum +^t_w (-^t_w x)$$

由于补码加法具有结合律和交换律，于是

$$sum -^t_w x = (-^t_w x + x) + y = 0+y=y$$

Problem 5
下面的代码判断减法过程中是否发生溢出，它错在哪里？

int tsub_ok(int x, int y) {
    return tadd_ok(x, -y);
}

补码减法本质上还是加法，即减去一个数等于加上它的逆元，上面这个程序大多数情况都是对的，除了$y=TMin_w$时，这个程序是错误的，因为$y$的逆元此时并不等于$-y$
以$w=4$举例，$x=3, y=-8$，事实上$-8+3=-5$，即$1000+0011=1011$并没有溢出，但是判定时变成判定$3+8=11\ge 2^3$，发生了溢出

事实上，在$y=TMin_w$时，如果$x<0$，实际上就负溢出了，但会被判定为没溢出；如果$x\ge 0$，实际上就没溢出，但会被判定为溢出

计算一个用bit串表示的数的补码非，有几种快速的方法

第一种是对每一位取反，然后再对结果加1，在C语言中，对于任意整数值x，-x和~x+1得到的结果一样

第二种方法是，对于这个值的位级表示，从右往左找到第一个1的位置，然后将1左侧的每一个bit都取反

3.4 Unsigned Multiplication

对于整数$0\le x, y\le 2^w-1$，它们的乘积最大为$2^{2w}-2^{w+1}+1$，需要$2w$位来表示，乘法$*^u_w$我们也定义为将结果截断成$w$位并把它视为补码表示进而得到数值

由于无符号数是非负的，于是对$0\le x, y\le UMax_w$，有

$$x*^u_w y=(xy)\ mod\ 2^w$$

3.5 Two’s-Complement Multiplication

对于$-2^{w-1}\le x,y\le 2^{w-1}-1$的整数$x, y$，最大上限是$2^{2w-2}$，这需要$2w$位来表示（注意补码最高位是负权）

同样地，我们也是得到结果后截断成$w$位，这等价于把$xy$模$2^w$，尽管$xy$可能是负的，但取模后的结果一定是截断+按无符号数去理解，这是因为任何整数都可以写成$N=k2^w+r,\ 0\le r < 2^w$，而$k2^w$对应的都是第$w$位及以上的内容。例如-10 = 4 * (-3) + 2
[10110] = -16 + 4 + 2 = 4 * (-3) + 2
截断成2位为[10]=2

Two’s-complement multiplication
For $x, y$ such that $TMin_w\le x, y\le TMax_w$ :

$$x *^t_w y = U2T_w((xy)\ mod\ 2^w)$$

Bit-level equivalence of unsigned and two’s-complement multiplication
设$\vec{x}, \vec{y}$是长度为$w$的位向量，设$x=B2T_w(\vec{x}), y=B2T_w(\vec{y}), x'=B2U_w(\vec{x}), y'=B2U_w(\vec{y})$
那么

$$T2B_w(x *^t_w y) = U2B_w(x' *^u_w y')$$

即对无符号数和补码乘法来说，乘法运算的结果的位级表示（截断后）是一样的

推导：
$x' = x + x_{w-1}2^w, y' = y + y_{w-1}2^w$，于是

$$(x'y')\ mod\ 2^w = (xy)\ mod\ 2^w$$

而

$$x *^t_w y = U2T_w((xy)\ mod\ 2^w)$$

两边同时应用$T2U_w$，有

$$T2U_w(x *^t_w y) = xy\ mod\ 2^w$$

于是

$$T2U_w(x *^t_w y) = (x'y')\ mod\ 2^w = x' *^u_w y'$$

两边同时应用$U2B_w$，有

$$U2B_w(T2U_w(x *^t_w y)) = T2B_w(x *^t_w y) = U2B_w(x' *^u_w y')$$

Problem 6
请说明为什么下面的程序是正确的

/* Determine whether arguments can be multiplied without overflow. */
int tmul_ok(int x, int y) {
    int p = x * y;
    // Either x is 0, or dividing p by x gives y.
    return !x || p/x == y;
}

(1)首先，先证明数学乘积$xy$可以写成$xy = p+t2^w$，$p$是截断成$w$位后按补码理解的结果，例如$w=4$时3*3=9=16+(-7)，-7正是实际截断后的结果

先将$xy$写成$2w$位的补码数，只看高$w$位，用补码理解得到数$v$，再看低$w$位，用无符号数理解得到$u$，那么$xy = v2^w+u$

由于$u$和$p$的bit串长得一模一样，所以$u=T2U_w(p)$，于是$u = p + p_{w-1}2^w$，令$t=v+p_w-1$，有$xy=p+t2^w$

(2)如果t=0，那么结果$xy=p$，刚好$w$位就能表示结果，没有溢出，如果t不等于0，那么$xy$不等于$p$，也就是$w$位是不够用的，发生了溢出，因此t=0当且仅当$xy$乘法过程没发生溢出

(3)需要注意的是，一般数学上的模运算要求除数和余数都是正数（或者余数为0），但C语言中的除法是向0截断的，比如$-7 / 3 = -2$，因为结果虽然是$-2.333...$但$-2$更靠近0，相应地，$-7 \% 3 = -1$，C语言中，余数的符号和被除数保持一致

于是计算p/x，设结果为$q$，则$p=xq+r$，其中$\mid r\mid < \mid x\mid$，这是因为这个式子中$q$要等于计算出来的真实结果

因此，$q=y$时，有$xy = xy+r+t2^w$，即$r+t2^w=0$，而$\mid r\mid <\mid x\mid \le 2^w$，所以这推出$r=t=0$

如果$t=0$，那么由(1)得$xy=p$，也许p/x==y是显然的，不过要严格证明，还需说明$q=y$，在$x$不等于0的情况下，有$xy=xq+r$，即$x(y-q)=r$
如果$q=y$，证明完毕，如果$q\neq y$，那么$r\neq 0$，两边同时取绝对值，有

$$\mid x\mid \mid y-q\mid = \mid r\mid$$

而$\mid r\mid <\mid x\mid$，那么在$x$不等于0的情况下，得到

$$\mid y-q\mid < 1$$

矛盾！因此$q=y$

而$x=0$时，乘法结果为0，不会发生溢出

因此我们证明了，过程没溢出等价于$t=0$等价于p/x==y或x等于0

Problem 6
假设int是32位的，利用int64_t设计一个检验乘法是否发生溢出的函数，不要用除法

int tmul_ok(int x, int y) {
    // Compute product without overflow.
    int64_t p = (int64_t) x*y;

    // See if casting to int preserves value.
    return p == (int) p;
}

注意第3行的如果写成int64_t p = x*y是不行的，这样的话x*y会先算成一个32位的值（可能是溢出后截断的），然后再位扩展成64位

Problem 7

3.6 Multiplying by Constants

Historically, the integer multiply instruction on many machines was fairly slow, requiring 10 or more clock cycles, whereas other integer operations—such as addition, subtraction, bit-level operations, and shifting—required only 1 clock cycle.

As a consequence, one important optimization used by compilers is to attempt to replace multiplications by constant factors with combinations of shift and addition operations.

Unsigned multiplication by a power of 2
For C variables x and k with unsigned values $x$ and $k$, such that $0\le k< w$, the C expression x << k yields the value $x *^u_w 2^k$.
使用一定的数学知识即可证明无符号数的情况

对于补码，之前说过，对于bit串长一样的x，按无符号数去理解的值是$x$，按补码的方式去理解的值是$x'$，那么$x *^u_w 2^k$和$x' *^t_w 2^k$的bit串也是一样的，而这个bit串是x << k得到的，因此只要按补码的方式理解x << k，得到的数值就是$x' *^t_w 2^k$的结果

Two’s-complement multiplication by a power of 2
For C variables x and k with two’s-complement values $x$ and unsigned value $k$, such that $0\le k< w$, the C expression x << k yields the value $x *^t_w 2^k$.
其实这个证明也可以不用补码和无符号数乘法结果的bit串一致的性质，直接展开用数学证明也行

这个过程中会发生溢出，但左移本身就是先移位后截断的，所以如果有溢出，得到的结果也是溢出后的结果，以$w=4$举例，对于x = 1011
若它是无符号数，左移1位，得到1 0110，即$11 *^u_4 2 = 6, 22\ mod\ 16 = 6$
若它是补码数，左移1位，得到1 0110，即$-5 *^t_4 2 = 6$

由于整数乘法比移位和加法的代价要大，C语言编译器试图以移位、加法和减法的组合来消除整数乘常数的情况，比如x * 14，由于$14 = 2^3+2^2+2^1=2^4-2^1$编译器会将乘法重写为(x<<3) + (x<<2) + (x<<1)或者(x<<4) - (x<<1)
根据我们上面的说明，无论x是无符号数还是补码数，无论乘法过程有没有溢出，结果都是对的

一般地，对于x * K，编译器可以以二进制的形式表示K，比如[(0…0)(1…1)…(1…1)(0…0)]，像14就是[(0…0)(111)(0)]，对于第$n$到第$m$个位置的连续的1（14中，n=3，m=1），可以有两种形式

1. x<<n + x<<(n-1) + ... + x<<m
2. x<<(n+1) - (x<<m)

比如K=55，只要求用2次加/减法和2次移位
[110111]可以看成[111111]减去中间那个1即$2^3$，于是为(x<<6) - x<<0 - x<<3 = x<<6 - (x<<3) - x
或者分成两块处理，即x<<6 - (x<<4) + (x<<3) - (x<<0) = x<<6 - (x<<3) - x

当然，并不是说乘常数都要化成加减法和移位的形式，这取决于这些指令在特定机器上的相对速度，大多数编译器只有在只需要少量移位、加减法就足够的时候才进行优化

3.7 Dividing by Powers of 2

Integer division on most machines is even slower than integer multiplication — requiring 30 or more clock cycles.

整数除法总是舍入到0，即如果x/y结果是正数，向下取整，如果x/y结果是负数，向上取整

Unsigned division by a power of 2
For C variables x and k with unsigned values $x$ and $k$, such that $0\le k < w$, the C expression x >> k yields the value $\left \lfloor x/2^k\right \rfloor $

这是因为，可以假想原本的数的二进制表示有小数点，那么右移后，一些小数点左侧的1被移动到小数点右侧，构成结果的小数部分，但实际上没有小数点的部分，那些1就被截断而消失了，也就是结果的小数部分直接舍去。
例如7/4=1.75，即0001.11，实际上0111 >> 2 = 0001

严格地证明，设无符号数值$x$的bit表示为[$x_{w-1},x_{w-2},...,x_0$]，$0\le k < w$，设无符号数值$x'$的bit表示为[$x_{w-1},...,x_k$]，设无符号数值$x''$的bit表示为[$x_{k-1},...,x_0$]，那么$x=2^kx'+x''$，而且$0\le x'' < 2^k$，所以$\left \lfloor x/2^k\right \rfloor = x'$

Two’s-complement division by a power of 2, rounding down
For C variables x and k with two’s-complement values $x$ and unsigned value $k$, such that $0\le k < w$, the C expression x >> k, when the shift is performed arithmetically, yields the value $\left \lfloor x/2^k\right \rfloor $

例如，-10/4向下取整得到-3，而1111 0110 >> 2 = 1111 1101

证明：设补码数值$x$的bit表示为[$x_{w-1},x_{w-2},...,x_0$]，$0\le k < w$，设补码数值$x'$的bit表示为[$x_{w-1},...,x_k$]，设无符号数值$x''$的bit表示为[$x_{k-1},...,x_0$]，那么$x=2^kx'+x''$，而且$0\le x'' < 2^k$，所以$\left \lfloor x/2^k\right \rfloor = x'$
而算术右移$k$位得到的[$x_{w-1},x_{w-1},...,x_{w-1},x_{w-2},...,x_k$]就是$x'$的bit表示的符号扩展，因此这个移位后的向量就是$\left \lfloor x/2^k\right \rfloor $的补码表示

Two’s-complement division by a power of 2, rounding up
For C variables x and k with two’s-complement values $x$ and unsigned value $k$, such that $0\le k < w$, the C expression (x + (1 << k) - 1) >> k, when the shift is performed arithmetically, yields the value $\left \lceil x/2^k\right \rceil $

证明：
我们需要证明对于整数$x,y\ (y>0)$，$\left \lceil x/y\right \rceil = \left \lfloor (x+y-1)/y\right \rfloor $

例如-30/4向上取整得到-7，而(-30+4-1)/4向下取整得到-7

设$x=qy+r,\ 0\le r < y$，那么$(x+y-1)/y=q+(r+y-1)/y$，那么$\left \lfloor (x+y-1)/y\right \rfloor =q+ \left \lfloor (r+y-1)/y\right \rfloor $，r=0时，后面一项等于0，r>0时，后面一项等于1，因此当y整除x时，结果为q，否则为q+1，实现向上取整

x + (1 << k) - 1对应$y=2^k$的情况，因此，对于算术右移的补码机器，C表达式(x<0 ? x+(1<<k)-1 : x) >> k会计算数值$x/2^k$

3.8 Final Thoughts on Integer Arithmetic

As we have seen, the “integer” arithmetic performed by computers is really a form of modular arithmetic. The finite word size used to represent numbers limits the range of possible values, and the resulting operations can overflow.

We have also seen that the two’s-complement representation provides a clever way to represent both negative and positive values, while using the same bit-level implementations as are used to perform unsigned arithmetic—operations such as addition, subtraction, multiplication, and even division have either identical or very similar bit-level behaviors, whether the operands are in unsigned or two’s complement form.

4 Floating Point

In this section, we will see how numbers are represented in the IEEE floating point format. We will also explore issues of rounding, when a number cannot be represented exactly in the format and hence must be adjusted upward or down
ward. We will then explore the mathematical properties of addition, multiplication, and relational operators.

IEEE
电气和电子工程师协会是一个包括所有电子和计算机技术的专业团体。它出版刊物，举办会议，并且建立委员会来定义标准，内容涉及从电力传输到软件工程。

4.1 Fractional Binary Numbers

例如$(0001.1010)_2 = 2^0+2^{-1}+2^{-3} = 1.625$

十进制小数转二进制，每次用小数部分乘2，并记录乘积的整数部分，并用剩下的小数部分继续乘，直到小数部分为0，然后顺序排列取出的整数

有些数，例如0.2，不能准确地表示为一个二进制小数，会一直循环下去，这时只能根据精度要求增加二进制表示的长度

4.2 IEEE Floating-Point Representation

The IEEE floating-point standard represents a number in a form $V=(-1)^s \times M \times 2^E$

• The sign s determines whether the number is negative (s=1) or positive.
• The significand(尾数) M is a fractional binary number that ranges either between $1$ and $2-\epsilon$ or between $0$ and $1-\epsilon$. (这里$1-\epsilon$是指$0.1111...1_2$)
• The exponent(阶码) E weights the value by a (possibly negative) power of 2.

The value encoded by a given bit representation can be divided into three different cases (the latter having two variants), depending on the value of exp.

4.2.1 Normalized Values

此时exp不是全0也不是全1，阶码此时被理解为一个以偏置(biased)形式表示的有符号数，阶码的值为$E=e-Bias$，其中$e$是无符号数，位表示为$e_{k-1}...e_1e_0$，双精度范围是1~2046，$Bias$是一个等于$2^{k-1}-1$（单精度为127，双精度为1023）的偏置值，所有指数的范围，对单精度是-126~127，对双精度是-1022~1023

The fraction field frac is interpreted as representing the fractional value $f$,
where $0 \le f<1$, having binary representation $0.f_{n−1} ...f_1f_0$, that is, with the binary point to the left of the most significant bit. The significand is defined to be
$M=1+f$. This is sometimes called an implied leading 1representation, because we can view $M$ to be the number with binary representation $1.f_{n−1}f_{n−2} ...f_0$. This representation is a trick for getting an additional bit of precision for free, since we can always adjust the exponent $E$ so that significand $M$ is in the range $1\le M<2$ (assuming there is no overflow).

4.2.2 Denormalized Values

When the exponent field is all zeros, the represented number is in denormalized form. In this case, the exponent value is $E = 1− Bias$, and the significand value is $M=f$.

非规格化数有两个用途

1. 提供了表示0的方式，因为规格化数的情况下M总是大于等于1，事实上，00…0表示+0.0而10…0表示-0.0，它们在某些方面被认为是不同，其他方面是相同的
2. 表示非常接近0.0的数

4.2.3 Special Values

A final category of values occurs when the exponent field is all ones. When the
fraction field is all zeros, the resulting values represent infinity, either $+\infty$ when $s=0$ or $-\infty$ when $s=1$. Infinity can represent results that overflow, as when we multiply two very large numbers, or when we divide by zero. When the fraction
field is nonzero, the resulting value is called a NaN, short for “not a number.” Such values are returned as the result of an operation where the result cannot be given as a real number or as infinity, as when computing $\infty -\infty$ or $\sqrt{-1}$.

4.3 Example Numbers

我们以8位浮点数为例，$k=4$的阶码位和$n=3$的小数位

对于非规格化数，总要乘$2^{1-7}=\frac{1}{64}$，最大就是$\frac{7}{8}\times \frac{1}{64}=\frac{7}{512}$，而最小的规格化数是$\frac{8}{512}$，因此，做到了最大非规格化数和最小规格话数的平滑转变，这归功于非规格化数中对$E=1-Bias$的定义

最大的规格化数为0 1110 111，$E=8+4+2-7=7$，$M=1+\frac{7}{8} = \frac{15}{8}$，值为$\frac{15}{8} \times 2^7=240$

对于一些特殊数值，我们可以得到如下结论

• +0.0的位表示全为0
• 最小的正非规格化数的位表示，是最低有效位为1而其他位为0
• 最大的非规格化数的位表示，是阶码字段全为0而小数字段全为1
• 最小的正规格化数的位表示是阶码字段最低有效位为1，其他位都为0
• 值1.0的位表示是阶码字段除最高位外都为1，其他位为0，这样$E=e-Bias=2^{k-1}-1-(2^{k-1}-1)=0$
• 最大的规格化数的位表示为符号位为0、阶码的最低有效位为0（其他均为1，这样防止变成无穷），其他位均为1

我们来试着把整数值转换成浮点形式，例如，对于12345，它的二进制表示是[11000000111001]，于是有$12345=1.1000000111001_2\times 2^13$

用单精度形式编码，开头的1丢弃，剩下的就是小数部分，对应小数字段，即[10000001110010000000000]，偏置量是127，那么阶码字段就应该是13+127=140，即[10001100]

最后，浮点表示可以表示的数并不是均匀分布的，越靠近0它们越稠密，这是因为小数字段的位数是固定的，每组数都要乘$2^E$，设小数字段的位数为$n$，那么在固定的$E$下，相邻浮点数间隔为$2^E \times 2^{-n}$

以6位浮点数为例，$k=3,n=2$，偏置为3
非规格化数，$E=1-3=-2$，小数为0~$2^{-1}+2^{-2}=\frac{3}{4}$，即$0,\frac{1}{16},\frac{2}{16},\frac{3}{16}$，间隔就是$2^{-2}\times 2^{-2}=\frac{1}{16}$

规格化数一开始也是$E=1-3=-2$，后面$E=2-3=-1$时，小数字段，即$M$的范围是$1.0,1.25,1.5,1.75$，每个数还要乘$2^{-1}$，间隔就是$2^{-1}\times 2^{-2} = \frac{1}{8}$

所有非负数是

$$\begin{aligned} E=-2 &: 0,\frac1{16},\frac2{16},\ldots,\frac7{16}\\ E=-1 &: \frac12,\frac58,\frac68,\frac78\\ E=0 &: 1,1.25,1.5,1.75\\ E=1 &: 2,2.5,3,3.5\\ E=2 &: 4,5,6,7\\ E=3 &: 8,10,12,14 \end{aligned}$$

4.4 Rounding

一个真实的数或者精确的运算结果，无法用当前浮点格式精确表示时，计算机该选附近哪个可表示的浮点数呢？

例如，某种浮点格式只能表示2.00,2.25,2.50,2.75,现在要保存2.63，必须挑2.50或2.75来表示，关键在于舍入方向

IEEE浮点格式定义了4种舍入方式(rounding modes)

4.4.1 Round-toward-zero

向0舍入，即正数向较小值舍入，负数向较大值舍入

4.4.2 Round-down & Round-up

向下舍入，即总向较小值舍入，向上舍入同理

4.4.3 Round-to-even

这是默认的舍入模式，它找最靠近的可表示的浮点数来舍入，比如舍入到整数，1.6舍入到2，1.4舍入到1，对于1.5，它比较特殊，会舍入到偶数，即1.5舍入到2，但2.5也舍入到2

如果不是舍入到整数，向偶数舍入就考虑最低有效位的数字是奇数还是偶数，比如我们想把十进制数舍入到百分位，例如1.23499999舍入到1.23，1.23500001舍入到1.24，因为它们并不是在1.23和1.24正中间，而1.23500000和1.2450000都舍入到1.24，因为4是偶数

同样地，向偶数舍入也可以应用到二进制表示的小数里，我们认为最低位为0就是“偶”，最低位为1就是“奇”

怎么判断刚好在中间呢？假设$X,Y$是要保留的部分，如果这个二进制小数形如$XX...X.YY...Y100...$，那么就说明是在正中间，例如保留到小数点右边2位，位，$1.01100_2$就是1.375，位于1.25和1.5正中间，那么这时就要向偶数舍入，即摄入为$1.10_2$

例如，舍入到小数点右边2位
$10.00011_2(2\frac{3}{32})$，它的剩余部分是01100…，小于100…，向更靠近的$10.00_2(2)$舍入即可

$10.00110_2(2\frac{3}{16})$，它的剩余部分是1100…，大于100…，因此向更靠近的$10.01_2(2\frac{1}{4})$舍入即可

但对于$10.00100_2(2.125)$，在正中间，我们向偶数舍入，得到$10.00_2$，又如$10.11100_2$，舍入到$11.00_2$

Problem 8
Consider the following two 7-bit floating-point representations based on the IEEE floating-point format. Neither has a sign bit — they can only represent nonnegative numbers.

1. Format A

• There are $k = 3$ exponent bits. The exponent bias is 3.
• There are n=4 fraction bits.

2. Format B

• There are $k =4$ exponent bits. The exponent bias is 7.
• There are $n=3$ fraction bits.
  Below, you are given some bit patterns in format A, and your task is to convert
  them to the closest value in format B. If necessary, you should apply the round-to even rounding rule.

Format A	A 的值	Format B	B 的值
011 0000	1	0111 000	1
101 1110
010 1001
110 1111
000 0001

答案：

Format A	A 的值	Format B	B 的值
011 0000	1	0111 000	1
101 1110	15/2	1001 111	15/2
010 1001	25/32	0110 100	3/4
110 1111	31/2	1011 000	16
000 0001	1/64	0001 000	1/64

010 1001，要乘的是$2^{2-3}=2^{-1}$，小数部分是$\frac{9}{16}$，那么B格式下的阶码就应该是0110，这样6-7=-1，小数部分本应该是1001，但现在只有3位，这个格式是二进制小数的格式，我们本质上是对有效数字$M$进行舍入，这里即$1.1001_2$，它处于正中间，所以向偶数舍入的结果要让最后一位是0，是100，事实上，$\frac{25}{32}$位于0110 100 ($\frac{24}{32}$)和0110 101 ($\frac{26}{32}$)之间

110 1111是一样的方法，可以确定阶码是1010，这样6-3=10-7，小数部分依旧1111要舍入到3位，实际上是对小数$1.1111_2$进行舍入，它处于$1.111_2(1.875)$和$10.000_2(2.000)$之间，即1010 111(15)和1011 111(16，注意这里对于$10.000_2$，为了使其为$1.000_2$，阶码要+1)之间，舍入结果为16

000 0001(1/64)要注意了，如果采取上面的方法，可能会得到0101 000(1/4)，问题在于这时小数部分没有默认的1了！000 0001是$\frac{1}{16}\times 2^{-2}$，不能认为转化成B格式后指数仍是-2，0101的阶码代表是规格化数，会默认有1，应该先尝试把格式A的数进行规格化，得到$1.000_2\times 2^{-6}$，于是格式B下有0001 000

4.5 Floating-Point Operations

IEEE标准规定了一个简单的规则，来确定算术运算的结果，即把浮点值$x,y$看成实数，精确地进行运算后再进行舍入，得到结果

这种规定运算行为和结果的好处是，它独立于任何具体的硬件或软件实现，我们不需要知道具体是怎么实现运算的，但我们知道最后的结果必须是什么

我们定义$x+^f y=Round(x+y)$，由于溢出，该运算可能得到无穷值，这个运算可交换但不可结合，例如单精度浮点下(3.14+1e10)-1e10会由于舍入，3.14会丢失，得到结果0.0

大多数值在浮点加法下有逆元，除了无穷和NaN，因为$+\infty - \infty = NaN, NaN +^f x = NaN$

由于不满足结合律，原本编译器可能将x = a + b + c; y = b + c + d;优化成t = b + c; x = a + t; y = t + d;来省去一个浮点加法，但这使用了加法运算的结合律，编译器会保守地避免这种优化

浮点加法满足单调性，如果不是NaN的$a\ge b$，那么对于不是NaN的任何$x$，有$x +^f a \ge x +^f b$，无符号加法和补码加法并不具备这个属性，例如4位无符号数，虽然$15>14$，但$15+1=0<14+1=15$

同样地，定义$x *^f y = Round(x\times y)$，结果可能是无穷或者NaN，满足交换律，且满足$x *^f 1.0 = x$，但不满足结合律，例如单精度浮点数，

$$(1e20 * 1e20) * 1e-20 = +∞ * 1e-20 = +\infty$$

$$1e20 * (1e20 * 1e-20) = 1e20$$

浮点乘法也不满足分配律，例如

$$1e20 * (1e20 - 1e20) = 0$$

但

$$1e20 * 1e20 - 1e20 * 1e20 = +\infty - (+\infty) = NaN$$

浮点乘法也满足单调性，对于不是NaN的$a\ge b, c\ge 0$，有$a*^f c\ge b*^f c$

同样，若$c\le 0$，有$a*^f c \le b*^f c$

此外，只要$a\ne NaN$，就有$a*^f a\ge 0$

对于特殊参数，IEEE标准还定义了如$1/ -0 = -\infty, 1/ +0 = +\infty$等规则

4.6 Floating Point in C

All versions of C provide two different floating-point data types: float and double. On machines that support IEEE floating point, these data types correspond to single- and double-precision floating point. In addition, the machines use the round-to-even rounding mode.

Unfortunately, since the C standards do not require the machine to use IEEE floating point, there are no standard methods to change the rounding mode or to get special values such as $−0, +∞, −∞$,or $NaN$.

Most systems provide a combination of include (.h) files and procedure libraries to provide access to these features, but the details vary from one system to another. For example, the GNU compiler GCC defines program constants INFINITY (for $+∞$) and NAN (for $NaN$) when the following sequence occurs in the program file:

# define _GNU_SOURCE 1
# include <math.h>

When casting values between int, float, and double formats, the program changes the numeric values and the bit representations as follows (assuming data type int is 32 bits):

• From int to float, the number cannot overflow, but it may be rounded.(float范围虽然比int大得多，但它不能精确表示所有int，因为虽然范围大，但数值之间的间隔也会越来越大)

• From int or float to double, the exact numeric value can be preserved because double has both greater range (i.e., the range of representable values), as well as greater precision (i.e., the number of significant bits(有效位数)).

• From double to float, the value can overflow to $+∞$ or $−∞$, since the range is smaller. Otherwise, it may be rounded, because the precision is smaller.

• From float or double to int, the value will be rounded toward zero. For example, 1.999 will be converted to 1, while −1.999 will be converted to −1. Furthermore, the value may overflow. The C standards do not specify a fixed result for this case. Intel-compatible microprocessors designate the bit pattern [10 …00] ($TMin_w$ for word size $w$) as an integer indefinite value. Any conversion from floating point to integer that cannot assign a reasonable integer approximation yields this value. Thus, the expression (int) +1e10 yields -2147483648, generating a negative value from a positive one.

Problem 9
Assume variables x, f, and d are of type int, float, and double, respectively.
Their values are arbitrary, except that neither f nor d equals $+∞, −∞$,or $NaN$.

判断下列C表达式真假：
A. x == (int) (double) x
对的，因为double精度、范围都比int高

B. x == (int) (float) x
不对，float只有24个二进制有效位(算是默认带的1)，无法精确表示所有32位整数。

比如x的值为$2^{24}+1=16777217$，而float的小数字段只有23位，我们希望x应该是0 10010111 0000...(23个0)1，但位数不够，实际上夹在float可表示的0 10010111 00...0(23个0) (16777216)和0 10010111 00...0(22个0)1 (16777218)

C. d == (double) (float) d
不对，因为double的范围和精度都比float大，比如d= 1e40，那么转float后溢出变成正无穷，再转double也为正无穷；精度的例子正如上面的16777217，double可以精确表示但float不行，导致舍入

D. f == (float) (double) f
对的，跟A同理

E. f == -(-f)
对的，只是翻转了两次符号位，会变回原状

F. 1.0/2 == 1/2.0
对的，C执行混合类型算术时，先进行算术转换，由于一边是double，所以其实是1.0 / 2.0 = 0.5，右边同理，为1.0 / 2.0 = 0.5

G. d*d >= 0.0
对的，这个性质是满足的，主要是上溢会变正无穷，不会出负数

H. (f + d) - f == d
不一定为真，例如，$f = 2^{66}$, $d = 1.0$

f的实际编码为0 | 11000001 | 00000000000000000000000

计算f + d，f会先精确转换成double，变为
0 | 10001000001 | 0000000000000000000000000000000000000000000000000000

要注意，下一个更大的double就是小数部分最后一位+1，即
0 | 10001000001 | 0000000000000000000000000000000000000000000000000001

但实际上多了$2^{-52}\times 2^{66} = 2^{14} = 16384$，所以f + d的精确结果是$2^{66} + 1$，但double只能在附近的两个值中选择

$$D_0 = 2^{66}$$

$$D_1 = 2^{66} + 16384$$

根据舍入到偶数的规则，选更近的$D_0$，因此是0.0 == 1.0为假