2.3.6 乘以常数

以往，在大多数机器上，整数乘法指令相当慢，需要 10 个或者更多的时钟周期，然而其他整数运算（例如加法、减法、位级运算和移位）只需要 1 个时钟周期。即使在我们的参考机器 Intel Core i7 Haswell 上，其整数乘法也需要 3 个时钟周期。因此，编译器使用了一项重要的优化，试着用移位和加法运算的组合来代替乘以常数因子的乘法。首先，我们会考虑乘以 2 的幂的情况，然后再概括成乘以任意常数。

原理：乘以 2 的幂

设 x 为位模式 [x_w-1, x_w-2, ..., x₀] 表示的无符号整数。那么，对于任何 k ≥ 0，我们都认为 [x_w-1, x_w-2, ..., x₀, 0, ..., 0] 给出了 x2^k 的 w + k 位的无符号表示，这里右边增加了 k 个 0。

因此，比如，当 w = 4 时，11 可以被表示为 [1011]。k = 2 时将其左移得到 6 位向量 [101100]，即可编码为无符号数 11 · 4 = 44。

推导：乘以 2 的幂

这个属性可以通过等式（2.1）推导出来：

B2U_w+k([x_w-1, x_w-2, ..., x₀, 0, ..., 0])

= Σ_i=0^w-1x_i2^i+k

= [Σ_i=0^w-1x_i2ⁱ] · 2^k

= x2^k

■

当对固定字长左移 k 位时，其高 k 位被丢弃，得到 [x_w-k-1, x_w-k-2, ..., x₀, 0, ..., 0]，而执行固定字长的乘法也是这种情况。因此，我们可以看出左移一个数值等价于执行一个与 2 的幂相乘的无符号乘法。

原理：与 2 的幂相乘的无符号乘法

C 变量 x 和 k 有无符号数值 x 和 k，且 0 ≤ k < w，则 C 表达式 x << k 产生数值 x *^u_w 2^k。

由于固定大小的补码算术运算的位级操作与其无符号运算等价，我们就可以对补码运算的 2 的幂的乘法与左移之间的关系进行类似的表述：

原理：与 2 的幂相乘的补码乘法

C 变量 x 和 k 有补码值 x 和无符号数值 k，且 0 ≤ k < w，则 C 表达式 x << k 产生数值 x *^t_w 2^k。

注意，无论是无符号运算还是补码运算，乘以 2 的幂都可能会导致溢出。结果表明，即使溢出的时候，我们通过移位得到的结果也是一样的。回到前面的例子，我们将 4 位模式 [1011]（数值为 11）左移两位得到 [101100]（数值为 44）。将这个值截断为 4 位得到 [1100]（数值为 12 = 44 mod 16）。

由于整数乘法比移位和加法的代价要大得多，许多 C 语言编译器试图以移位、加法和减法的组合来消除很多整数乘以常数的情况。例如，假设一个程序包含表达式 x * 14。利用 14 = 2³ + 2² + 2¹，编译器会将乘法重写为 (x<<3)+(x<<2)+(x<<1)，将一个乘法替换为三个移位和两个加法。无论 x 是无符号的还是补码，甚至当乘法会导致溢出时，两个计算都会得到一样的结果。（根据整数运算的属性可以证明这一点。）更好的是，编译器还可以利用属性 14 = 2⁴ - 2¹，将乘法重写为 (x<<4)-(x<<1)，这时只需要两个移位和一个减法。

练习题 2.38 就像我们将在第 3 章中看到的那样，LEA 指令能够执行形如 (a<<k)+b 的计算，这里 k 等于 0、1、2 或 3，而 b 等于 0 或者某个程序值。编译器常常用这条指令来执行常数因子乘法。例如，我们可以用 (a<<1)+a 来计算 3*a。

考虑 b 等于 0 或者等于 a、k 为任意可能的值的情况，用一条 LEA 指令可以计算 a 的哪些倍数？

归纳一下我们的例子，考虑一个任务，对于某个常数 K 的表达式 x*K 生成代码。编译器会将 K 的二进制表示表达为一组 0 和 1 交替的序列：

[(0...0)(1...1)(0...0)...(1...1)]

例如，14 可以写成 [(0...0)(111)(0)]。考虑一组从位位置 n 到位位置 m 的连续的 1（n ≥ m）。（对于 14 来说，我们有 n = 3 和 m = 1。）我们可以用下面两种不同形式中的一种来计算这些位对乘积的影响：

形式 A：(x<<n)+(x<<(n-1))+...+(x<<m)

形式 B：(x<<(n+1))-(x<<m)

把每个这样连续的 1 的结果加起来，不用做任何乘法，我们就能计算出 x*K。当然，选择使用移位、加法和减法的组合，还是使用一条乘法指令，取决于这些指令的相对速度，而这些是与机器高度相关的。大多数编译器只在需要少量移位、加法和减法就足够的时候才使用这种优化。

练习题 2.39 对于位位置 n 为最高有效位的情况，我们要怎样修改形式 B 的表达式？

练习题 2.40 对于下面每个 K 的值，找出只用指定数量的运算表达 x*K 的方法，这里我们认为加法和减法的开销相当。除了我们已经考虑过的简单的形式 A 和 B 原则，你可能会需要使用一些技巧。

K	移位	加法/减法
6	2	1
31	1	1
-6	2	1
55	2	2

练习题 2.41 对于一组从位位置 n 开始到位位置 m 的连续的 1（n ≥ m），我们看到可以产生两种形式的代码，A 和 B。编译器该如何决定使用哪一种呢？