我最近遇到了以下面试问题:
如何以高效优化的方式将数字乘以7？
我知道我可以乘以8(或左移三位)然后减去原始值:
num = (num << 3) - num;
但还有其他解决方案.
pax*_*blo 16
对于有限范围,您可以使用查找表:
static unsigned int mult7[] = {0, 7, 14, 21, ...};
unsigned int three = 3;
unsigned int twenty_one = mult7[three];
这可能听起来愚蠢(很可能是这种特定的情况下),但它往往是很方便的事情,那里是一个真正以计算成本.我不确定将七个计数乘以其中一个案例.
首先,乘以x7(或向x左移三位然后减去x)是一种可以完全在CPU内部完成的操作.使用表查找,您可能会看到乘以4(向左移动两位),然后是添加以获取正确的地址,但是您必须访问内存才能进行实际查找 - 即使使用缓存和所有其他当前CPU有能力的奇妙技巧,这可能会减慢速度.
您的编译器也很有可能已经知道有关如何快速乘法的所有技巧.如果你的七是一个常数(或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它,它确实保持非内联所有堆栈框架设置和拆卸,但它至少仍然使用下面提到的(可能)更有效的技巧.你可以摆脱堆栈框架代码,gcc如果你使用-fomit-frame-pointer提供这不会对代码产生负面影响,但这开始深入研究黑暗的一面:-)
这招是使用LEA指令设置edx于eax * 8再减去eax从.与sall/subl正常优化相同的理论,只是略有不同的机制.
最重要的是,相信你的编译器.如果要乘以num7,请使用以下命令:
num *= 7;
很可能无论您从这种尝试的微优化中获得什么改进,您都可以通过查看宏观级别(算法和数据结构选择等)获得更好的改进.
Kei*_*son 15
要以有效的方式获得7的倍数:
7
7是7的倍数.这回答了你问的问题,但我确定它没有回答你的问题.
编辑:以上是基于问题的原始标题,我刚刚更正.
乘由 7高效,只写,例如:
x * 7
并通过优化调用您的编译器.让编译器弄清楚单个MUL指令或类似的东西对于当前机器(x<<3) - x是否更有效.
这里还有另一个隐含的问题:面试官在寻找什么答案？我希望 "让编译器担心它"将是一个可以接受的答案. (x<<3) - x可能是最明显的微优化 - 但如果x<<3溢出它会产生错误的答案,并且取决于系统它可能比MUL指令慢.
(如果我是面试官,对问题的解释和理解比任何具体答案都要好得多.)
编辑
进一步思考,如果您比编译器更了解可能的值,那么此处讨论的微优化类型可能会有用x.如果你知道,由于程序逻辑的性质,它x总是在0..10的范围内,那么查找表可能比乘法运算更快.或者,如果你知道x99%的时间都在该范围内,那么回溯到实际乘法的查找表可能就是这样.
但是,如果你的程序流程的编译器的分析并没有允许它证明这x始终是在这个范围内,那么就不能执行这种优化.
但这种情况非常罕见.当您的代码在一个x可能为11 的新环境中运行时(可能它在具有更大显示器的设备上运行),kaboom.而且性能改善很可能首先并不显着.
有时微观优化是合适的,但在开发和测试时间方面存在大量成本.只有在实际测量表明它值得的时候才这样做.
我这样做的方式就像
num = (num << 3) - num;
即.2 ^ 3 = 8,然后减去乘以的数字得到7的倍数.
我刚用gcc编译了下面的代码:
int mul(int num)
{
return num * 7;
}
这是它编译为的gdb转储:
Dump of assembler code for function mul:
0x00000000004004c4 <+0>: push rbp
0x00000000004004c5 <+1>: mov rbp,rsp
0x00000000004004c8 <+4>: mov DWORD PTR [rbp-0x4],0xa
0x00000000004004cf <+11>: mov edx,DWORD PTR [rbp-0x4]
0x00000000004004d2 <+14>: mov eax,edx
0x00000000004004d4 <+16>: shl eax,0x3
0x00000000004004d7 <+19>: sub eax,edx
0x00000000004004d9 <+21>: mov DWORD PTR [rbp-0x4],eax
0x00000000004004dc <+24>: pop rbp
0x00000000004004dd <+25>: ret
End of assembler dump.
所以看起来我的机器左移3次然后减去乘以的数字是gcc认为可能是最佳的.
编辑:结果优化级别至少为1(-O1),gcc使用lea技巧:
Dump of assembler code for function mul:
0x00000000004004e0 <+0>: lea eax,[rdi*8+0x0]
0x00000000004004e7 <+7>: sub eax,edi
0x00000000004004e9 <+9>: ret
End of assembler dump.