哪种方法是获取一个数的绝对值最快的方式？

Question

如何实现一个返回数字绝对值的操作，哪种方法最快？

x=root(x²)

或者

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

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

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

- Diones

---

这是绝对值，不是模数。 - kquinn

至少在罗马尼亚，我们使用英语中“modulus”/“module”的等效词来表示“绝对值”。我认为这种现象在其他语言中也很普遍。 - Eduard - Gabriel Munteanu

啊，在美式英语中，绝对值是指在数轴上距离0的距离。也就是说，-4的绝对值是4，12的绝对值是12。 - Perchik

尽管维基百科似乎提到在表示“绝对值”时使用“模数”一词：http://en.wikipedia.org/wiki/Absolute_value - Eduard - Gabriel Munteanu

我认为这些英语纯粹主义者无法区分模和取模。"Modulus"是一个有效的英语术语，可用于指代实数或复数的绝对值。 - Violet Giraffe

平方/平方根方法也容易发生溢出。 - user5483294

Answer 1

有一个很棒的技巧可以在不使用if语句的情况下计算2s补码整数的绝对值。理论上来说，如果这个值是负数，你需要切换位并加1，否则你希望按原样传递位。A 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

原则上，您可以仅使用三个汇编指令（无需分支）完成它。而您希望 abs() 函数（通过 math.h 获取）能够以最优方式进行操作。

没有分支 == 更好的性能。与 @paxdiablo 上面的回答相反，在深层流水线中，分支越多，代码中出现分支预测错误和必须回滚的可能性就越大。如果尽可能避免分支，那么您的核心将保持全速运转 :)

- vicatcu

---

顺便提一下，这里假设“value”是一个int32_t类型的变量（即带符号的整型），如果不是，你需要在进行移位操作之前先将其转换为int32_t类型。 - vicatcu

建议使用更简单的 value -= temp，而不是 value += temp & 1，并且没有理由使用无符号类型的 temp。 - Qwertie

正是我在这里寻找的！因此，如果您的情况允许一个错误，您可以屏蔽掉符号位！为什么我没想到呢？哈哈。 - Dmitri

为什么要这么费劲呢？用((value >> 31) | 1) * value不就行了吗？乘法并不昂贵。 - M.kazem Akhgary

如果将1解释为1111...1，则A XOR 1会反转A。右移（>>31）假定用左侧的位进行填充。这被称为算术移位。很好的答案，这个小细节让我困惑了。 - Polymer

Answer 2

条件语句的速度比简单的算术运算要慢，但比计算平方根等愚蠢的操作快得多。

以下是我从汇编时代总结出来的经验法则：

• 整数或位运算：1个周期
• 浮点数加/减/乘：4个周期
• 浮点数除法：约30个周期
• 浮点数幂运算：约200个周期
• 浮点数平方根：约60个周期，具体取决于实现
• 条件分支：平均10个周期，如果预测正确，则更好，如果预测错误，则更糟

- kquinn

---

对于fp add/sub/mul，它们是延迟。如果您没有在延迟上遇到瓶颈，吞吐量仍然至少为每个时钟1次。此外，现代x86整数乘法的延迟为3个周期。请参阅Agner Fog的优化指南，了解流水线CPU（和乱序执行）的吞吐量和延迟之间的区别。 - Peter Cordes

还要注意，任何像样的编译器都会看到这个特定的 if 在做什么，并将其编译为只清除浮点数或双精度数的符号位的位运算（像带有 SSE 的 x86 现代 FPU），或者像旧的 x87 fabs 那样的专用指令，在不支持浮点数上的任意位运算的 x87 FPU 上执行相同的操作。 - Peter Cordes

或者至少你希望如此；实践更加复杂。https://godbolt.org/z/4K5W61。这就是为什么在C语言中应该实际使用`fabs(x)`，它可以尽可能高效地编译，而不必担心编译器对有符号零和NaN进行特殊处理。例如，`if (x<0) x = -x;或x = (x<0) ? -x : x;都需要保留负零，因为它与0.0相等。但无论如何，(-1)*x可以优化为只需使用xorps`来翻转符号位。 - Peter Cordes

Answer 3

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

(x >= 0) ? x : -x

编译器可能会将此代码优化为一条指令。由于现代处理器的长执行流水线可能导致条件语句非常昂贵 - 如果分支预测错误并且处理器开始执行错误的代码路径，则必须放弃计算。但是，由于提到的编译器优化，在这种情况下您不需要担心。

- danbruc

---

为什么这个答案没有更多的赞？！ 这段代码编译为“mov eax, edi; neg eax; cmovl eax, edi; ret”，它不需要任何注释来解释所有位操作。 - Indiana Kernick

Answer 4

为了完整起见，在x86系统上用C++进行IEEE浮点数转换的方法如下：

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

- awdz9nld

---

