logo标签列表

乘法和减法哪个更快？

cperformanceoptimization
7

我目前正在进行一项大学项目，它的评分与我的解决方案的速度和效率密切相关。我对代码所做的微小更改具有巨大影响，因为我所编写的特定函数会被调用数十万次。

我已经编写了项目的主要功能，目前正在努力优化所有可能的部分。我质疑的代码部分如下：

array[i] *= -1;

我正在考虑进行优化，以便：

array[i] = 0 - array[i];

更改这段代码是否会实际影响速度？减法运算是否比乘法运算更快？或者这种问题已经成为过去式了吗？

7
试试看。这很大程度上取决于你的架构。 - Graham Borland
翻转符号位 :) 这是最快的方法（但我同意，这完全取决于体系结构） - ppeterka
5
大多数情况下，进行这种预优化是没有必要的，任何半好的编译器都会为您优化代码。 - AndersK
@ppeterka 这仅适用于一种补码系统，这很不可能是 OP 所拥有的。 - unwind
4
顺便问一句，我不禁想知道：为什么你不直接写 array[i] = -array[i] 呢？这样更容易理解。 - Nikos C.
6个回答
20
忽略这个事实，你应该使用这个替代方案：
array[i] = -array[i];

在我看来，使用明确的意图会更清晰，让我们来看看编译器（GCC 4.7.2 on x86-64）如何处理这个程序：

#include <stdio.h>
#include <time.h>

int main(void)
{
    time_t t = time(NULL);
    t *= -1;
    return 0;
}

使用命令：gcc -S mult.c -o 1.s

对于这个命令：

#include <stdio.h>
#include <time.h>

int main(void)
{
    time_t t = time(NULL);
    t = 0 - t;
    return 0;
}

gcc -S sub.c -o 2.s

现在比较这两个汇编输出：

diff 1.s 2.s

没有打印任何内容。编译器为这两个版本生成了完全相同的代码。因此答案是：使用哪个都无所谓，编译器会选择最快的方法。这是一个非常容易实现的优化（如果你可以称之为优化），因此我们可以假设几乎每个编译器都会针对给定的CPU架构选择最快的方法。

参考资料，生成的代码如下：

int main()
{
    time_t t = time(NULL);
       mov    edi,0x0
       call   12 
       mov    QWORD PTR [rbp-0x8],rax
t *= -1;
       neg    QWORD PTR [rbp-0x8]
t = 0 - t;
       neg    QWORD PTR [rbp-0x8]
return 0;
       mov    eax,0x0
}

在两种情况下，它都使用NEG来取反值。 t *= -1 和 t = 0 - t 都会生成以下内容：

neg QWORD PTR [rbp-0x8]
14

只有通过测量应用程序的性能才有一个明智的优化方式。一个好的分析器能告诉你很多东西，但是简单地计时你的程序执行和各种修改也可以大有帮助。不过我首先会选择使用分析器来找到瓶颈所在。

至于你的具体问题，正如其他人指出的那样，这将高度依赖于架构。

5
编译器足够智能，可以将此转换为高效的操作。例如：
C源代码
void f()
{
    int a = 7, b = 7;
    a *= -1;
    b = -b;
}

使用gcc -S a.c命令可以生成汇编代码。

    .file    "a.c"
    .text
    .globl    f
    .type    f, @function
f:
.LFB0:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    $7, -8(%rbp) ; assign 7
    movl    $7, -4(%rbp) ; assign 7
    negl    -8(%rbp)     ; negate variable
    negl    -4(%rbp)     ; negate variable
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size    f, .-f
    .ident    "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
    .section    .note.GNU-stack,"",@progbits

这是在使用Ubuntu 12.04和gcc 4.6.3的PC上。您的架构可能会不同。

4
乘法在几乎所有设备上都会变慢。这是一个更为复杂的操作。
然而，你的编译器可能聪明到足以自行进行转换。 在现代 CPU 上，操作可以以这样的方式重叠，以至于指令的额外时间不会导致执行时间增加，因为它与其他工作重叠。 而且，除非你要执行许多次，否则很可能差异太小而无法测量，除非你付出了大量的努力。
通常先编写清晰易懂的代码，如果必要再进行优化。 如果你想得到一个变量的负值，请写 "-value" 而不是 "-1*value"，因为它更准确地反映了你的意图，而不仅仅是一种计算方法。
2

以下是gcc 4.6.1使用-O选项的效果：

