[解決済み] 結果がどうであれ、ゼロによる除算をサポートする最速の整数除算は何でしょうか？

質問

概要です。

を最速で計算する方法を探しています。

(int) x / (int) y

に対して例外を発生させることなく y==0 . その代わり、私は任意の結果が欲しいだけです。

背景です。

画像処理アルゴリズムをコーディングするとき、私はしばしば（累積）アルファ値で除算する必要があります。最も単純な方法は、整数演算を使用したプレーンな C コードです。私の問題は、通常、次のような結果ピクセルに対してゼロによる除算エラーが発生することです。 alpha==0 . しかし、これはまさに結果が全く重要でないピクセルです。 alpha==0 .

詳細です。

みたいなのを探しています。

result = (y==0)? 0 : x/y;

または

result = x / MAX( y, 1 );

xとyは正の整数です。このコードはネストしたループの中で膨大な回数実行されるので、条件分岐をなくす方法を探しています。

yがバイトの範囲を超えていないとき、私は解決策に満足している

unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];

しかし、これは明らかに大きな範囲ではうまくいきません。

最後の質問は、他のすべての値を変更しないまま、0を他の整数値に変更する最速のビット操作ハックは何かということです。

明確な説明

分岐が高すぎるというのは100%ないですね。ただし、使用するコンパイラが異なるので、最適化の少ないベンチマークが良い（確かに疑問は残るが）。

確かに、ビットをいじることに関してはコンパイラは素晴らしいのですが、"don't care"の結果をCで表現できないので、コンパイラが最適化をフル活用することはないでしょうね。

コードは完全にC互換であるべきで、主なプラットフォームはgccとclangとMacOSを備えたLinux 64ビットです。

どのように解決するのですか？

いくつかのコメントに触発されて、私は自分の Pentium 上のブランチを削除して gcc コンパイラーを使用して

int f (int x, int y)
{
        y += y == 0;
        return x/y;
}

コンパイラは基本的に、追加でテストの条件フラグを使えると認識しています。

アセンブリの要求通り。

.globl f
    .type   f, @function
f:
    pushl   %ebp
    xorl    %eax, %eax
    movl    %esp, %ebp
    movl    12(%ebp), %edx
    testl   %edx, %edx
    sete    %al
    addl    %edx, %eax
    movl    8(%ebp), %edx
    movl    %eax, %ecx
    popl    %ebp
    movl    %edx, %eax
    sarl    $31, %edx
    idivl   %ecx
    ret

これはとても人気のある質問と回答になってしまったので、もう少し詳しく説明します。上記の例は、コンパイラが認識するプログラミング慣用句に基づいています。上の例では積分演算でブール式が使われていますが、このためにハードウェアで考案されたのが条件フラグの使用です。一般にC言語では、条件フラグはイディオムを使ってのみアクセス可能である。そのため、インラインアセンブリに頼らずに移植可能な多倍長整数ライブラリを C で作るのはとても難しいのです。私の推測では、ほとんどのまともなコンパイラーは上記のイディオムを理解すると思います。

上のコメントのいくつかで指摘されているように、分岐を回避するもうひとつの方法は、述語的実行です。そこで私は、philipp の最初のコードと私のコードを、ARM からのコンパイラーと、述語的実行を特徴とする ARM アーキテクチャ用の GCC コンパイラーを通して実行しました。両方のコンパイラーは、コードの両方のサンプルで分岐を回避しました。

ARM コンパイラーを使用した Philipp のバージョン。

f PROC
        CMP      r1,#0
        BNE      __aeabi_idivmod
        MOVEQ    r0,#0
        BX       lr

GCCを使ったPhilippのバージョン。

f:
        subs    r3, r1, #0
        str     lr, [sp, #-4]!
        moveq   r0, r3
        ldreq   pc, [sp], #4
        bl      __divsi3
        ldr     pc, [sp], #4

ARMコンパイラを使った私のコードです。

f PROC
        RSBS     r2,r1,#1
        MOVCC    r2,#0
        ADD      r1,r1,r2
        B        __aeabi_idivmod

GCCを使った私のコードです。

f:
        str     lr, [sp, #-4]!
        cmp     r1, #0
        addeq   r1, r1, #1
        bl      __divsi3
        ldr     pc, [sp], #4

このバージョンの ARM は除算のためのハードウェアを持っていないので、すべてのバージョンはまだ除算ルーチンへの分岐を必要としますが、そのためのテストは y == 0 のテストはプリディケイテッド実行によって完全に実装されています。