2 ^ n指数计算真的比位移效率低吗？

Question

如果我做:

int x = 4;
pow(2, x);

这真的是效率低于仅仅这样做:

1 << 4

？

Answer 1

是.显示这个的简单方法是编译以下两个执行相同操作的函数,然后查看反汇编.

#include <stdint.h>
#include <math.h>

uint32_t foo1(uint32_t shftAmt) {
    return pow(2, shftAmt);
}

uint32_t foo2(uint32_t shftAmt) {
    return (1 << shftAmt);
}

cc -arch armv7 -O3 -S -o - shift.c (我碰巧发现ARM asm更容易阅读,但如果你想要x86只删除arch标志)

    _foo1:
@ BB#0:
    push    {r7, lr}
    vmov    s0, r0
    mov r7, sp
    vcvt.f64.u32    d16, s0
    vmov    r0, r1, d16
    blx _exp2
    vmov    d16, r0, r1
    vcvt.u32.f64    s0, d16
    vmov    r0, s0
    pop {r7, pc}

_foo2:
@ BB#0:
    movs    r1, #1
    lsl.w   r0, r1, r0
    bx  lr

您可以看到foo2只需要2条指令,foo1其中需要多条指令.它必须将数据移动到FP HW寄存器(vmov),将整数转换为float(vcvt.f64.u32)调用该exp函数,然后将应答转换回uint(vcvt.u32.f64)并将其从FP HW移回GP寄存器.

Answer 2

是的。虽然我不能说多少。确定它的最简单方法是对其进行基准测试。

该pow函数使用双精度...至少，如果它符合 C 标准。即使该函数在看到 的基数时使用了 bitshift 2，仍然会进行测试和分支以得出该结论，届时您的简单 bitshift 将完成。我们甚至还没有考虑函数调用的开销。

为了等效，我假设您打算使用1 << x而不是1 << 4.

也许编译器可以优化这两者，但优化对pow. 如果您需要最快的方法来计算 2 的幂，请使用移位来完成。

更新...因为我提到它很容易进行基准测试，所以我决定这样做。我碰巧有 Windows 和 Visual C++，所以我使用了它。结果会有所不同。我的程序：

#include <Windows.h>

#include <cstdio>
#include <cmath>
#include <ctime>

LARGE_INTEGER liFreq, liStart, liStop;


inline void StartTimer()
{
    QueryPerformanceCounter(&liStart);
}


inline double ReportTimer()
{
    QueryPerformanceCounter(&liStop);
    double milli = 1000.0 * double(liStop.QuadPart - liStart.QuadPart) / double(liFreq.QuadPart);
    printf( "%.3f ms\n", milli );
    return milli;
}


int main()
{    
    QueryPerformanceFrequency(&liFreq);

    const size_t nTests = 10000000;
    int x = 4;
    int sumPow = 0;
    int sumShift = 0;

    double powTime, shiftTime;

    // Make an array of random exponents to use in tests.
    const size_t nExp = 10000;
    int e[nExp];
    srand( (unsigned int)time(NULL) );
    for( int i = 0; i < nExp; i++ ) e[i] = rand() % 31;

    // Test power.
    StartTimer();
    for( size_t i = 0; i < nTests; i++ )
    {
        int y = (int)pow(2, (double)e[i%nExp]);
        sumPow += y;
    }
    powTime = ReportTimer();

    // Test shifting.
    StartTimer();
    for( size_t i = 0; i < nTests; i++ )
    {
        int y = 1 << e[i%nExp];
        sumShift += y;
    }
    shiftTime = ReportTimer();

    // The compiler shouldn't optimize out our loops if we need to display a result.
    printf( "Sum power: %d\n", sumPow );
    printf( "Sum shift: %d\n", sumShift );

    printf( "Time ratio of pow versus shift: %.2f\n", powTime / shiftTime );

    system("pause");
    return 0;
}

我的输出：

379.466 ms
15.862 ms
Sum power: 157650768
Sum shift: 157650768
Time ratio of pow versus shift: 23.92