重点练习

2.10

考虑如下代码：

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

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

步骤	`*x`	`*y`
初始	`a`	`b`
第一步	`a`	`a ^ b`
第二步	`a ^ (a ^ b) = b`	`a ^ b`
第三步	`b`	`b ^ (a ^ b) = a`

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

2.15

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

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

2.21

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

表达式	类型	求值
`-2147483647-1 == 2147483648U`	无符号	1
`-2147483647-1 < 2147483647`	有符号	1
`-2147483647-1U < 2147483647`	无符号	0
`-2147483647-1 < -2147483647`	有符号	1
`-2147483647-1U < -2147483647`	无符号	1

在运算时，无符号类型比有符号类型的等级要高。只要两个操作数之中有一个是无符号数，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$ 的情况即可：

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;
}

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

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

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$ 位之后是否相等即可。代码如下：

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，那就是小端法，否则是大端法。

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

2.59

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

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

2.60

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。要求在任意字长的机器上都可以运行。

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

2.63

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

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

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 分为左右两段来处理。

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位对齐后异或，直到最后剩一位，就是我们要的答案。

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而要用异或来解决。

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;
> }
>

请回答：

这份代码在哪个方面没有遵守 C 语言标准？

修改代码使得它在 int 至少为32位的任何机器上都能正确地运行。

修改代码使得它在 int 至少为16位的任何机器上都能正确地运行。

在第3行，左移运算的右值为32，在 int 为32位的机器上是不合法的，超过了左值的宽度。
将第3行修改为 int beyond_msb = 2 << 31;
若要支持至少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

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

> /*
>  * 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);
>

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

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$ 位补码表示出来。

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

2.71

题目太长不写了。

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

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

2.72

给出的代码中采用 maxbytes - sizeof(val) >= 0 来判断是否进行 memcpy() 函数。本章笔记中我们也提到，无符号类型比有符号类型级别高，两种类型进行运算时会转化成 unsigned 来进行。sizeof() 函数返回的类型是 size_t ，而这一标识符在 <stdio.h> 中被定义为 unsigned ，因此即使 maxbytes < sizeof(val) ，它们相减都会得到一个无符号数，而它一定是非负的。
将 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。因此可以考虑将三个标记量与其分别对应的结果进行 & 运算，再一起进行 | 运算，这样可以不用分支结构来完成这个任务。

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$ 。继续沿用上一题的想法，写出如下函数：

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

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

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$ 位不为零时要加一。

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$ 时再进行舍入的操作。

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^{w-k} 0^k$

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

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

（未完，待续）