2.1.9 C 语言中的移位运算

C 语言还提供了一组移位运算，向左或者向右移动位模式。对于一个位表示为 [x_w-1, x_w-2, ..., x₀] 的操作数 x，C 表达式 x << k 会生成一个值，其位表示为 [x_w-k-1, x_w-k-2, ..., x₀, 0, ..., 0]。也就是说，x 向左移动 k 位，丢弃最高的 k 位，并在右端补 k 个 0。移位量应该是一个 0 ~ w - 1 之间的值。移位运算是从左至右可结合的，所以 x << j << k 等价于 (x << j) << k。

有一个相应的右移运算 x >> k，但是它的行为有点微妙。一般而言，机器支持两种形式的右移：逻辑右移和算术右移。逻辑右移在左端补 k 个 0，得到的结果是 [0, ..., 0, x_w-1, x_w-2, ..., x_k]。算术右移是在左端补 k 个最高有效位的值，得到的结果是 [x_w-1, ..., x_w-1, x_w-1, x_w-2, ..., x_k]。这种做法看上去可能有点奇特，但是我们会发现它对有符号整数数据的运算非常有用。

让我们来看一个例子，下面的表给出了对一个 8 位参数 x 的两个不同的值做不同的移位操作得到的结果：

操作	值	值
参数 x	[01100011]	[10010101]
x << 4	[00110000]	[01010000]
x >> 4（逻辑右移）	[00000110]	[00001001]
x >> 4（算术右移）	[00000110]	[11111001]

斜体的数字表示的是最右端（左移）或最左端（右移）填充的值。可以看到除了一个条目之外，其他的都包含填充 0。唯一的例外是算术右移 [10010101] 的情况。因为操作数的最高位是 1，填充的值就是 1。

C 语言标准并没有明确定义对于有符号数应该使用哪种类型的右移--算术右移或者逻辑右移都可以。不幸地，这就意味着任何假设一种或者另一种右移形式的代码都可能会遇到可移植性问题。然而，实际上，几乎所有的编译器/机器组合都对有符号数使用算术右移，且许多程序员也都假设机器会使用这种右移。另一方面，对于无符号数，右移必须是逻辑的。

与 C 相比，Java 对于如何进行右移有明确的定义。表达式 x >> k 会将 x 算术右移 k 个位置，而 x >>> k 会对 x 做逻辑右移。

旁注：移动 k 位，这里 k 很大

对于一个由 w 位组成的数据类型，如果要移动 k ≥ w 位会得到什么结果呢？例如，计算下面的表达式会得到什么结果，假设数据类型 int 为 w = 32：

int lval = 0xFEDCBA98 << 32;
int aval = 0xFEDCBA98 >> 36;
unsigned uval = 0xFEDCBA98u >> 40;

C 语言标准很小心地规避了说明在这种情况下该如何做。在许多机器上，当移动一个 w 位的值时，移位指令只考虑位移量的低 log₂ w 位，因此实际上位移量就是通过计算 k mod w 得到的。例如，当 w = 32 时，上面三个移位运算分别是移动 0、4 和 8 位，得到结果：

lval  0xFEDCBA98
aval  0xFFEDCBA9
uval  0x00FEDCBA

不过这种行为对于 C 程序来说是没有保证的，所以应该保持位移量小于待移位值的位数。另一方面，Java 特别要求位移数量应该按照我们前面所讲的求模的方法来计算。

旁注：与移位运算有关的操作符优先级问题

常常有人会写这样的表达式 1 << 2+3 << 4，本意是 (1 << 2) + (3 << 4)。但是在 C 语言中，前面的表达式等价于 1 << (2+3) << 4，这是由于加法（和减法）的优先级比移位运算要高。然后，按照从左至右结合性规则，括号应该是这样打的 (1 << (2+3)) << 4，得到的结果是 512，而不是期望的 52。

在 C 表达式中搞错优先级是一种常见的程序错误原因，而且常常很难检查出来。所以当你拿不准的时候，请加上括号！

练习题 2.16 填写下表，展示不同移位运算对单字节数的影响。思考移位运算的最好方式是使用二进制表示。将最初的值转换为二进制，执行移位运算，然后再转换回十六进制。每个答案都应该是 8 个二进制数字或者 2 个十六进制数字。

x 十六进制	x 二进制	x << 3 二进制	x << 3 十六进制	x >> 2（逻辑的）二进制	x >> 2（逻辑的）十六进制	x >> 2（算术的）二进制	x >> 2（算术的）十六进制
0xC3
0x75
0x87
0x66