这是获得数字绝对值的最快方法

Question

哪个是实现返回数字绝对值的操作的最快方法？

x=root(x²)

要么

if !isPositive(x):
    x=x*(-1)

实际上这个问题可以翻译为,有多快if(为什么请).

我的大学程序教授总是告诉我要避免使用ifs,因为它们非常慢,但我总是忘记问多慢和为什么.这里有人知道吗？

Answer 1

在不使用if语句的情况下计算2s-补码整数的绝对值有一个很好的技巧.理论上说,如果值为负,则需要切换位并添加一个,否则您希望按原样传递位.XOR 1碰巧切换A和A XOR 0碰巧保持A完好无损.所以你想做这样的事情:

  uint32_t temp = value >> 31;     // make a mask of the sign bit
  value ^= temp;                   // toggle the bits if value is negative
  value += temp & 1;               // add one if value was negative

原则上,您可以在少至三个汇编指令(没有分支)的情况下执行此操作.而且你想认为你用math.h得到的abs()函数可以最佳地完成它.

没有分支==更好的表现.与@ paxdiablo上面的响应相反,这在深层管道中非常重要,在您的代码中,您拥有的分支越多,您的分支预测器就越有可能出错并且必须回滚等等.如果您避免分支在哪里可能的,事情将继续在你的核心全油门:).

Answer 2

条件比普通的算术运算慢,但是比计算平方根时更快,更快.

我的集会日的经验法则:

• 整数或按位运算:1个周期
• 浮点加/子/ mul:4个周期
• 浮点div:~30个周期
• 浮点取幂:约200个循环
• 浮点sqrt:约60个周期,具体取决于实现
• 条件分支:平均 10个周期,如果预测得好则更好,如果误预测会更糟

Answer 3

呃,你的老师实际上告诉过你了吗？大多数人遵循的规则是首先使代码可读,然后在证明实际出现问题之后调整任何性能问题. 99.999%的时间你永远不会看到性能问题,因为你使用了太多的if语句. Knuth说得最好,"过早优化是万恶之源".

Answer 4

计算平方根可能是你可以做的最糟糕的事情之一,因为它真的很慢.通常有一个库函数来执行此操作; 像Math.Abs​​()这样的东西.乘以-1也是不必要的; 只需返回-x.因此,以下是一个很好的解决方案.

(x >= 0) ? x : -x

编译器可能会将其优化为单个指令.由于执行流程较长,现代处理器上的条件可能相当昂贵 - 如果分支被错误预测并且处理器开始从错误的代码路径执行指令,则必须丢弃计算.但是由于提到的编译器优化,在这种情况下你不需要关心.

Answer 5

哪个是获得数字绝对值的最快方法

我认为“正确”的答案实际上并不在这里。获得绝对数的最快方法可能是使用 Intel Intrinsic。请参阅https://software.intel.com/sites/landingpage/IntrinsicsGuide/并查找“vpas”（或其他为您的 CPU 完成工作的内在函数）。我很确定它会在这里击败所有其他解决方案。

如果您不喜欢内在函数（或不能使用它们或...），您可能需要检查编译器是否足够智能来确定对“本机绝对值”（std::abs在 C++ 或Math.Abs(x)C# 中）的调用是否会改变自动进入内在 - 基本上涉及查看反汇编（编译）代码。如果您在 JIT 中，请确保未禁用 JIT 优化。

如果这也没有给你优化的说明，你可以使用这里描述的方法：https : //graphics.stanford.edu/~seander/bithacks.html#IntegerAbs。

Answer 6

为了完整起见,这里有一种方法可以在C++的x86系统上实现IEEE浮点数:

*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1;