是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彙編更容易閱讀，但如果你想86只是刪除拱形標誌）

_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個指令VS foo1這需要幾條指令。它必須將數據移動到FP HW寄存器（vmov），整數轉換爲浮動（vcvt.f64.u32）調用exp函數，然後將轉換的回答返回到一個UINT（vcvt.u32.f64），並將其從FP HW移回GP寄存器。

Answer 2

這取決於編譯器，但一般情況下（編譯器不完全是braindead時）是的，移位是一個CPU指令，另一個是函數調用，包括保存當前狀態以設置堆棧幀這需要很多指導。

Answer 3

通常是的，因爲移位對於處理器來說是非常基本的操作。

在另一方面，許多編譯器優化代碼，從而提高電源其實只是有點移位。

Answer 4

是的。雖然我無法說多少。確定的最簡單方法是對其進行基準測試。

的pow功能使用雙打......至少，如果它符合C標準。即使該函數在看到2的基數時使用了位移，仍然會進行測試和分支以得出結論，屆時您的簡單位移將會完成。我們甚至沒有考慮到函數調用的開銷。

對於等價，我假設你想用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