第 2 章家庭作业：2.61～2.81

位级整数编码规则

在接下来的作业中，我们特意限制了你能使用的编程结构，来帮你更好地理解 C 语言的位级、逻辑和算术运算。在回答这些问题时，你的代码必须遵守以下规则：

假设

整数用补码形式表示。
有符号数的右移是算术右移。
数据类型 int 是 w 位长的。对于某些题目，会给定 w 的值，但是在其他情况下，只要 w 是 8 的整数倍，你的代码就应该能工作。你可以用表达式 sizeof(int)<<3 来计算 w。

禁止使用

条件语句（if 或者 ?:）、循环、分支语句、函数调用和宏调用。
除法、模运算和乘法。
相对比较运算（<、>、<= 和 >=）。

允许的运算

所有的位级和逻辑运算。
左移和右移，但是位移量只能在 0 和 w-1 之间。
加法和减法。
相等（==）和不相等（!=）测试。（在有些题目中，也不允许这些运算。）
整型常数 INT_MIN 和 INT_MAX。
对 int 和 unsigned 进行强制类型转换，无论是显式的还是隐式的。

即使有这些条件的限制，你仍然可以选择带有描述性的变量名，并且使用注释来描述你的解决方案的逻辑，尽量提高代码的可读性。例如，下面这段代码从整数参数 x 中抽取出最高有效字节：

/* Get most significant byte from x */
int get_msb(int x) {
    /* Shift by w-8 */
    int shift_val = (sizeof(int)-1)<<3;
    /* Arithmetic shift */
    int xright = x >> shift_val;
    /* Zero all but LSB */
    return xright & 0xFF;
}

家庭作业 2.61（★★）写一个 C 表达式，在下列描述的条件下产生 1，而在其他情况下得到 0。假设 x 是 int 类型。

A. x 的任何位都等于 1。

B. x 的任何位都等于 0。

C. x 的最低有效字节中的位都等于 1。

D. x 的最高有效字节中的位都等于 0。

代码应该遵循位级整数编码规则，另外还有一个限制，你不能使用相等（==）和不相等（!=）测试。

家庭作业 2.62（★★★）编写一个函数 int_shifts_are_arithmetic()，在对 int 类型的数使用算术右移的机器上运行时这个函数生成 1，而其他情况下生成 0。你的代码应该可以运行在任何字长的机器上。在几种机器上测试你的代码。

家庭作业 2.63（★★★）将下面的 C 函数代码补充完整。函数 srl 用算术右移（由值 xsra 给出）来完成逻辑右移，后面的其他操作不包括右移或者除法。函数 sra 用逻辑右移（由值 xsrl 给出）来完成算术右移，后面的其他操作不包括右移或者除法。可以通过计算 8*sizeof(int) 来确定数据类型 int 中的位数 w。位移量 k 的取值范围为 0～w-1。

unsigned srl(unsigned x, int k) {
    /* Perform shift arithmetically */
    unsigned xsra = (int) x >> k;

    /* ... */
}

int sra(int x, int k) {
    /* Perform shift logically */
    int xsrl = (unsigned) x >> k;

    /* ... */
}

家庭作业 2.64（★）写出代码实现如下函数：

/* Return 1 when any odd bit of x equals 1; 0 otherwise.
   Assume w=32 */
int any_odd_one(unsigned x);

函数应该遵循位级整数编码规则，不过你可以假设数据类型 int 有 w=32 位。

家庭作业 2.65（★★★）写出代码实现如下函数：

/* Return 1 when x contains an odd number of 1s; 0 otherwise.
   Assume w=32 */
int odd_ones(unsigned x);

函数应该遵循位级整数编码规则，不过你可以假设数据类型 int 有 w=32 位。

你的代码最多只能包含 12 个算术运算、位运算和逻辑运算。

家庭作业 2.66（★★★）写出代码实现如下函数：

/*
 * Generate mask indicating leftmost 1 in x. Assume w=32.
 * For example, 0xFF00 -> 0x8000, and 0x6600 --> 0x4000.
 * If x = 0, then return 0.
 */
int leftmost_one(unsigned x);

函数应该遵循位级整数编码规则，不过你可以假设数据类型 int 有 w=32 位。

你的代码最多只能包含 15 个算术运算、位运算和逻辑运算。

提示： 先将 x 转换成形如 [0...011...1] 的位向量。

家庭作业 2.67（★★）给你一个任务，编写一个过程 int_size_is_32()，当在一个 int 是 32 位的机器上运行时，该程序产生 1，而其他情况则产生 0。不允许使用 sizeof 运算符。下面是开始时的尝试：

/* The following code does not run properly on some machines */
int bad_int_size_is_32() {
    /* Set most significant bit (msb) of 32-bit machine */
    int set_msb = 1 << 31;
    /* Shift past msb of 32-bit word */
    int beyond_msb = 1 << 32;

    /* set_msb is nonzero when word size >= 32
       beyond_msb is zero when word size <= 32 */
    return set_msb && !beyond_msb;
}

