三个小伙子同时爱上了一 个姑娘，为了决定他们谁能娶这个姑娘，他们决定用手枪进行一次决斗。小李的命中率是30％，小黄比他好些，命中率是50％，最出色的枪手是小林，他从不失误，命中率是100％。由于这个显而易见的事实，为公平起见，他们决定按这样的顺序：小李先开枪，小黄第二，小林最后。然后这样循环，直到他们只剩下一个人。那么这三个人中谁活下来的机会最大呢？他们都应该采取什么样的策略？

更新日志：

• 2018.4.10
  • 初版；

更新日志：

• 2018.4.8
  • 增加 na_if() 函数的介绍；
• 2018.4.4
  • 增加“项目的组织”一节；
  • 增加列操作与维度变换一节；
• 2018.4.3
  • 初版；

我已经好久没有写过一篇文章了。

重点练习

2.10

考虑如下代码：

1 2 3 4 5 6

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

>

已知 a ^ a = 0，求以上代码运行时每一步的情况。

但这个函数在 $x = y$（注意不是 $a=b$ ）时，会出现原地交换的错误，被修改的内存将会被置0。因此如果使用这个方式交换两个数的值，一定要严防原地交换。

2.15

只使用位级和逻辑运算，编写一个 C 表达式，使它等价于 x == y。

答案是 !(x ^ y)。在不能使用 == 运算符的时候可以用它代替。

2.21

假设在采用补码运算的 32 位机器上对以下表达式求值，填写下表，描述强制类型转换和关系运算的结果。

在运算时，无符号类型比有符号类型的等级要高。只要两个操作数之中有一个是无符号数，C语言就会在运算之前把两个操作数都转换为无符号数，再进行运算。下面把以上五个式子的十六进制表达列出。若为有符号数，则同时将十进制表达列出。

• 0x80000000 == 0x80000000
• 0x80000000 < 0x7FFFFFFF ，-2147483648 < 2147483647
• 0x80000000 < 0x7FFFFFFF
• 0x80000000 < 0x80000001 ，-2147483648 < -2147483647
• 0x80000000 < 0x80000001

2.30、2.31、2.35、2.36

编写一个函数，检验两个有符号整数相加是否会溢出。

补码加法的溢出有正溢出（得到负数）和负溢出（得到正数）两种。两种均不溢出才返回1，否则应该返回0。若 $x$ 和 $y$ 不同号，那么一定不会溢出。因此只需要讨论 $xy>0$ 的情况即可：

1
2
3
4
5

int tadd_ok(int x, int y) {
    int neg_over = (x < 0 && y < 0 && x + y > 0);
    int pos_over = (x > 0 && y > 0 && x + y < 0);
    return !neg_over && !pos_over;
}

但是一定要注意的是，补码的运算对加法和减法是封闭的。所以用减法来检验加法是否溢出是没有作用的。

不过对乘法则不是这样。补码的乘法是否溢出是可以用除法来检验的。示例如下：

1
2
3
4

int tmult_ok(int x, int y) {
    int p = x * y;
    return !x || p / x == y;
}

下面给出证明：

首先，当 $x=0$ 时，这个函数是符合要求的。当 $x\neq 0$ 时，考虑 $w$ 位的数字 $x$ 和 $y$ 。记 $p$ 是 $x$ 和 $y$ 进行补码乘法的结果，那么一定存在整数 $t=0$ 或 $t=1$ 使得 $x\cdot y = p + t\cdot 2^w$ 。当 $p$ 的计算溢出时，$t=1$ 。由带余除法的基本原理，存在唯一整数对 $(q, r)$ ，使得 $p=qx+r$，其中 $0\leq r < |x|$。下面证明 $q=y$ 是 $r=t=0$ 的充要条件。

当 $q=y$ ，我们有 $x\cdot y-t\cdot 2^w = p = xy+r$。又 $r\geq 0, -t\cdot 2^w\leq 0$，故 $r=t=0$ 。当 $r=t=0$， $x\cdot y = p = q\cdot x$ ，故 $q=y$。因此 $q=y$ 是 $r=t=0$ 的充要条件。由于 $q$ 恰好是 p / x 的值，因此用除法来检验乘法是否溢出是有效的。

这一方法也可以不用除法实现。只需用 $2w$ 位有符号类型来存储结果，并看它和截断至 $w$ 位之后是否相等即可。代码如下：

1
2
3
4

int tmult_ok(int x, int y) {
    int64_t pll = (int64_t) x * y;
    return pll == (int) pll;
}

家庭作业

2.55–2.57

略。

2.58

