PHP 中的位移和乘法运算有什么不同？

Question

我有以下代码：

<?php
$start = 1;

$timestart = microtime(1);
for ($i = 0; $i < 1000000; $i++) {
    $result1 = $start * 4;
}
echo "\n";
echo microtime(1) - $timestart;
echo "\n";

$timestart = microtime(1);
for ($i = 0; $i < 1000000; $i++) {
    $result2 = $start << 2;
}
echo "\n";
echo microtime(1) - $timestart;
echo "\n";

这将输出：

0.14027094841003

0.12061500549316

我在网上找到了一道谷歌面试题（我想作为开发人员申请，但我意识到我无法通过），其中的一个问题是如何最快地乘一个数字。我的第一个想法是使用*符号，所以我进行了测试。

我的问题是，为什么移位比乘法快？

- aki

---

因为乘法运算需要进行乘法计算，这比位移操作需要更多的时间，因为它是一种更加复杂的运算。 - Dan

@Dan - 这个问题可能更多地涉及到为什么在PHP中位移可能与整数/浮点乘法等价。 - Jared Farrish

参见http://en.wikipedia.org/wiki/Multiplication_algorithm#Electronic_usage，该方法用于计算两个n位数的乘积需要约n2次操作。更正式地说：使用数字位数的自然度量标准，使用长乘法计算两个n位数的时间复杂度为Θ(n2)。位移是一条指令。 - drew010

顺便提一下，进行乘法运算的方法比人们想象的要多得多——不同的方法在不同的情况下都有出色的表现。 - sarnold

@drew010; 可以使用线性时间算法——假设您有足够的RAM来存储一些表格。 - sarnold

为什么我的评论被删除了？我不明白发生了什么，想知道原因。 - Drewdin

Answer 1

因为比特位移是计算机硬件中一项常见操作，对于 CPU 来说是非常简单的。但乘法运算更加困难，因为它不能仅仅使用简单的比特位移来完成，需要进行实际的计算。将一个小整数乘以 4 恰好等同于左移 2 位，这个操作可以被优化为比特位移，但即使编译器/运行时/CPU 将此操作优化为比特位移，某些代码也需要首先“识别”它可以通过这种方式进行优化，这比简单的比特位移本身还要复杂。

无论如何，这两个运算做的事情完全不同，即使某些操作的输出结果相同，也会需要更多的工作量。

- deceze

Answer 2

由于位移操作可以直接在硬件中实现，而硬件很少直接实现乘法操作。通过几个简单的逻辑门可以实现乘以2的幂次方，而乘以任意乘数至少需要多次乘以2的幂次方加上一个自加操作叠加在一起(5=2*2+1)。 我不知道PHP语言是否特别使用可用的低级调用来实现位移操作，但如果它没有这样做，我会感到惊讶。

来源: 多年经验+计算机科学教育

- taz

---

你可能需要明确表明你所说的是硬件效率与ISA之间的区别。x86和ARM都支持在硬件中进行乘法指令。这几乎不能算作“罕见”。我认为你需要定义一下你所说的“直接”是什么意思。 - Will Bickford

我不知道x86和ARM支持硬件乘法指令。所谓“直接在硬件中”，是指在没有任何汇编代码协助的情况下，通过硬件构造逻辑门来实现。例如，只需使用硬件即可实现加法和递增。我曾经学过，纯硬件乘法可能需要比加法多数千个门，而且很少在除了超级计算机之外的任何地方实现。汇编程序可以通过重复加法或其他优化（如重复位移和自加）来模拟硬件乘法。 - taz

@taz：当芯片中有十亿个晶体管时，几千个用于乘法器并不多，而与移位加法相比的性能增益足以证明其必要性。很难找到没有内置乘除法的32或64位CPU。 - Ira Baxter

@IraBaxter 谢谢您提供的信息。我怀疑我的导师可能有点跟不上时代了。 - taz

Answer 3

在英特尔Sandy Bridge CPU上，似乎立即移位的成本约为1个时钟周期，而乘法需要大约3-4个周期。 显然，整个程序性能受到的影响不仅仅是原始乘法，但这足以产生差异。 现在大多数编译器通过将常量2^n优化为移位来优化乘法（编译器作者喜欢优化您的代码 :))，但也许PHP解释器不会这么做。

- ChrisWue

---

这是一个很好的答案。现在我很好奇PHP解释器是否将2^n乘法优化为移位！ - aeu