如何使用右移来避免运算符除法

Question

我有一个 cpp 项目可以运行但性能不佳。

int currentPos = getPos();
int length = getLength();
if (1.0 * currentPos / length < 0.5)
{
    // do something
}
else
{
    // do something
}

问题是：1.0 * currentPos / length 太花时间了。

Google告诉我除法总是很花时间，我们可以通过右移来避免。

例如a=a/4可以替换为b=b>>2。

我能理解这个例子，但我不知道如何使用右移来优化我上面的代码。

如果不可能，请问还有其他方法可以避免分裂吗？

编辑
1) if中的条件并不总是0.5，它可以是(0, 1).

之间的任意有理数 2) 上面的代码每秒执行 10 * 56 * 181 * 56 * 181 次。

Answer 1

除法是微不足道的。

if (length > 2 * currentPos)

移位而不是除法是一种微优化，任何体面的编译器都会自动为您执行，而不会弄乱您的代码并使其不可读。

Answer 2

有一种方法可以非常快速地除以一个常量，但只有当您在编译时知道该值时才有效。一般算法在书Hacker's Delight中有描述。互联网上也有很多例子。不过，您的情况有所不同。您从函数

中检索长度

getLength();

但是，如果长度不是常数，但在多次计算中仍然是相同的数字，您可以通过计算倒数和 相乘来提高性能 一起吧。

这与乘法本身是通过二进制移位和加法完成的事实有关 - 远远少于除法。实现起来可能有点棘手，因为我假设代码片段来自函数内部，因此您可能希望有一个 global 变量（或至少在函数外部，即 class 成员）。

Answer 3

让我们说实话。在甚至遥远的现代 CPU 上，浮点数的除法将被流水线处理掉，并且与大多数其他 FPU 甚至整数运算所花费的时间大致相同。

相反，您应该在代码上使用分析器来准确查看瓶颈实际发生的位置。在编写代码时，除非它处于 1,000,000,000,000 时间类型 for/loop，否则根本不重要。

如果您的代码处于这样的循环中，请告诉我们，因为除了有点无用的简单除法之外，还有一些方法可以减少强度、预先计算等，在这些情况下可以提供帮助十年。

关于这确实处于 10 亿次循环中这一事实的更新。

现在，让我们从您的两个函数开始 GetPos() 和 GetLength() 如果您可以组织数据的方式使这些值在循环的某些部分保持不变，那么您完全可以消除一些内存访问。然后，您也可以在循环外乘以 2。

接下来，如果您可以组织数据，使其在循环运行之前按长度或位置排序，那么您可以对数据进行二分搜索并将比较减少到大约最多 20 个左右而不是数十亿个（ O(log n) 与 O(n) 的幂）然后你的代码运行得非常快。

如果不可能，但每个循环的数据是恒定的并且 "do something" 不会改变条件，那么这将变得令人尴尬地并行并且可能能够跨越许多 CPUs - 这并不像听起来那么容易，但要小心。

这只是一个开始，但我想让您看到更多信息可以为您提供更好的解决方案。

Answer 4

注意：要将整数除以 2，您只需移动 1 ... (4 >> 1) == 2。（和 4 >> 2 == 1）

我最近了解到（艰难地）完全优化 (-O3) 并不总是如您所愿。 (g++ v5.2.1, ubuntu 64)

在 5x10^9 循环中，我手动更改了代码：

if (ZERO == (n & B00) // n-even
{
    ...even actions
}
else // n-odd
{
    ...odd actions
}

至：

if (n & B00) // n-odd
{
    ...odd actions
}
else // n-even
{
    ...even actions
}

并在该循环中消除了 8 秒。（从 58 增加到 50）

在我尝试这个测试之前，我认为编译器 a) 可以（并且会）重新安排代码，并且 b) 显式测试零会更快。我错了

我提到这一点，即使您的问题看起来不同，因为这是一个非常简单的测试来尝试...几秒钟的编辑，然后是编译和运行。

How to use right shift to avoid operator division