本题需要编写一个函数 is_little_endian，返回机器是用小端法还是大端法。

想法非常简单，只需要用1来检验即可，看第一个字节。如果第一个字节不是全0，那就是小端法，否则是大端法。

1
2
3
4

int is_little_endian() {
    int x = 1;
    return *((char *) &x);
}

2.59

本题需要编写一个 C 表达式，生成一个字，由 x 的最低有效字节和 y 中剩下的字节组成。

本质上是生成两个掩码，表达式是 (x & 0xFF) & (y & ~0xFF) 。

2.60

1
2
3
4

unsigned replace_byte(unsigned x, int i, unsigned char b) {
    // Replace x's i th byte with b
    return (x << (i << 3)) | ((int) b << (i << 3));
}

2.61

• x 的每一位都等于1：!~x。
• x 的每一位都等于0：!x。
• x 的最低有效字节中的位都等于1：!((x ^ 0xFF) & 0xFF) 。
• x 的最高有效字节中的位都等于0：!(x & (0xFF << ((sizeof(int) - 1) << 3))) 。

2.62

编写函数 int_shifts_are_arithmetic() ，在对 int 类型的数使用算术右移的机器上生成1，反之生成0。要求在任意字长的机器上都可以运行。

1
2
3
4

int int_shifts_are_arithmetic() {
    int x = ~0;
    return !(x ^ (x >> 1));
}

2.63

用函数 srl() 来用算术右移来完成逻辑右移。用函数 sra() 来用逻辑右移来完成算术右移。不能使用右移或除法。

对 srl() 这个函数，本质是要将第 $w-1$ 位到 $w-k$ 位都刷成0（最右为第0位）。

1
2
3
4
5
6
7

unsigned srl(unsigned x, int k) {
    unsigned xsra = (int) x >> k;
    // Your code here.
    int w = sizeof(int) << 3;
    unsigned mask = 2 << (w - k - 1) - 1; // in case k == 0
    return xsra & mask;
}

对 sra() ，需要将第 $w-1$ 位到 $w-k$ 位都统一成第 $w - k - 1$ 位的值。那么我们首先取得第 $w-k-1$ 位的值，对其取反加1，即可得到最高的 $k$ 位。于是我们把原来的数 xsrl 分为左右两段来处理。

1
2
3
4
5
6
7
8
9
10

unsigned sra(unsigned x, int k) {
    int xsrl = x >> k;
    // Your code here.
    int w = sizeof(int) << 3;
    unsigned z = 1 << (w - k - 1);
    unsigned mask = z - 1;
    unsigned left = ~mask & (~(z & xsrl) + z);
    unsigned right = mask & xsrl;
    return left | right;
}

2.64

编写函数 any_odd _one(x) ，当 x 的二进制表示中的任一奇数位为1时返回1，否则返回0。假设 $w=32$ 。

1
2
3

int any_odd_one(unsigned x) {
    return !!(x & 0x55555555);
}

2.65

编写函数 odd_ones(x) ，当 x 的二进制表达含有奇数个1时返回1，否则返回零。设 $w=32$。代码中算术运算、位运算和逻辑运算最多只能包含12个。

看到这个题目，可以考虑异或运算来对消1。如果有偶数个1，它们会两两经过异或变成0，从而最终得到0。所以将 x 的第一位依次与其后一位异或，到最后如果为1就是奇数个1，反之为偶数个1。但是这样会需要15次异或操作，会超出题目所限制的12个。如此一来，我们就只能考虑用对半分治的方式。先将前16位和后16位对齐后异或，再取前8位和后8位对齐后异或，直到最后剩一位，就是我们要的答案。

1
2
3
4
5
6
7
8

int odd_ones(unsigned x) {
    x ^= (x >> 16);
    x ^= (x >> 8);
    x ^= (x >> 4);
    x ^= (x >> 2);
    x ^= (x >> 1);
    return (x ^ 1) & 1;
}

2.66

生成一个掩码，取 x 的最高非零位。假设 $w=32$ 。最多只能包含15个算术运算、位级运算和逻辑运算。

本题的想法是先将 x 最高非零位向右扩展到最低位，再右移1位与原数异或即可。注意由于当 $x=0$ 的时候要返回 $0$ ，所以不能直接加1而要用异或来解决。

1
2
3
4
5
6
7
8

int leftmost_one(unsigned x) {
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x ^ (x >> 1);
}

2.67

编写一个过程 int_size_is_32() ，当在一个 int 是32位的机器上运行时产生1，而其他情况则产生0。不允许使用 sizeof 运算符。下面是一个错误的尝试：

