2.3.7 除以 2 的幂
2.3.7 除以 2 的幂
在大多数机器上，整数除法要比整数乘法更慢 - 需要 30 个或者更多的时钟周期。除以 2 的幂也可以用移位运算来实现，只不过我们用的是右移，而不是左移。无符号和补码数分别使用逻辑移位和算术移位来达到目的。
整数除法总是舍入到零。为了准确进行定义，我们要引入一些符号。对于任何实数 a，定义 ⌊a⌋ 为唯一的整数 a'，使得 a' ≤ a < a' + 1。例如，⌊3.14⌋ = 3，⌊-3.14⌋ = -4，而 ⌊3⌋ = 3。同样，定义 ⌈a⌉ 为唯一的整数 a'，使得 a' - 1 < a ≤ a'。例如，⌈3.14⌉ = 4，⌈-3.14⌉ = -3，而 ⌈3⌉ = 3。对于 x ≥ 0 和 y > 0，结果会是 ⌊x/y⌋，而对于 x < 0 和 y > 0，结果会是 ⌈x/y⌉。也就是说，它将向下舍入一个正值，而向上舍入一个负值。
对无符号运算使用移位是非常简单的，部分原因是由于无符号数的右移一定是逻辑右移。
原理：除以 2 的幂的无符号除法
C 变量 x 和 k 有无符号数值 x 和 k，且 0 ≤ k < w，则 C 表达式 x >> k 产生数值 ⌊x/2k⌋。
例如，图 2-28 给出了在 12 340 的 16 位表示上执行逻辑右移的结果，以及对它执行除以 1、2、16 和 256 的结果。从左端移入的 0 以斜体表示。我们还给出了用真正的运算做除法得到的结果。这些示例说明，移位总是舍入到零的结果，这一点与整数除法的规则一样。
| k | >> k（二进制） | 十进制 | 12 340/2k |
|---|---|---|---|
| 0 | 0011000000110100 | 12 340 | 12 340.0 |
| 1 | 0001100000011010 | 6170 | 6170.0 |
| 4 | 0000001100000011 | 771 | 771.25 |
| 8 | 0000000000110000 | 48 | 48.203125 |
图 2-28 无符号数除以 2 的幂（这个例子说明了执行一个逻辑右移 k 位与除以 2k 再舍入到零有一样的效果）
推导：除以 2 的幂的无符号除法
设 x 为位模式 [xw-1, xw-2, ..., x0] 表示的无符号整数，而 k 的取值范围为 0 ≤ k < w。设 x' 为 w - k 位位表示 [xw-1, xw-2, ..., xk] 的无符号数，而 x'' 为 k 位位表示 [xk-1, ..., x0] 的无符号数。由此，我们可以看到 x = 2kx' + x''，而 0 ≤ x'' < 2k。因此，可得 ⌊x/2k⌋ = x'。
对位向量 [xw-1, xw-2, ..., x0] 逻辑右移 k 位会得到位向量 [0, ..., 0, xw-1, xw-2, ..., xk]，这个位向量有数值 x'，我们看到，该值可以通过计算 x >> k 得到。■
对于除以 2 的幂的补码运算来说，情况要稍微复杂一些。首先，为了保证负数仍然为负，移位要执行的是算术右移。现在让我们来看看这种右移会产生什么结果。
原理：除以 2 的幂的补码除法，向下舍入
C 变量 x 和 k 分别有补码值 x 和无符号数值 k，且 0 ≤ k < w，则当执行算术移位时，C 表达式 x >> k 产生数值 ⌊x/2k⌋。
对于 x ≥ 0，变量 x 的最高有效位为 0，所以效果与逻辑右移是一样的。因此，对于非负数来说，算术右移 k 位与除以 2k 是一样的。作为一个负数的例子，图 2-29 给出了对 -12 340 的 16 位表示进行算术右移不同位数的结果。对于不需要舍入的情况（k = 1），结果是 x/2k。但是当需要进行舍入时，移位导致结果向下舍入。例如，右移 4 位将会把 -771.25 向下舍入为 -772。我们需要调整策略来处理负数 x 的除法。
| k | >> k（二进制） | 十进制 | -12 340/2k |
|---|---|---|---|
| 0 | 1100111111001100 | -12 340 | -12 340.0 |
| 1 | 1110011111100110 | -6170 | -6170.0 |
| 4 | 1111110011111100 | -772 | -771.25 |
| 8 | 1111111111001111 | -49 | -48.203125 |
图 2-29 进行算术右移（这个例子说明了算术右移类似于除以 2 的幂，除了是向下舍入，而不是向零舍入）
推导：除以 2 的幂的补码除法，向下舍入
设 x 为位模式 [xw-1, xw-2, ..., x0] 表示的补码整数，而 k 的取值范围为 0 ≤ k < w。设 x' 为 w - k 位 [xw-1, xw-2, ..., xk] 表示的补码数，而 x'' 为低 k 位 [xk-1, ..., x0] 表示的无符号数。通过与对无符号情况类似的分析，我们有 x = 2kx' + x''，而 0 ≤ x'' < 2k，得到 x' = ⌊x/2k⌋。进一步，可以观察到，算术右移位向量 [xw-1, xw-2, ..., x0] k 位，得到位向量 [xw-1, ..., xw-1, xw-1, xw-2, ..., xk]，它刚好就是将 [xw-1, xw-2, ..., xk] 从 w - k 位符号扩展到 w 位。因此，这个移位后的位向量就是 ⌊x/2k⌋ 的补码表示。■
我们可以通过在移位之前“偏置（biasing）”这个值，来修正这种不合适的舍入。
原理：除以 2 的幂的补码除法，向上舍入
C 变量 x 和 k 分别有补码值 x 和无符号数值 k，且 0 ≤ k < w，则当执行算术移位时，C 表达式 (x + (1<<k) - 1) >> k 产生数值 ⌈x/2k⌉。
图 2-30 说明在执行算术右移之前加上一个适当的偏置量是如何导致结果正确舍入的。在第 3 列，我们给出了 -12 340 加上偏量值之后的结果，低 k 位（那些会向右移出的位）以斜体表示。我们可以看到，低 k 位左边的位可能会加 1，也可能不会加 1。对于不需要舍入的情况（k = 1），加上偏量只影响那些被移掉的位。对于需要舍入的情况，加上偏量导致较高的位加 1，所以结果会向零舍入。
| k | 偏量 | -12 340 + 偏量 | >> k（二进制） | 十进制 | -12 340/2k |
|---|---|---|---|---|---|
| 0 | 0 | 1100111111001100 | 1100111111001100 | -12 340 | -12 340.0 |
| 1 | 1 | 1100111111001101 | 1110011111100110 | -6170 | -6170.0 |
| 4 | 15 | 1100111111011011 | 1111110011111101 | -771 | -771.25 |
| 8 | 255 | 1101000011001011 | 1111111111010000 | -48 | -48.203125 |
图 2-30 补码除以 2 的幂（右移之前加上一个偏量，结果就向零舍入了）
偏置技术利用如下属性：对于整数 x 和 y（y > 0），⌈x/y⌉ = ⌊(x + y - 1)/y⌋。例如，当 x = -30 和 y = 4，我们有 x + y - 1 = -27，而 ⌈-30/4⌉ = -7 = ⌊-27/4⌋。当 x = -32 和 y = 4 时，我们有 x + y - 1 = -29，而 ⌈-32/4⌉ = -8 = ⌊-29/4⌋。
推导：除以 2 的幂的补码除法，向上舍入
查看 ⌈x/y⌉ = ⌊(x + y - 1)/y⌋，假设 x = qy + r，其中 0 ≤ r < y，得到 (x + y - 1)/y = q + (r + y - 1)/y，因此 ⌊(x + y - 1)/y⌋ = q + ⌊(r + y - 1)/y⌋。当 r = 0 时，后面一项等于 0，而当 r > 0 时，等于 1。也就是说，通过给 x 增加一个偏量 y - 1，然后再将除法向下舍入，当 y 整除 x 时，我们得到 q，否则，就得到 q + 1。
回到 y = 2k 的情况，C 表达式 x + (1<<k) - 1 得到数值 x + 2k - 1。将这个值算术右移 k 位即产生 ⌈x/2k⌉。■
这个分析表明对于使用算术右移的补码机器，C 表达式
(x < 0 ? x + (1<<k) - 1 : x) >> k将会计算数值 x/2k。
练习题 2.42 写一个函数 div16，对于整数参数 x 返回 x/16 的值。你的函数不能使用除法、模运算、乘法、任何条件语句（if 或者 ?:）、任何比较运算符（例如 <、> 或 ==）或任何循环。你可以假设数据类型 int 是 32 位长，使用补码表示，而右移是算术右移。
现在我们看到，除以 2 的幂可以通过逻辑或者算术右移来实现。这也正是为什么大多数机器上提供这两种类型的右移。不幸的是，这种方法不能推广到除以任意常数。同乘法不同，我们不能用除以 2 的幂的除法来表示除以任意常数 K 的除法。
练习题 2.43 在下面的代码中，我们省略了常数 M 和 N 的定义：
#define M /* Mystery number 1 */
#define N /* Mystery number 2 */
int arith(int x, int y) {
int result = 0;
result = x*M + y/N; /* M and N are mystery numbers. */
return result;
}我们以某个 M 和 N 的值编译这段代码。编译器用我们讨论过的方法优化乘法和除法。下面是将产生出的机器代码翻译回 C 语言的结果：
/* Translation of assembly code for arith */
int optarith(int x, int y) {
int t = x;
x <<= 5;
x -= t;
if (y < 0) y += 7;
y >>= 3; /* Arithmetic shift */
return x+y;
}M 和 N 的值为多少？