@Stefnotch 取一个32位浮点变量foo的地址，强制转换为32位无符号整数指针，解引用并应用掩码以保留除了（MSB）符号位之外的所有位。 - awdz9nld

这个答案是错误的。如果你移除 -1 的二进制符号，你得到的不是 1 而是一个非常大的值。查找二进制补码以了解原因。 - Julien__

@Julien__ 我认为你误解了这里正在发生的事情。我们正在操作浮点数的原始位 - 结果位模式不是用作有符号整数，而是用作浮点数。 - awdz9nld

@MartinKällman，哎呀你说得对。我的错。当时我在操作整数，忽略了答案中的“浮点数”部分。 - Julien__

Answer 5

如何最快地获取一个数的绝对值

我认为“正确”的答案实际上不在这里。获取绝对值的最快方法可能是使用Intel Intrinsic。请参见https://software.intel.com/sites/landingpage/IntrinsicsGuide/并查找“vpabs”（或另一个适用于您的CPU的内部函数）。我非常确定它会击败这里所有其他解决方案。

如果您不喜欢内部函数（或无法使用它们或...），您可能需要检查编译器是否足够聪明，可以自动将对“本机绝对值”的调用（C ++中的std :: abs 或C＃中的 Math.Abs（x））转换为内部函数 - 基本上涉及查看反汇编（已编译）代码。如果您处于JIT中，请确保未禁用JIT优化。

如果上述方法仍未提供优化的指令，您可以使用此处描述的方法：https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs。

- atlaste

---

如果您有一个值数组或者可以将数据仅保留在向量寄存器中，那么pabsd非常好用。但是与从整数寄存器复制到XMM再返回相比，neg/cmov更加高效。您几乎总是应该使用std::abs，并让编译器自动矢量化（如果需要的话），否则请高效地内联它。 - Peter Cordes

Answer 6

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

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

混淆的主要原因是if无疑会以非顺序方式改变指令指针。这可能会拖慢预取指令到管道中的处理器，因为当地址意外更改时，它们必须重新填充管道。

然而，与执行平方根操作相比，进行简单的检查和否定的成本微不足道。

- Pax

Answer 7

取模运算用于找到余数，你指的是绝对值。我修改了问题，因为应该是如果!pos（x）那么x = x * -1。（缺少不是）。不要担心if语句的效率，而是专注于代码的可读性。如果您确定存在效率问题，则应专注于对代码进行分析以查找真正的瓶颈。如果您想在编码时注意效率，那么只需担心算法的大O复杂度即可。if语句非常高效，它评估任何表达式，然后仅基于该条件更改程序计数器。程序计数器存储要执行的下一条指令的地址。将一个值乘以-1并检查其是否大于0都可以缩减为单个汇编指令。首先找到一个数字的平方根再平方肯定比带有否定的if更多操作。

- Brian R. Bondy

---

我猜教授在考虑 If 语句堵塞流水线的问题。但我很确定现代处理器不会再出现这种情况了。 - Ray

那个教授是个白痴 - 对 root() 函数的调用也会搞乱流水线。 - paxdiablo

Answer 8

你在使用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

(明目张胆地盗窃)

- Mark Maxham

---

使用test same,same而不是or same,same可以提高效率（在CMP reg,0 vs OR reg,reg中测试寄存器是否为零？）。除非你正在编写真正古老的CPU程序，否则请使用cmov代替条件分支。 - Peter Cordes

Answer 9

计算平方根所需的时间远大于条件判断的时间。如果你曾被教导要避免使用条件语句，因为它们速度较慢，那么你就收到了错误的信息。 与像加减整数或位移这样的简单操作相比，它们确实要慢得多。这就是为什么展开循环只有在做这种简单操作时才有好处的原因。但是从整体上看，条件语句是好的和快速的，而不是坏的和慢的。为了避免条件语句而执行复杂的操作，如调用函数或计算平方根，这是不明智的。

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

- thomasrutter

---

“另外，为什么不用(x = 0 - x)代替(x = x * -1)呢？也许编译器会将它们优化成相同的代码，但第二种方式不是更简单吗？” 当然，我从来没有这样想过... - Diones

Answer 10

你可以尝试使用一个AND运算符作为掩码。

以下是一个示例伪代码。

i8 num = 10001101 = -13
u8 mask = 01111111 = 127;
i8 res = num & mask = 00001101 = 13

.

我相信这是计算机上计算绝对值的最快方式。如果我错了，请纠正我。

- Zain Ahmed

---

这似乎是基于“符号-幅值”整数的假设。而比较常见的是“二进制补码”：-13₁₀ = 11110011₂。 - greybeard

嗯，这个应该也适用于浮点数，因为浮点数和双精度数的最高有效位都是有符号位。实际上，任何带有符号位作为最高有效位的有符号数都可以用单个AND操作来计算绝对值。 - Zain Ahmed