1 2 3 4 5 6

> int bad_int_size_is_32() { > int set_msb = 1 << 31; > int beyond_msb = 1 << 32; > return set_msb && !beyond_msb; > } >

>

请回答：

1. 这份代码在哪个方面没有遵守 C 语言标准？
2. 修改代码使得它在 int 至少为32位的任何机器上都能正确地运行。
3. 修改代码使得它在 int 至少为16位的任何机器上都能正确地运行。

1. 在第3行，左移运算的右值为32，在 int 为32位的机器上是不合法的，超过了左值的宽度。

2. 将第3行修改为 int beyond_msb = 2 << 31;

3. 若要支持至少16位的机器，那么左移的量最多为15。可以将第2、3行用如下代码替换：

   1 2 3 4

   int a = 1 << 15; a <<= 15; int set_msb = a << 1; int beyond_msb = a << 2;

2.68

编写一个函数，生成一个掩码，将最低 $n$ 位置为 1 。其中 $1\leq n\leq w$ 。注意 $n=w$ 的情况。

1
2
3

int lower_one_mask(int n) {
    return (2 << (n - 1)) - 1;
}

2.69

写出一个具有以下原型的函数代码：

1 2 3 4 5 6 7

> /* > * Do rotating left shift. Assume 0 <= n <= w > * Examples when x = 0x12345678 and w = 32: > * n=4 -> 0x23456781, n=20 -> 0x67812345 > */ > unsigned rotate_left(unsigned x, int n); >

左移过程中，一部分位被舍去，一部分位被保留，因此我们考虑分成两部分来处理。

1
2
3
4
5
6

unsigned rotate_left(unsigned x, int n) {
    int w = sizeof(int) << 3;
    unsigned left = x << n;
    unsigned right = (x & ~((2 << (w - n - 1)) - 1)) >> (w - n);
    return left | right;
}

这里要特别注意第4行，需要处理好 $n=0$ 的情况，因此使用了 2 << (w - n - 1) 。这一行的意思是取出 x 的前 n 位然后右移 w-n 位，得到右边的部分。

2.70

编写一个函数，当 $x$ 可以被表示为 $n$ 位补码时返回1，否则返回0。其中 $1\leq n\leq w$ 。

本题其实是要看 $x$ 是否在 $-2^{n-1}$ ～ $2^{n-1} -1$ 这个闭区间内。如果 $x$ 满足这个条件，那么第 $n-1$ 位就是符号位，它以上的 $w-n$ 位都与第 $n-1$ 位相同。所以考虑将 $x$ 右移 $n-1$ 位，如果得到的数是全1或者全0，那么就说明它可以被 $n$ 位补码表示出来。

1
2
3
4

int fits_bits(int x, int n) {
    x >>= n - 1;
    return (!x) || (!~x);
}

2.71

题目太长不写了。

1. 题目中给出的代码返回的是 unsigned 类型，右移时使用了逻辑右移，不能返回题目要求的 int 类型。
2. 重写如下：

1
2
3
4

int xbyte(packed_t word, int bytenum) {
    int temp = word << ((3 - bytenum) << 3);
    return temp >> 24;
}

2.72

1. 给出的代码中采用 maxbytes - sizeof(val) >= 0 来判断是否进行 memcpy() 函数。本章笔记中我们也提到，无符号类型比有符号类型级别高，两种类型进行运算时会转化成 unsigned 来进行。sizeof() 函数返回的类型是 size_t ，而这一标识符在 <stdio.h> 中被定义为 unsigned ，因此即使 maxbytes < sizeof(val) ，它们相减都会得到一个无符号数，而它一定是非负的。
2. 将 maxbytes - sizeof(val) >= 0 替换为 maxbytes > 0 && maxbytes >= sizeof(val) 。注意前面的那个条件是必需的，否则若 maxbytes 为负数，在比较时也会被转化为正数，后面的逻辑运算可能也会出现问题。

2.73

实现饱和加法，将两个 int 类型的数 $x$ 和 $y$ 相加，若正溢出返回 INT_MAX ，负溢出返回 INT_MIN ，无溢出返回其和。

由于本章习题限制不能使用条件语句，我们只能用位运算来解决这些问题。32位 int 表达中，INT_MAX 的值为 0x7FFFFFFF ，INT_MIN 的值为 0x80000000 。考虑以下几种情况：

• $x, y$ 异号，则一定不会发生溢出。
• $x,y>0$，此时可能发生正溢出。
• $x,y<0$ ，此时可能发生负溢出。