double a1(double b) { return -b; }       // xors sign bit with constant, 2 instr
                                         // movsd   .LC0(%rip), %xmm1   (instr 1)
                                         // xorpd   %xmm1, %xmm0        (instr 2)
                                         // ret                     (not counted)
double a2(double b) { return -1.0*b; }   // xors sign bit with constant, 2 instr
                                         // same code as above
double a3(double b) { return 0.0-b; }    // substract b from 0,  3 instructions
                                         // xorpd   %xmm1, %xmm1
                                         // subsd   %xmm0, %xmm1
                                         // movapd  %xmm1, %xmm0    (+ret)
int a4(int a){return -a;}                // neg rax   (+ret)  1 instruction
int a5(int a){return a*(-1);}            // neg rax
int a6(int a){return 0-a;}               // neg rax
double a7(double b) { return 0-b;}       // same as a3() -- 3 instructions

因此，建议的优化方法在这个编译器上会使情况变得更糟（取决于数组类型）。
然后是有关乘法比加法慢的问题。一个经验法则是，如果乘法和加法一样快，我们谈论的是DSP体系结构或DSP扩展：Texas C64、Arm NEON、Arm VFP、MMX、SSE。同样适用于许多浮点扩展，从Pentium开始，FADD和FMUL的延迟为3个周期，吞吐量为每个周期1个指令。ARM整数核心也可以在1个周期内执行乘法。
1

好的，我试图清理我的混乱，并将我的愚蠢转化为有用的知识，不仅对我自己，还对其他人。

主要结论和总结：

这种优化是由编译器自动完成的，在这种情况下，两种方法都被编译成了x86上的一个单一的ASM指令。（见上面的帖子）不要让编译器的工作比必须的更加艰难，只需按照逻辑做即可。

几个答案表明，这两种方式编译成了完全相同的指令。

简而言之

为了纠正我在这个话题上犯的错误，我决定付出一些努力来澄清这个问题 - 对于那些像我一样在回答这个问题时遭受神奇的错误答案的人们。

否定一个数字取决于架构和数据表示方式。

符号和大小表示法

我曾经认为这种实现被使用了 - 但事实并非如此。这种实现将数字表示为一个符号位和其余部分的值。因此，它可以表示从-2n-1-1到2n-1-1的数字，并且还具有负零值。在这种表示法中，只需翻转符号位即可：

input ^ -0; // as the negative zero has all bits but the MSB as zero

补码表示法

补码整数表示法将负数表示为正表示的按位取反。然而，从8080开始，使用二进制补码。这种表示法的一个奇怪后果是负零，可能会带来很多麻烦。此外，所表示的数字范围从-2n-1-1到2n-1-1，其中n是存储数字的位数。

在这种情况下，最快的“手动”取反数字的方法是翻转表示符号的所有位：

input ^ 0xFFFFFFFF; //assuming 32 bits architecture

或者

input ^ -0; //as negative zero is a "full one" binary value

二进制补码表示法

更广泛使用的表示法是二进制补码系统。它表示-2n-1到2n-1-1范围内的数字，并且仅有一个零值。它将正数范围表示为它们的普通二进制表示。然而，将1添加到2n-1-1（所有位数除了最高位都是1）将导致-2n-1（在最高位有一个1，在所有其他位上是零）。

手动否定二进制补码数需要否定所有位并加1：

(input ^ -1) + 1 //as -1 is represented by all bits as 1

然而，由于负值范围比正值范围更广，因此在这种表示中，最负数没有正数对应项，处理这些数字时必须考虑到这一点！将最负值反转将导致其本身，就像零一样（为简单起见，在8位中）。
most negative number: -128, represented as 10000000
inverting all bits: 01111111
adding one: 10000000 -> -128 again

但是请大家记住：过早的优化是万恶之源！（而且在任何资源丰富的架构上，这些都已经成为过去式了）。
*：OP已经通过了这一点，所以这是给像我这样的其他人的提醒。
（自己的注释：（过早地）愚蠢是所有（合理的）负评的根源。）
2
大多数当前体系结构（包括x86）上的有符号整数并没有“符号位”。 - CAFxX
2
在你的机器上尝试一下，看看是否能得到正确的结果。我怀疑你不会得到正确的结果。从0开始尝试。 - Art
1
是的，但在x86上对-1进行异或运算至少不会给出正确的结果：0 ^ (-1) == -1。 - Sergey L.
@Sergey：非常愿意。我这里没有任何C环境的访问权限...而且你说得对，32位移是不允许的。 - ppeterka
阅读了一些资料后，我发现了我的错误，谢谢大家，至少我学到了一些东西！ - ppeterka
显示剩余8条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接