以有效的方式乘以7[英] Multiply by 7 in efficient way

本文是小编为大家收集整理的关于以有效的方式乘以7的处理方法,想解了以有效的方式乘以7的问题怎么解决?以有效的方式乘以7问题的解决办法?那么可以参考本文帮助大家快速定位并解决问题。

问题描述

我最近遇到了以下采访问题:

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

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

num = (num << 3) - num;

但是还有其他解决方案.

推荐答案

以有效的方式获得7个倍数:

7

7是7个倍数.回答您问的问题,但我敢肯定它不会回答您的意思是要问的问题.

编辑:以上是基于问题的原始标题,我刚刚纠正了.

有效地将乘以,例如:

x * 7

并通过优化调用您的编译器.让编译器弄清楚当前机器..

这里还有另一个隐含的问题:面试官正在寻找什么答案?我希望"让编译器担心"将是一个可以接受的答案. (x<<3) - x可能是最明显的微观优化 - 但是如果x<<3溢出,它可能会产生错误的答案,并且根据系统的不同,它可能比MUL指令慢.

(如果我是面试官,对问题的理解和理解比任何特定答案都给人留下了深刻的印象.)

编辑

在进一步的思考中,如果您比编译器更多地了解x的可能值,那么此处讨论的微观量化的种类可能会有用.如果您知道,由于程序逻辑的性质,x将始终在0..10范围内,那么查找表很容易比乘法更快.或者,如果您知道x在该范围内99%的时间,则有一个后备向实际乘法的查找表可能只是事物.

但是,如果编译器对程序流的分析不允许证明 x始终在该范围内,那么它就无法执行这种优化.

但是这种情况非常罕见.当您的代码在x的新环境中运行时(也许是在具有较大显示屏的设备上运行)时, kaboom .首先,性能提高很可能并不重要.

有时候微观优化是适当的,但是开发和测试时间有很大的成本.仅当实际测量表明它值得.

其他推荐答案

在有限的范围内,您可以使用查找表:

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

这May sound 愚蠢(这可能是针对这种特定情况),但是对于有 real 计算成本的东西通常很方便.我只是不确定将七个算数乘以其中一种情况.

对于开始,将x乘以7(或剩下三个位,然后减去x)是可以完全在CPU内部完成的操作.使用桌子查找,您可能会看到一个乘乘以四个(剩下的两个位),然后添加以获取正确的地址,但是您必须访问内存才能进行实际查找 - 即使使用缓存以及其他所有奇妙的技巧当前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

at -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,它确实确实将其与所有堆栈框架设置和拆卸拆下来保持不合格,但至少它仍然使用(可能是)(可能是)更有效的技巧.您 can 如果使用-fomit-frame-pointer,请摆脱gcc中的堆栈框架代码

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

底线,相信您的编译器.如果要乘以num 7,请使用以下内容:

num *= 7;

是,无论您从这种尝试的微观优化中得到什么改进,您都可以通过查看宏(算法和数据结构选择等)来更好地改进.

.

其他推荐答案

我要做的方式将是

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.

本文地址:https://www.itbaoku.cn/post/359310.html