因此我们可以提取 $x,y,x+y$ 三者的符号位（用右移运算），来看是否会发生溢出情况。由于右移是算术右移，直接右移 $w-1$ 位就可以得到全1或全0的一个数，表示符号。直接用位运算来表示是否溢出，则这些标记量也是全1或全0的数，且三个标记量中仅有一个是全1，剩下两个都是全0。因此可以考虑将三个标记量与其分别对应的结果进行 & 运算，再一起进行 | 运算，这样可以不用分支结构来完成这个任务。

1
2
3
4
5
6
7
8
9
10
11
12

int saturate_add(int x, int y) {
    int sum = x + y;
    int t = sum;
    int w = sizeof(int) << 3;
    x >>= w - 1;
    y >>= w - 1;
    t >>= w - 1;
    int pos_ovf = ~x & ~y & t; // x 和 y 为正而 t 为负
    int neg_ovf = x & y & ~t; // x 和 y 为负而 t 为正
    int not_ovf = ~(pos_ovf | neg_ovf); // 既未正溢出也未负溢出
    return (pos_ovf & INT_MAX) | (not_ovf & sum) | (neg_ovf & INT_MIN); 
}

2.74

编写函数 tsub_ok(int x, int y) 来检测 $x-y$ 是否溢出。

设 $t=x-y$ ，并将 $t$ 转换为 $w$ 位补码，则有以下结论：

• $xy \geq 0$ ，即 $x$ 和 $y$ 同号时，一定不发生溢出。
• $x>0,y<0$ ，此时可能发生正溢出，结果 $t<0$ 。
• $x<0,y>0$ ，此时可能发生负溢出，结果 $t>0$ 。

综上，溢出的充要条件是 $yt>0,xy<0$ 。继续沿用上一题的想法，写出如下函数：

1
2
3
4
5
6
7
8

int tsub_ok(int x, int y) {
    int w = sizeof(int) << 3;
    int t = x - y;
    x >>= w - 1;
    y >>= w - 1;
    t >>= w - 1;
    return (x != y) && (y == t);
}

2.75

已知有函数 int signed_high_prod(int x, int y) 计算整型变量 x 和 y 相乘后高 $w$ 位的值。请编写 unsigned unsigned_high_prod(unsigned x, unsigned y) 来计算无符号型变量相乘后高 $w$ 位的值。

由书中公式 2.18 可知，整型乘法和无符号类型的乘法在位级水平上是相同的。设 $x’$ 和 $y’$ 分别是 $x$ 和 $y$ 的无符号类型值，那么有：
$$
x’\cdot y’= (x + x_{w-1}\cdot 2^w)\cdot (y+y_{w-1}\cdot 2^w) = x\cdot y + (x_{w-1}\cdot y + y_{w-1}\cdot x)\cdot 2^w + 2^{2w}
$$
于是，$x’\cdot y’$ 的高 $w$ 位的计算方法如下：

1
2
3

unsigned unsigned_high_prod(unsigned x, unsigned y) {
    return signed_high_prod((int) x, (int) y) + y & ((int) x >> (w - 1)) + x & ((int) y >> (w - 1));
}

2.76

库函数 calloc 有如下声明：void *calloc(size_t nmemb, size_t size); 。根据库文档：“函数 calloc 为一个数组分配内存，该数组有 nmemb 个元素，每个元素为 size 字节。内存设置为0。如果 nmemb 或 size 为0，则 calloc 返回 NULL 。”

编写 calloc 的实现，通过调用 malloc 执行分配，调用 memset 将内存设置为0。你的代码应该没有任何由算术溢出引起的漏洞，且无论数据类型 size_t 用多少位表示，代码都应该正常工作。

作为参考，函数 malloc 和 memset 声明如下：

1 2 3

> void *malloc(size_t size); > void *memset(void *s, int c, size_t n); >

本题没有说要按照整数位级编码规则，因此应该可以使用乘法和条件语句吧。于是这个问题好像没有那么难？

1
2
3
4
5
6
7
8
9
10
11
12

void *calloc(size_t nmemb, size_t size) {
    if (!(nmemb & size)) {
        return NULL;
    }
    size_t prod = nmemb * (size << 3);
    if (size == prod / nmemb) {
        void *p = malloc(prod);
        memset(p, 0, prod);
        return p;
    }
    return NULL;
}

2.77

假设我们有一个任务：生成一段代码，将整数变量 x 乘以不同的常数因子 $K$ 。为了提高效率，我们想只使用 + - << 运算。对于下列 $K$ 的值，写出执行乘法运算的 C 表达式，每个表达式中最多使用 3 个运算。

• $K=17$
• $K=-7$
• $K=60$
• $K=-112$

