c - 高效地乘以 7

Question

我最近遇到了下面的面试题:

How can you multiply a number by 7 in an efficient and optimized way?

我知道我可以乘以 8(或左移三位)然后减去原始值:

num = (num << 3) - num;

但是有没有其他解决办法。

Answer 1

对于有限的范围，可以使用查找表:

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

这可能听起来很愚蠢(而且它可能是针对这种特定情况)，但对于需要实际计算成本的事情，它通常很方便。我只是不确定乘以七算不算其中一种情况。

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

您的编译器也很有可能已经知道有关如何快速乘法的所有技巧。如果你的 7 是一个常量(或 const int 或等价物)，编译器可能已经选择了最快的方法，并且编译器编写者很可能对这类东西了解更多，而不仅仅是凡人 :-) ^(a)

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

---

^(a) 检查以下代码:

#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

在 -O3(我喜欢称之为疯狂的优化级别)，整个事情被内联到 main 中:

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，它确实会使其与所有堆栈框架设置和拆卸保持非内联，但它至少仍然使用下面提到的(可能)更有效的技巧。如果您使用 -fomit-frame-pointer，您可以摆脱 gcc 中的堆栈帧代码，前提是这不会对代码产生不利影响但这开始有点深入到黑暗面:-)

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

最重要的是，相信您的编译器。如果您想将 num 乘以 7，请使用以下命令:

num *= 7;

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