割り算 VS 右シフト

C

 除算をビットシフトで実装する古参のCプログラマは結構多い。
「割り算は処理に時間がかかるので、簡単な除算はビットシフトで書くほうがよい。」というのがその人達の主張である。しかし、「最近のコンパイラは賢いので、ビットシフトを使っても使わなくてもたいして速度は変わらない」と主張する人もいる。一体どちらが正しいのだろうか?

 そこで、C言語の商と右シフトでは、gccの解釈はどのように変化するのかを検証してみることにした。

検証方法

 gcc -Sオプションを使用して、C言語のプログラムからアセンブラソースを入手し、実際のプロセッサ内部でどのように命令が実行されるかを確認する。

実行環境

OS:  Ubuntu7.10

GCC: gcc4.1.3

CPU: Intel

検証に使用するプログラム

 準備したC言語のプログラムは、変数valに1024を格納し、それを1/2した結果を表示するだけのシンプルなプログラムである。プログラム(商)は変数val / 2を行うことで除算し、プログラム(左シフト)は変数valを1bit右シフトすることで除算を行っている。

商 div2.c
/* header files */
#include <stdio.h>
#include <stdlib.h>

/* main */
int main (int argc, char *argv[]) {
    int val = 1024;
    int ans = val / 2;
    printf("%d\n", ans);
    return EXIT_SUCCESS;
}
右シフト rshift2.c
/* header files */
#include <stdio.h>
#include <stdlib.h>

/* main */
int main (int argc, char *argv[]) {
    int val = 1024;
    int ans = val >> 1;
    printf("%d\n", ans);
    return EXIT_SUCCESS;
}

割り算 vs 右シフト(割る2)

 2種類のソースを-Sオプションのみをつけコンパイルした。2種類のC言語プログラムから生成されたアセンブラソースには差異が認められた。以下に差異とその付近のソースを示す。

商 div2.s
16        movl    $1024, -12(%ebp)
17        movl    -12(%ebp), %edx
18        movl    %edx, %eax
19        shrl    $31, %eax
20        addl    %edx, %eax
21        sarl    %eax
22        movl    %eax, -8(%ebp)
23        movl    -8(%ebp), %eax
24        movl    %eax, 4(%esp)
右シフト rshift.s
16        movl    $1024, -12(%ebp)
17        movl    -12(%ebp), %eax
18        sarl    %eax
19        movl    %eax, -8(%ebp)
20        movl    -8(%ebp), %eax
21        movl    %eax, 4(%esp)

 上記のソースを見る限り、div2.sとrshift2.sはどちらも算術右シフトをすることで除算を行っている。しかし、rshift2.sよりもdiv2.sのほうが3行分ソース行数が多い。(18行目から20行目)どうやらこれは割り算と右シフトの、負の整数型データの扱いの違いによって生じたもののようだ。

割り算と右シフトはそもそも違う

例えば、整数型の5から2を割る場合、単純に5 / 2しても、5 >> 1しても、結果は2となる。ところが整数型の-5から2を割る場合、-5 / 2とすると結果は-2となり、-5 >> 1とすると結果は-3となる。

つまり、割り算と右シフトでは、負の数の小数点以下の丸め方が異なるわけである。上記div2.sの18行目から20行目は、この問題を、算術右シフトによって除算を行う前に、31ビット分論理右シフトをすることで符号ビットを1ビット目までずらし、演算対象との和をとることで解決している。

div2.s 18行目から21行目の動作 (5 / 2の場合)

div2.s 18行目から21行目の動作 (-5 / 2の場合)

割り算 vs 右シフト(割る2)の結果

 若干右シフトのほうが速い。

割り算 VS 右シフト その2に続く