• (x << 4) + x
• x - (x << 3)
• (x << 6) - (x << 2)
• (x << 4) - (x << 7)

2.78

写出具有如下原型的函数的代码：

1 2 3

> /* Divide by power of 2. Assume 0 <= k < w-1 */ > int divide_power2(int x, int k); >

首先计算 x >> k ，然后考虑除法的向零舍入，即 $x<0$ 且 $x$ 的最后 $k$ 位不为零时要加一。

1
2
3
4
5
6

int divide_power2(int x, int k) {
    int q = x >> k;
    int w = sizeof(int) << 3;
    ans += (x >> (w - 1)) && (x & ((1 << k) - 1));
    return ans;
}

2.79

写出函数 mul3div4 的代码，对于整数参数 x ，计算 3*x/4，但是要遵循位级整数编码规则。你的代码计算 3*x 也会产生溢出。

利用上一题的思想，在 $x<0$ 时再进行舍入的操作。

1
2
3
4
5
6

int mul3div4(int x) {
    int prod = (x << 1) + x;
    int sign = !!(prod & INT_MIN);
    int bias = !sign && (x & 0x3); // 除以4时最后2位不为0且为负数时要加1
    return (prod >> 2) + bias;
}

2.80

写出函数 threefourths 的代码。对于整数参数 x ，计算 $\frac 34 x$ 的值，向零舍入。它不会溢出。函数应该遵循位级整数编码规则。

1
2
3

int threefourths(int x) {
    return ((x >> 2) << 1) + (x << 2) + ((((x & 3) << 1) + (x & 3)) >> 2);
}

2.81

编写 C 表达式产生如下位模式，其中 $a^k$ 表示符号 $a$ 重复 $k$ 次。假设一个$w$ 位的数据类型。代码可以包含对参数 j 和 k 的引用，它们分别表示 $j$ 和 $k$ 的值，但是不能使用表示 $w$ 的参数。

1. $1^{w-k} 0^k$
2. $0^{w-k-j} 1^k 0^j$

1. ~0 << k
2. ((1 << k) - 1) << j

（未完，待续）

信息存储

十六进制与字节顺序

在计算机中，信息的存储均为二进制位(bit)的形式。每八个二进制位就形成一个字节(byte)。由于二进制位的表示将会把数字拉得很长，通常我们会用十六进制来表示。每个十六进制位都恰好表示四个二进制位，高位补0。

内存中的空间是以字节为单位的。而一个字节只有8位，可以存储的数据非常少。因此跨字节的存储就成为了必需。这也就意味着对于内存中的对象，我们需要两个规则：

• 这个对象的地址是什么？
• 内存中这些字节如何排列？

在所有的机器上，跨越多个字节的数据都是连续存储的，其地址为它所使用的字节中地址最小的一个。例如 int 型变量 x 需要用4个字节，分别为0x100 0x101 0x102 0x103， 那么 &x 的值就是 0x100。但是 x 的四个字节在其中如何排列又成为了一个问题。设 x = 0x01234567，那么它的排列可能是 01 23 45 67 也有可能是 67 45 23 01。前者小端在前，称为小端法(little endian)；后者大端在前，称为大端法(big endian)。

字长

每台计算机都有一个字长(word size)，表明一个指针数据的标称大小。旧一些的机器通常是32位字长的，意味着它可以访问的字节数为 $2^{32}-1$。这样的空间总和大约为4GB，也就是说32位的机器最多只支持4GB的内存。而目前市面上的机器字长都是64位，其虚拟地址空间为16EB（$1.84\times 10^{19}$字节），远远超出我们现在所使用的空间了。一般地，字长为 $w$ 的机器，虚拟地址的范围为0到 $2^w-1$。同时需要强调，无论指针的类型如何，因为它表示的都是一个虚拟地址，所以其位数不变。在64位机器上，尽管 char 类型只有一个字节，但是 char *则会被分配8个字节。

字符与字符串

在C语言中，字符用 char 类型表达，占一个字节。这一个字节表示一个整数，它与不同的字符之间有一个映射规则，即 ASCII。因此字符型的变量存储和整数没有区别。字符串则是一个由字符组成的数组，并在其结尾有一个 \0，其 ASCII 码为0，标志着字符串的结尾。

布尔代数

布尔运算

布尔运算有& | ~ ^ 四种，分别为与、或、非和异或。它们的操作数只有0和1两种。其运算规则如下：

• 与：1 & 1 = 1，其余情况为0；
• 或：0 & 0 = 0，其余情况为1；
• 非：~1 = 0 ，~0 = 1；
• 异或：两数同为1或同为0得0，否则得1；