当在 SUN SPARC 这样的 32 位机器上编译并运行时，这个过程返回的却是 0。下面的编译器信息给了我们一个问题的指示：

warning: left shift count >= width of type

A. 我们的代码在哪个方面没有遵守 C 语言标准？

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

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

家庭作业 2.68（★★）写出具有如下原型的函数的代码：

/*
 * Mask with least significant n bits set to 1
 * Examples: n = 6 --> 0x3F, n = 17 --> 0x1FFFF
 * Assume 1 <= n <= w
 */
int lower_one_mask(int n);

函数应该遵循位级整数编码规则。要注意 n=w 的情况。

家庭作业 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);

函数应该遵循位级整数编码规则。要注意 n=0 的情况。

家庭作业 2.70（★★）写出具有如下原型的函数的代码：

/*
 * Return 1 when x can be represented as an n-bit, 2's-complement
 * number; 0 otherwise
 * Assume 1 <= n <= w
 */
int fits_bits(int x, int n);

函数应该遵循位级整数编码规则。

家庭作业 2.71（★）你刚刚开始在一家公司工作，他们要实现一组过程来操作一个数据结构，要将 4 个有符号字节封装成一个 32 位 unsigned。一个字中的字节从 0（最低有效字节）编号到 3（最高有效字节）。分配给你的任务是：为一个使用补码运算和算术右移的机器编写一个具有如下原型的函数：

/* Declaration of data type where 4 bytes are packed
   into an unsigned */
typedef unsigned packed_t;

/* Extract byte from word. Return as signed integer */
int xbyte(packed_t word, int bytenum);

也就是说，函数会抽取出指定的字节，再把它符号扩展为一个 32 位 int。

你的前任（因为水平不够高而被解雇了）编写了下面的代码：

/* Failed attempt at xbyte */
int xbyte(packed_t word, int bytenum)
{
    return (word >> (bytenum << 3)) & 0xFF;
}

A. 这段代码错在哪里？

B. 给出函数的正确实现，只能使用左右移位和一个减法。

家庭作业 2.72（★★）给你一个任务，写一个函数，将整数 val 复制到缓冲区 buf 中，但是只有当缓冲区中有足够可用的空间时，才执行复制。

你写的代码如下：

/* Copy integer into buffer if space is available */
/* WARNING: The following code is buggy */
void copy_int(int val, void *buf, int maxbytes) {
    if (maxbytes-sizeof(val) >= 0)
        memcpy(buf, (void *) &val, sizeof(val));
}

这段代码使用了库函数 memcpy。虽然在这里用这个函数有点刻意，因为我们只是想复制一个 int，但是它说明了一种复制较大数据结构的常见方法。

你仔细地测试了这段代码后发现，哪怕 maxbytes 很小的时候，它也能把值复制到缓冲区中。

A. 解释为什么代码中的条件测试总是成功。提示：sizeof 运算符返回类型为 size_t 的值。

B. 你该如何重写这个条件测试，使之工作正确。

家庭作业 2.73（★★）写出具有如下原型的函数的代码：

/* Addition that saturates to TMin or TMax */
int saturating_add(int x, int y);

同正常的补码加法溢出的方式不同，当正溢出时，饱和加法返回 TMax，负溢出时，返回 TMin。饱和运算常常用在执行数字信号处理的程序中。

你的函数应该遵循位级整数编码规则。

家庭作业 2.74（★★）写出具有如下原型的函数的代码：

/* Determine whether arguments can be subtracted without overflow */
int tsub_ok(int x, int y);

如果计算 x-y 不溢出，这个函数就返回 1。

家庭作业 2.75（★★★）假设我们想要计算 x · y 的完整的 2w 位表示，其中，x 和 y 都是无符号数，并且运行在数据类型 unsigned 是 w 位的机器上。乘积的低 w 位能够用表达式 x*y 计算，所以，我们只需要一个具有下列原型的函数：

unsigned unsigned_high_prod(unsigned x, unsigned y);

这个函数计算无符号变量 x · y 的高 w 位。

我们使用一个具有下面原型的库函数：

int signed_high_prod(int x, int y);

它计算在 x 和 y 采用补码形式的情况下，x · y 的高 w 位。编写代码调用这个过程，以实现用无符号数为参数的函数。验证你的解答的正确性。

提示： 看看等式（2.18）的推导中，有符号乘积 x · y 和无符号乘积 x′ · y′ 之间的关系。

家庭作业 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 声明如下：

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

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

A. K=17

B. K=-7

C. K=60

D. K=-112

家庭作业 2.78（★★）写出具有如下原型的函数的代码：

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

该函数要用正确的舍入方式计算 x/2^k，并且应该遵循位级整数编码规则。

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

家庭作业 2.80（★★★）写出函数 threefourths 的代码，对于整数参数 x，计算 3/4 x 的值，向零舍入。它不会溢出。函数应该遵循位级整数编码规则。

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

A. 1^w-k0^k

B. 0^w-k-j1^k0^j