ビットシフトによる掛算

ビットシフトによる掛算の例題です。 単純に掛算するだけでは物足りないかもしれないと思いましたので、 100万回の繰り返し計算での通常の掛算との時間の比較を行ってみました。

演算結果は結果のところにあるとおりですが、通常の掛算の方が早くなっています。 やはり、普通に2の指数倍で計算しないと逆に演算時間が掛かるだけですね。。

ビットシフトによる掛算（list_44.c） 
#include <stdio.h>
#include <sys/time.h>
#include <time.h>
#include <unistd.h>
//-----------------------------------------------------------------
// 関数宣言
//-----------------------------------------------------------------
int bit_multi(int calc_m,int calc_n);
inline unsigned long long int RDTSC(void);
double measure_cps();
//-----------------------------------------------------------------

int main()
{
    int n,m;
    int i,result;
    clock_t t1,t2;
    double cpers=measure_cps();
    printf("input n,m(n*m) : ");
    scanf("%d,%d",&n,&m);
    //-------------------------------------------------------
    // 計算1 : ビットシフトによる計算
    //-------------------------------------------------------
    t1 = clock(); // 計算開始時刻
    for(i=0;i<1000000;i++){
        result = bit_multi(n,m); // 計算開始
    }
    t2 = clock(); // 計算終了
    // 処理時間
    printf("bitshift:result = %d\n",result);
    printf("time of loop=%d clock,%lg[sec]\n",t2-t1,(double)((t2-t1)/cpers));
    //-------------------------------------------------------
    // 計算2 : 普通の演算
    //-------------------------------------------------------
    t1 = clock(); // 計算開始時刻
    for(i=0;i<1000000;i++){
        result = n*m; // 計算開始
    }
    t2 = clock(); // 計算終了
    // 処理時間
    printf("normal:result = %d\n",result);
    printf("time of loop=%d clock,%lg[sec]\n",t2-t1,(double)((t2-t1)/cpers));
    
    return 0;
}

//-----------------------------------------------------------------
// ビットシフトによる掛け算
//-----------------------------------------------------------------
int bit_multi(int calc_m,int calc_n)
{
    int m,n,ml=0;
    m=calc_m; n=calc_n;
    while(m>1){
        if((m&1) == 0){ n<<=1; m>>=1; }
        else          { ml+=n; m--; }
    }
    n+=ml;
    return n;
}
//-----------------------------------------------------------------
// 時間計測
//-----------------------------------------------------------------
inline unsigned long long int RDTSC(void)
{
    unsigned int h,l;
    /* read Pentium cycle counter */
    __asm__(".byte 0x0f,0x31":"=a" (l),"=d" (h));
    return ((unsigned long long int)h<<32)|l;
}
/* 1クロックに対する処理時間の計測 */
double measure_cps()
{
    double cpers;
    struct timeval     tv1,tv2;
    unsigned long long tsc1,tsc2;
    gettimeofday(&tv2,NULL); tsc2=RDTSC();
    sleep(1);
    gettimeofday(&tv1,NULL); tsc1=RDTSC();
    cpers = (double)(tsc1-tsc2)/((tv1.tv_sec-tv2.tv_sec)*1000000
                                 +(tv1.tv_usec-tv2.tv_usec));
    return cpers;
}
実行結果 
Gami[149]% list_44.exe
input n,m(n*m) : 7,88
bitshift:result = 616
time of loop=70 clock,0.0501621[sec]
normal:result = 616
time of loop=0 clock,0[sec]
Gami[150]%
inserted by FC2 system