位级运算

在C语言中，同样的运算符将对操作数进行按位布尔运算。例如：

• ~0x41 = ~[01000001] = [10111110] = 0xBE；
• 0x69 & 0x55 = [01101001] & [01010101] = [01000001] = 0x41；
• 0x69 | 0x55 = [01101001] & [01010101] = [01111101] = 0x7D；

位级运算的重要作用之一是实现掩码运算。若要保留某个位，可用 &1或者|0；将某些位置为0，可用 &0；将某个位置为1，可用 |1。

逻辑运算

逻辑运算有三种：逻辑与&&，逻辑或||，逻辑非!。其运算规则是：

• 逻辑与：非零和非零得1，反之为0；
• 逻辑或：零和零得0，反之为1；
• 逻辑非：非零得0，零得1；

移位运算

C语言中有左移<<和右移>>两种移位运算。左移时低位补0，高位舍去；右移时则分为逻辑右移和算术右移两种。逻辑右移高位直接补0，而算术右移高位将补原来数的最高位。

对一个 $w$ 位存储的整数，向左移位时最多可以移动 $w - 1$ 位。考虑表达式 x << m ，若 $m >= w$ ，那么计算机会先进行 m %= w 的运算。也就是说，如果 $m=w$，那么 x << m 的值将与 x 完全相同。

整数的表达

整数的类型

在C语言中，一般有 char short int long long long 几种。它们占的内存（一般）为1、2、4、4、8字节。它们还有各自的无符号类型。无符号类型就只能表达非负数。

无符号数与有符号数

对有 $w$ 位来存储的整型变量，若为无符号类型，则其表达范围为0～$2^w-1$；若为有符号类型，则其表达范围为 $-2^w$ ～ $2^w - 1$。以下均认为我们所指的整型变量由 $w$ 位存储。

对无符号数而言，自右向左第 $k$ 位的权重为 $2^{k-1}$。所有位的加权和即为其表示的十进制值。对有符号数而言，最高位的权重为 $-2^w$，其余与无符号数相同。这样的表达也称为整数的补码表示。在这样的编码规则下，非负数的补码和原码相同，负数的补码是其相反数按位取反再加1。

这里需要注意，在32位 int 类型中，如果要表达 -2147483648 这个32位整数可以表达的最小值，一定要用 -2147483647-1 来表示。否则计算机将对 2147483648 这一个数取相反数。但是这个数已经超出了32位整型能表达的范围，就会出现问题。

另外，无符号类型的等级比有符号类型要高。因此如果无符号数和有符号数进行运算，结果将返回无符号数。如以下代码：

1
2
3
4
5
6
7
8

double sum_elements(double a[], unsigned length) {
    int i;
    double result = 0;
    for (i = 0; i <= length - 1; ++i) {
        result += a[i];
    }
    return result;
}

若 length == 0 ，那么在 for 循环中，length - 1 就会返回无符号数的最大值 $2^{32} - 1$，从而在访问 a[i] 时出现下标越界的状况。将 i <= length - 1 改为 i < length 即可解决这个问题。同样的道理，在无符号数的运算中，x - y > 0 和 x > y 可能会产生不同的结果。

溢出

由于存储的空间有限，一旦运算结果超出了可存储数的范围，就是出现溢出。这个时候，计算机会保留运算结果中较低的 $w$ 位。

加法

对无符号数而言，$0\leq x, y \leq 2^w - 1$ ，因此 $0\leq x + y\leq 2^{w+1}-2$ 。令 $z = x + y$，当 $0\leq z \leq 2^w - 1$ 时，不会发生溢出。但是当 $2^w\leq z\leq 2^{w+1} - 2$ 时，最高位超出了 $w$ 位的表示范围，于是得到的结果 $z’ = z\mod 2^w$。

对有符号数而言，$-2^{w-1}\leq x,y\leq 2^{w-1} - 1​$，因此 $-2^w\leq x+y\leq 2^w - 2​$。令 $z=x+y​$，当 $-2^{w-1}\leq z\leq 2^{w-1} - 1​$ 时不会发生溢出。当 $2^{w-1}\leq z\leq 2^w-2​$，最高位出现一个权重为 $2^w​$ 的进位会被舍去，于是 $z’=z-2^w<0​$，称为正溢出（得到负数）。当 $-2^w\leq z\leq 2^{w-1}​$，最高位出现退位，$z’=z+2^w>0​$，称为负溢出（得到正数）。

乘法

类似的，乘法也会出现对应的溢出。

