は2^n個の指数計算がビットシフトよりも効率的ではありませんか？

Question

私がしなければ：

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

は本当にそのはるかに少ない効率的なだけで行うよりもです：

1 << 4 

？

Answer 1

はい。これを表示する簡単な方法は、同じことをする次の2つの関数をコンパイルし、逆アセンブリを調べることです。

#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をしたい場合は、単にアーチフラグを削除）

_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だけでいくつかの命令を取るfoo1対2つの手順を取る見ることができます。データをFP HWレジスタ（vmov）に移動し、整数をfloat（vcvt.f64.u32）に変換してexp関数を呼び出すと、その応答がuint（vcvt.u32.f64）に変換され、FP HWからGPレジスタ。

Answer 2

これはコンパイラに依存しますが、一般的に（コンパイラが完全にbraindeadでない場合）はい、シフトは1つのCPU命令であり、もう1つは関数呼び出しであり、現在の状態をスタックフレーム多くの指示が必要です。

Answer 3

通常、ビットシフトはプロセッサにとって非常に基本的な操作です。

一方、多くのコンパイラはコードを最適化しているため、電力を上げることは実際には少しシフトしています。

Answer 4

はい。どれくらい私は言うことができませんが。それをベンチマークするのが最も簡単な方法です。

pow関数は、double型を使用します...少なくともC標準に準拠している場合。たとえその関数が基底が2と見なされてもビットシフトを使用したとしても、その結論に達するまでテストと分岐が行われ、単純なビットシフトが完了します。また、関数呼び出しのオーバーヘッドについてはまだ検討していません。

1 << 4の代わりに1 << xを使用することを前提としています。

おそらくコンパイラはこれらの両方を最適化できますが、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