48

实现返回数字绝对值的运算的最快方法是什么？

x=root(x²)

或者

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

实际上这个问题可以翻译为，多快if（以及为什么）。

我的大学编程教授总是告诉我要避免if使用 s，因为它们非常慢，但我总是忘记问有多慢以及为什么。这里有人知道吗？

4

15 回答 15

88

在不使用 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 的回复相反，这在深层管道中确实很重要，因为代码中的分支越多，分支预测器出错并不得不回滚的可能性就越大，等等。如果你避免在哪里分支有可能，事情会在你的核心中全速前进:)。

于 2010-01-15T19:59:26.887 回答
75

条件比普通的算术运算要慢，但比计算平方根这样愚蠢的运算要快得多。

我组装日的经验法则：

  • 整数或按位运算：1 个周期
  • 浮点加/减/乘：4 个周期
  • 浮点 div：~30 个周期
  • 浮点取幂：~200 个周期
  • 浮点 sqrt：约 60 个周期，具体取决于实现
  • 条件分支：avg. 10 个周期，如果预测良好则更好，如果预测错误则更糟
于 2009-03-20T03:18:31.187 回答
20

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

(x >= 0) ? x : -x

编译器可能会将其优化为单个指令。由于执行管道很长，现代处理器的条件可能非常昂贵——如果分支预测错误并且处理器开始从错误的代码路径执行指令，则必须丢弃计算。但是由于提到的编译器优化，在这种情况下你不需要关心。

于 2009-03-20T03:32:06.350 回答
7

为了完整起见，这里有一种在 C++ 中为 x86 系统上的 IEEE 浮点数执行此操作的方法：

*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1;
于 2012-07-26T16:08:51.753 回答
6

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

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

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

如果这也没有为您提供优化的说明，您可以使用此处描述的方法：https ://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs 。

于 2015-07-13T20:13:14.973 回答
4

与平方根相比，该if变体几乎肯定会快得令人眼花缭乱，因为它通常会转换为机器代码级别的条件跳转指令（在表达式的评估之后，这可能很复杂，但在这种情况下并非如此，因为它很简单检查是否小于 0）。

取数字的平方根可能要慢得多（例如，牛顿的方法将在机器代码级别使用许多语句）。 if

混淆的可能来源是if总是导致以非顺序方式更改指令指针的事实。这可能会减慢将指令预取到流水线中的处理器，因为当地址意外更改时它们必须重新填充流水线。

但是，与执行平方根运算而不是简单的检查和取反相比，这样做的成本将是微不足道的。

于 2009-03-20T03:19:20.857 回答
3

模运算用于求余数，即绝对值。我修改了这个问题，因为它应该是 if !pos(x) then x = x*-1。（没有丢失）

我不会担心 if 语句的效率。而是专注于代码的可读性。如果您发现存在效率问题，则专注于分析您的代码以找到真正的瓶颈。

如果您想在编写代码时注意效率，您应该只担心算法的大 O 复杂性。

如果语句非常有效，它会评估任何表达式，然后根据该条件简单地更改程序计数器。程序计数器存储要执行的下一条指令的地址。

乘以 -1 和检查值是否大于 0 都可以简化为一条汇编指令。

找到一个数字的根并首先对该数字进行平方肯定比带有否定的 if 更多的操作。

于 2009-03-20T03:17:20.270 回答
1

做一个平方根的时间比做一个条件的时间要长得多。如果你被教导要避免条件句，因为它们很慢，那么你就被误导了。它们比诸如加减整数或位移之类的琐碎操作要慢得多——这就是为什么展开循环只有在执行此类琐碎操作时才有用。但在事物的宏伟计划中，条件句是好的和快的，不是坏的和慢的。做一些复杂的事情，比如调用函数或计算平方根来避免条件语句是疯狂的。

另外，为什么不使用（x = x * -1）而不是（x = 0 - x）？也许编译器会对它们进行同样的优化，但是第二个不是更简单吗？

于 2009-03-20T03:35:00.430 回答
1

你用的是8086汇编吗？;-)

                ; abs value of AX
   cwd          ; replicate the high bit into DX
   xor  ax, dx  ; take 1's complement if negative; no change if positive
   sub  ax, dx  ; AX is 2's complement if it was negative The standard
                : absolute value method works on any register but is much
                ; slower:

   or   bx, bx  ; see if number is negative
   jge  notneg  ; if it is negative...
   neg  bx      ; ...make it positive
notneg:         ; jump to here if positive

（公然盗用）

于 2009-03-20T04:23:33.260 回答
0