对两个无符号数 $x, y$，$0\leq x, y \leq 2^w - 1$。令 $z=x\cdot y$，则有 $0\leq z\leq 2^{2w} - 2^{w+1}+1$。然而一个无符号数 $z$ 若没有溢出，它应该满足 $0\leq z \leq 2^w-1$。在 $2^w\leq z\leq 2^{2w} - 2^{w+1}+1$ 的情况下都会出现溢出。此时将直接取低 $w$ 位。

有符号数的乘法在位级水平上与无符号数完全相同。因此只要将 $x\cdot y$ 的二进制表示取低 $w$ 位作为补码解读，即可得到计算的结果。考虑表达式 x * x，在不溢出的情况下它应该是一个大于等于0的数。设 $z=x^2$，那么不溢出的范围应该是 $z < 2^{31}$。因此只要 $x\geq 2^{15.5}\approx 46341$ 就会发生溢出。事实上，若 $x=2^{16}-1=65535$，则由以下代码可以得到一个小于0的值：

1
2
3
4
5
6

#include <stdio.h>
int main(void) {
    int x = 0xFFFF;
    printf("%d %X\n", x * x, x * x);
    return 0;
}

其输出为 -131071 FFFE0001，即我们算出了一个小于0的 x * x。这其实取决于 $x^2$ 二进制表示的第 $w-1$ 位，只要它是1就可以得到这样一个正溢出的效果。

乘法和除法的优化

从机器的水平上，乘法和除法是非常消耗时间的。乘法大约需要10个时钟周期，而除法则需要30多个。与此相比，加减和位运算则都只需要1个时钟周期。所以将乘法和除法优化为移位和加减将让程序执行的时间大大减少。

在十进制中，一次向左移位就意味着将原来的数乘以10。计算机中使用二进制，同理可得向左移一位就是将原来的数乘以2。假设现在我们有整数 $x$ 和常数 $y$ ，要计算 $x\cdot y$ 。若 $y=2^k$ ，那么 x * y 和 x << k 的值完全相等。我们知道，$y$ 可以被表示为一个二进制数 $(y_{w-1}\cdots y_1y_0)_2$ ，因此我们有：
$$
y=\sum_{i=0}^{w - 1}y_i2^i
$$
所以可以把其中为1的位都提出来，依次移位再相加。例如要计算 x * 14，而 $14=2^3+2^2+2^1​$ 。所以这个运算可以被优化成 (x << 3) + (x << 2) + (x << 1)。又 $14=2^4-2^1​$，它也可以被优化为 (x << 4) - (x << 1)。这一特性可以被用于解决 LeetCode 29: Divide two integers。

浮点数

浮点数是对形如 $V=x\times 2^y$ 的有理数进行编码的方案。这里说是有理数，是因为有限位的 $p$ 进制小数只能表示出有理数。这一种存储方案使我们可以对很小和很大的数进行方便的运算。

二进制小数的表示

一般地，对于一个 $p$ 进制的小数 $V$，我们可以将其表示为如下形式：
$$
V=\left(b_mb_{m-1}\cdots b_2b_1b_0.b_{-1}b_{-2}\cdots b_{-n+1}b_{-n}\right)_p
$$
其中，对 $-n\leq i\leq m$，均有 $0\leq b_i<p$，而 $b_i$ 的权重为 $p^{i}$。故有：
$$
V=\sum_{i=-n}^{m}b_ip^i
$$
特别地，当 $p=2$ 时，就可以得到一个二进制小数了。

IEEE浮点数

如何用一段二进制码来表示一个浮点数是一个非常重要的问题。为此 IEEE（电气和电子工程师协会）制订了浮点数的编码标准。显而易见地，用越多的字节来编码浮点数，我们就可以获得更广的表示范围和更高的精度。IEEE 定义了单精度浮点数（4字节）和双精度浮点数（8字节）。

IEEE 标准是这样的。对于一个浮点数 $V$，我们将它表示为 $V=(-1)^s\times M\times 2^E$ 的形式。其中 $s$ 称为符号 (sign)，用一位0或1来表示。$M$ 称为尾数 (significand)，它是一个二进制小数。$E$ 称为阶码 (exponent)，简单理解就是指数。将这三段拼在一起，就成为了一个 IEEE 浮点数的二进制表达。因此，假如用 $w$ 位来表达这个浮点数，就需要将这段空间划分为三段，方案如下：

• 最左边的1位为符号位 $s$。
• 阶码字段 $k$ 位，编码阶码 $E$。
• $n$ 位小数字段，编码尾数 $M$。

