2.1.7 C 语言中的位级运算

C 语言的一个很有用的特性就是它支持按位布尔运算。事实上，我们在布尔运算中使用的那些符号就是 C 语言所使用的：| 就是 OR（或），& 就是 AND（与），~ 就是 NOT（取反），而 ^ 就是 EXCLUSIVE-OR（异或）。这些运算能运用到任何“整型”的数据类型上，包括图 2-3 所示内容。以下是一些对 char 数据类型表达式求值的例子：

C 的表达式	二进制表达式	二进制结果	十六进制结果
~0x41	~[0100 0001]	[1011 1110]	0xBE
~0x00	~[0000 0000]	[1111 1111]	0xFF
0x69&0x55	[0110 1001]&[0101 0101]	[0100 0001]	0x41
0x69\|0x55	[0110 1001]\|[0101 0101]	[0111 1101]	0x7D

正如示例说明的那样，确定一个位级表达式的结果最好的方法，就是将十六进制的参数扩展成二进制表示并执行二进制运算，然后再转换回十六进制。

练习题 2.10 对于任一位向量 a，有 a ^ a = 0。应用这一属性，考虑下面的程序：

void inplace_swap(int *x, int *y) {
    *y = *x ^ *y;  /* Step 1 */
    *x = *x ^ *y;  /* Step 2 */
    *y = *x ^ *y;  /* Step 3 */
}

正如程序名字所暗示的那样，我们认为这个过程的效果是交换指针变量 x 和 y 所指向的存储位置处存放的值。注意，与通常的交换两个数值的技术不一样，当移动一个值时，我们不需要第三个位置来临时存储另一个值。这种交换方式并没有性能上的优势，它仅仅是一个智力游戏。

以指针 x 和 y 指向的位置存储的值分别是 a 和 b 作为开始，填写下表，给出在程序的每一步之后，存储在这两个位置中的值。利用 ^ 的属性证明达到了所希望的效果。回想一下，每个元素就是它自身的加法逆元（a ^ a = 0）。

步骤	*x	*y
初始	a	b
第1步
第2步
第3步

练习题 2.11 在练习题 2.10 中的 inplace_swap 函数的基础上，你决定写一段代码，实现将一个数组中的元素头尾两端依次对调。你写出下面这个函数：

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

当你对一个包含元素 1、2、3 和 4 的数组使用这个函数时，正如预期的那样，现在数组的元素变成了 4、3、2 和 1。不过，当你对一个包含元素 1、2、3、4 和 5 的数组使用这个函数时，你会很惊奇地看到得到数字的元素为 5、4、0、2 和 1。实际上，你会发现这段代码对所有偶数长度的数组都能正确地工作，但是当数组的长度为奇数时，它就会把中间的元素设置成 0。

A. 对于一个长度为奇数的数组，长度 cnt = 2k + 1，函数 reverse_array 最后一次循环中，变量 first 和 last 的值分别是什么？

B. 为什么这时调用函数 inplace_swap 会将数组元素设置为 0？

C. 对 reverse_array 的代码做哪些简单改动就能消除这个问题？

位级运算的一个常见用法就是实现掩码运算，这里掩码是一个位模式，表示从一个字中选出的位的集合。让我们来看一个例子，掩码 0xFF（最低的 8 位为 1）表示一个字的低位字节。位级运算 x & 0xFF 生成一个由 x 的最低有效字节组成的值，而其他的字节就被置为 0。比如，对于 x = 0x89ABCDEF，其表达式将得到 0x000000EF。表达式 ~0 将生成一个全 1 的掩码，不管机器的字大小是多少。尽管对于一个 32 位机器来说，同样的掩码可以写成 0xFFFFFFFF，但是这样的代码不是可移植的。

练习题 2.12 对于下面的值，写出变量 x 的 C 语言表达式。你的代码应该对任何字长 w ≥ 8 都能工作。我们给出了当 x = 0x87654321 以及 w = 32 时表达式求值的结果，仅供参考。

A. x 的最低有效字节，其他位均置为 0。[0x00000021]。

B. 除了 x 的最低有效字节外，其他的位都取补，最低有效字节保持不变。[0x789ABC21]。

C. x 的最低有效字节设置成全 1，其他字节都保持不变。[0x876543FF]。

练习题 2.13 从 20 世纪 70 年代末到 80 年代末，Digital Equipment 的 VAX 计算机是一种非常流行的机型。它没有布尔运算 AND 和 OR 指令，只有 bis（位设置）和 bic（位清除）这两种指令。两种指令的输入都是一个数据字 x 和一个掩码字 m。它们生成一个结果 z，z 是由根据掩码 m 的位来修改 x 的位得到的。使用 bis 指令，这种修改就是在 m 为 1 的每个位置上，将 z 对应的位设置为 1。使用 bic 指令，这种修改就是在 m 为 1 的每个位置，将 z 对应的位设置为 0。

为了看清楚这些运算与 C 语言位级运算的关系，假设我们有两个函数 bis 和 bic 来实现位设置和位清除操作。只想用这两个函数，而不使用任何其他 C 语言运算，来实现按位 | 和 ^ 运算。填写下列代码中缺失的代码。提示：写出 bis 和 bic 运算的 C 语言表达式。

/* Declarations of functions implementing operations bis and bic */
int bis(int x, int m);
int bic(int x, int m);

/* Compute x|y using only calls to functions bis and bic */
int bool_or(int x, int y) {
    int result = __________;
    return result;
}

/* Compute x^y using only calls to functions bis and bic */
int bool_xor(int x, int y) {
    int result = __________;
    return result;
}