如果您只是比较两个数字的绝对值（例如，在比较之后您不需要任何一个的绝对值），那么只需将两个值平方以使两者都为正（删除每个值的符号），较大的平方将是大于较小的正方形。

于 2014-10-21T15:25:32.457 回答
0

更快的速度很大程度上取决于您所针对的编译器和 CPU。在大多数 CPU 和所有编译器上 x = (x>=0)？x:-x; 是获得绝对值的最快方法，但实际上，通常标准函数已经提供了这种解决方案（例如 fabs()）。它被编译成比较后跟条件赋值指令（CMOV），而不是条件跳转。不过，有些平台缺少该指令。虽然，英特尔（但不是微软或 GCC）编译器会自动将 if() 转换为条件赋值，甚至会尝试优化循环（如果可能的话）。

如果 CPU 使用统计预测，则分支代码通常比条件赋值慢。如果操作重复多次并且条件结果不断变化，则 if() 平均可能会变慢。像 Intel 这样的 CPU 会开始计算两个分支，并会丢弃无效的分支，以防出现较大的 if() 主体或可能很关键的大量周期。

现代英特尔 CPU 上的 sqr() 和 sqrt() 是单个内置指令，并不慢，但它们不精确，加载寄存器也需要时间。

相关问题：为什么 CPU 分支指令很慢？

最有可能的是，教授希望学生对这个问题进行研究，这是一个半挑衅性的问题\任务，只有当学生学会独立思考并寻找额外的资源时才会有好处。

于 2015-03-18T16:29:40.467 回答
0

我正在用 C 语言为 8088/8086 进行一些复古图形编程，并且调用abs()很耗时，所以我将其替换为：

/* assuming 'i' is int; this WILL NOT WORK on floating point */
if (i < 0) {
    i = ~i + 1;
}

这更快的原因是因为它本质上是CALL在汇编中将 a换成JNE. 调用一个方法会更改几个寄存器，再推送几个，将参数推送到堆栈上，并且可以刷新预取队列。此外，这些操作需要在函数结束时反转，所有这些对 CPU 来说都是非常昂贵的。

于 2016-11-21T23:08:13.740 回答
0

为了完整起见，如果您正在处理浮点数，您总是可以执行类似的操作n * sign(n)，sign如果数字为正，则返回 +1，如果为负，则返回 -1。在 C 中，这类似于copysign(1.0, n)or (n > 0) - (n < 0)。

现在大多数机器都使用 IEEE 754 作为浮点格式，因此您可以直接清除符号位：

float fabs(float x) {
    char *c = &x;
    c[0] &= 7;
    return *(float *)c;
}

鉴于该abs功能可能会执行此操作，因此最好的选择是在可用时使用它。如果你幸运的话，这个函数将是几个指令，并且会被内联。

于 2020-07-30T23:43:16.957 回答
0

我想知道，这个解决方案是否有问题。有

  • 没有分支
  • 不依赖位宽的移位
  • 没有一点玩弄
  • 没有架构依赖
  • 没有编译器依赖
  • 可选：没有未定义的行为INT_MIN

可能指令太多了？

我的解决方案

xabs = (x < 0)*(-x) + (x >=0)*x
  • 2个整数比较
  • 2 次乘法

旧解决方案 

xtest = (x < 0)*x;           // xtest = x if is negative, otherwise zero
xabs = (x - xtest) - xtest;  // Order of instructions taken into account

未定义的否定行为INT_MIN

INT_MIN如果您的值在之前某处的算法中不受限制，则可以添加对未定义行为（对 的否定）的检查。但这使它变得更复杂一些。也许，有人发现了一个更简单的逻辑。

xabs =   (x < -INT_MAX)*INT_MAX            //  x < -INT_MAX < 0  --> xabs = INT_MAX
       + ((x >= -INT_MAX)&&(x < 0))*(-x)   // -INT_MAX =< x < 0  --> xabs = -x
       + (x >= 0)*x                        // 0 <= x             --> xabs = +x
  • 5 个整数比较
  • 3个整数乘法

不幸的是，我从未做过速度比较。所以我不知道它是否真的比

if ( x < 0 )
{
  if ( x >= -INT_MAX )
  {
    x = -x;
  }
  else
  {
    x = INT_MAX;
  }
}
于 2021-04-22T11:36:20.787 回答
-1

对于负数列表：

如果您在内存中存储了零，只需使用0 - x，其中x是负数。

或者，如果您没有零存储在内存中：

x-x-x, 哪里x是负数。

或者，为了清楚起见，用括号：

(x) - (x) - (x) => (-n) - (-n) - (-n)，其中x = -n

即从自身减去负数得到零，然后从零减去它。

于 2019-09-08T16:37:51.877 回答