在单精度浮点数中，$k=8,n=23$；双精度浮点数中，$k=11,n=52$。在了解这个编码方案后我们首先发现的问题就是如何处理0。由于有独立的符号位，可能出现 $+0$ 和 $-0$ 两种。这也是 IEEE 浮点数的一个特性。依据阶码的情况，IEEE 将浮点数分为以下三种：

• 规格化的值：$E\neq 0$ 且 $E\neq 2^k-1$。
• 非规格化的值：$E=0$。
• 特殊值：$E=2^k-1$。

规格化的值

在规格化的值中，阶码字段 $E$ 以无符号数的形式来表示一个有符号数（因为阶码确实需要负数，但补码用着不方便），因此会产生一个偏置 (bias)。我们用 $B$ 来表示这个偏置量，$B=2^{k-1}-1$。因此，若 $E$ 的无符号数对应值是 $e$，那么 $E=e-B$。

小数字段被解释为小数值 $f$，其中 $f\in [0,1)$。这里 $f=M-1$。$f$ 的二进制表示为 $0.f_{n-1}\cdots f_1f_0$。其实在这里 $V$ 就是被表示成了二进制下的科学记数法，前面被乘的部分 $M$ 应该满足 $1\leq M<2$，因此一定有一位1。由于是二进制，这里小数点前面一位只可能是1，为我们的编码省下了一位。

非规格化的值

当阶码字段为全0时，阶码值 $E=1-B$。这里多出来的1为非规格化的值与规格化的值无缝衔接提供了必要的保障。此时 $M=f$，没有开头隐含的1。这为我们表示数字 $0$ 提供了可能。它表示非常接近0的那些数。

特殊值

特殊值的阶码字段为全1。当小数域为全0时，它表示无穷。$s=0$ 时为 $+\infty$，$s=1$ 时为 $-\infty$。它可以表示溢出的结果。而当小数域不是全0，它表示 NaN (Not a Number)，比如 $\sqrt{-1}$ 。

这样的表示方法提供了极大的运算便利，即小数段的进位一旦溢出，恰好会落入阶码字段，这是一个非常神奇的巧合。

浮点数的舍入

由于二进制小数不能精确地表达十进制小数的值，它需要进行适当地舍入(rounding)。计算机中的舍入和我们日常所说的“四舍五入”是不太一样的。IEEE 定义了向偶数舍入、向零舍入、向下舍入和向上舍入四种舍入方式。首先我们解释后三种。向下舍入和向上舍入分别表示下取整和上取整。向零舍入则是对正数向下舍入，而对负数向上舍入。

向偶数舍入的基本原则是“四舍六入五取偶”。即1.5和2.5保留整数均为2，因为2是偶数。而2.51保留整数则应该为3，因为2.51并不会是2和3之间的正中间值。如果所有的5都要进一的话，最终的平均值计算下来很有可能会偏大。因此向偶数舍入可以在统计上保持平均值的稳定。

相似地，在二进制小数中，我们认为0是偶数，1是奇数，而如果需要保留的最低有效位后是 $1000\cdots$ 这样的串，那么在舍入时将在最低有效位取偶数。举例如下（保留小数点后2位）：

• $10.00110 \approx 10.01$
• $10.00011 \approx 10.00$
• $10.11100 \approx 11.00$
• $10.10100 \approx 10.10$

观察以上小数，从小数点后第3位起将被舍入。若小数点后第3–5位组成 100 串，则需要对小数点后第2位取偶，因为它们可能是上下两个可能值的正中间值。

小结

本章对于信息在计算机中的存储形式做了深度讲解。虽然知识点总结出来不多，但是还是需要大量的手算和练习去对布尔代数和位运算有基本的把握。由于存储空间的有限和运算精度的有限，计算机并不总能得到我们想要的答案。从这一章中可以找到以往编程中出现过的各种不能理解的错误，也可以学到一些位运算的奇技淫巧。大量的练习和实践仍然是掌握知识最重要的途径。

听说想写代码挣钱的话，买书的钱加起来就是第一个月工资。终于没有嫌书贵，下手买了《深入理解计算机系统（第3版）》。为了保证学习效果，我自己在这里开一个小栏目做重点记录和习题解答。我对 C 语言相对熟练，于是决定啃一下这块硬骨头，希望能有毅力一直写下去。

这个国庆假期最初的计划是借10月8、9日的调休和天一去大同和平遥玩耍几日避开高峰，后来她因为实习上班就没有能够付诸实施。于是作为一个替代计划，我们把目的地改成了京郊的十渡。

这个中秋终于拍到一个能看的月亮了。

所以这个博客终于搭起来了。