有效地乘以 7

我最近遇到了以下面试问题：

如何以高效且优化的方式将数字乘以 7？

我知道我可以乘以 8（或左移三位），然后减去原始值：

num = (num << 3) - num;

但还有其他解决方案吗？

对于有限范围，您可以使用查找表：

static unsigned int mult7[] = {0, 7, 14, 21, ...};
unsigned int three = 3;
unsigned int twenty_one = mult7[three];

这可能sound愚蠢（这可能是针对这个特定情况的），但对于有的事情来说它通常很方便real成本来计算。我只是不确定乘以七是否算作其中一种情况。

首先，乘以x7（或移位x剩下三位然后减去x）是完全可以在CPU内部完成的操作。通过表查找，您可能会看到乘以四（左移两位），然后进行加法以获得正确的地址，但随后您必须访问内存才能进行实际查找 - 即使使用缓存和所有其他方法当前 CPU 具有的奇妙技巧，这可能会减慢速度。

There's also a good chance that your compiler will already know all the tricks about how to multiply fast. If your seven is a constant (or const int or equivalent), the compiler will probably already have chosen the fastest way and there's a good chance the compiler writers know a lot more about this sort of stuff than mere mortals :-) ^(a)

但对于计算成本的情况is相对较高，计算一次值并将它们作为查找表嵌入到代码中是标准优化策略之一（以时间换取空间）。

^(a) Examine the following code:

#include <stdio.h>

static int mult7 (int num) {
    return num * 7;
}

int main (int argc, char *argv[]) {
    printf ("%d\n", mult7 (atoi (argv[1])));
    return 0;
}

通过正常编译gcc, mult7左移三位并减去技巧：

_mult7:
    pushl   %ebp             ; stack frame setup.
    movl    %esp, %ebp
    movl    8(%ebp), %edx    ; get value to edx
    movl    %edx, %eax       ;    and eax.
    sall    $3, %eax         ; eax <- eax * 8.
    subl    %edx, %eax       ; eax <- eax - edx.
    popl    %ebp             ; stack frame teardown and return.
    ret

At -O3（我喜欢称之为疯狂的优化级别），整个事情都内联到main with:

call    _atoi
movl    $LC0, (%esp)

leal    0(,%eax,8), %edx     ; these two are the relevant instructions.
subl    %eax, %edx

movl    %edx, 4(%esp)
call    _printf

请注意，此内联操作仅由于函数的静态性质而可能 - 如果它对链接器可见，则必须将其维护为单独的函数，以防另一个对象文件需要调用它。

如果您脱下static，它确实使其与所有堆栈帧设置和拆卸保持非内联，但它至少仍然使用下面提到的（大概）更有效的技巧。你can摆脱堆栈帧代码gcc如果你使用-fomit-frame-pointer前提是这不会对代码产生不利影响，但这已经开始深入研究黑暗面了:-)

这个技巧是使用LEA设置指令edx to eax * 8然后减去eax从那。与理论相同sall/subl在正常优化时，只是机制略有不同。

底线，相信你的编译器。如果你想乘法num到 7 时，使用以下命令：

num *= 7;

很可能，无论您从这种尝试的微观优化中获得什么改进，您都可以通过查看宏观层面（算法和数据结构选择等）获得更好的改进。