不管结果是什么，支持被零除的最快整数除法是什么？
摘要：
我在寻找最快的计算方法
(int) x / (int) y而不会得到y==0的异常。相反，我只想要一个任意的结果。
背景：
在编写图像处理算法的代码时，我经常需要除以(累积的) alpha值。最简单的变体是带有整数运算的纯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为任何其他整数值，而所有其他值保持不变？
Clarifications
我不是百分之百确定分支是否太昂贵。但是，由于使用了不同的编译器，所以我更喜欢进行少量优化的基准测试(这确实是有问题的)。
当然，当涉及到位旋转时，编译器是很棒的，但是我不能用C来表达“无关”的结果，所以编译器永远不能使用所有的优化。
代码应该是完全兼容C语言的，主要的平台是64位的Linux64位的gcc和clang和MacOS。
回答 4
Stack Overflow用户
发布于 2013-05-28 01:14:32
受一些注释的启发，我删除了奔腾和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编译器运行，该体系结构具有谓词执行的特点。两个编译器都避免了两个示例代码中的分支：
Philipp的ARM编译器版本：
f PROC
CMP r1,#0
BNE __aeabi_idivmod
MOVEQ r0,#0
BX lr菲利普与GCC的版本：
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的测试是通过谓词执行完全实现的。
Stack Overflow用户
发布于 2013-05-28 02:13:10
以下是一些具体的数字，在Windows上使用的是GCC 4.7.2：
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned int result = 0;
for (int n = -500000000; n != 500000000; n++)
{
int d = -1;
for (int i = 0; i != ITERATIONS; i++)
d &= rand();
#if CHECK == 0
if (d == 0) result++;
#elif CHECK == 1
result += n / d;
#elif CHECK == 2
result += n / (d + !d);
#elif CHECK == 3
result += d == 0 ? 0 : n / d;
#elif CHECK == 4
result += d == 0 ? 1 : n / d;
#elif CHECK == 5
if (d != 0) result += n / d;
#endif
}
printf("%u\n", result);
}请注意，我有意不调用srand()，以便rand()始终返回完全相同的结果。还要注意，-DCHECK=0只计算零，因此很明显出现的频率是很明显的。
现在，以不同的方式编译和计时：
$ for it in 0 1 2 3 4 5; do for ch in 0 1 2 3 4 5; do gcc test.cc -o test -O -DITERATIONS=$it -DCHECK=$ch && { time=`time ./test`; echo "Iterations $it, check $ch: exit status $?, output $time"; }; done; done显示可在表格中汇总的输出：
Iterations → | 0 | 1 | 2 | 3 | 4 | 5
-------------+-------------------------------------------------------------------
Zeroes | 0 | 1 | 133173 | 1593376 | 135245875 | 373728555
Check 1 | 0m0.612s | - | - | - | - | -
Check 2 | 0m0.612s | 0m6.527s | 0m9.718s | 0m13.464s | 0m18.422s | 0m22.871s
Check 3 | 0m0.616s | 0m5.601s | 0m8.954s | 0m13.211s | 0m19.579s | 0m25.389s
Check 4 | 0m0.611s | 0m5.570s | 0m9.030s | 0m13.544s | 0m19.393s | 0m25.081s
Check 5 | 0m0.612s | 0m5.627s | 0m9.322s | 0m14.218s | 0m19.576s | 0m25.443s如果零值很少，那么-DCHECK=2版本的性能就很差。随着零开始出现的次数越来越多，-DCHECK=2案例的性能开始明显提高。在其他选择中，真的没有太大的区别。
然而，对于-O3来说，这是一个不同的故事：
Iterations → | 0 | 1 | 2 | 3 | 4 | 5
-------------+-------------------------------------------------------------------
Zeroes | 0 | 1 | 133173 | 1593376 | 135245875 | 373728555
Check 1 | 0m0.646s | - | - | - | - | -
Check 2 | 0m0.654s | 0m5.670s | 0m9.905s | 0m14.238s | 0m17.520s | 0m22.101s
Check 3 | 0m0.647s | 0m5.611s | 0m9.085s | 0m13.626s | 0m18.679s | 0m25.513s
Check 4 | 0m0.649s | 0m5.381s | 0m9.117s | 0m13.692s | 0m18.878s | 0m25.354s
Check 5 | 0m0.649s | 0m6.178s | 0m9.032s | 0m13.783s | 0m18.593s | 0m25.377s在这里，与其他检查相比，检查2没有缺点，并且当零变得更加常见时，它确实保留了好处。
不过，您真的应该衡量一下编译器和代表性样本数据发生了什么变化。
Stack Overflow用户
发布于 2013-05-28 01:44:28
在不了解平台的情况下，无法确切知道最有效的方法，但在通用系统上，这可能接近最优(使用英特尔汇编程序语法)：
(假设除数为ecx，被除数为eax)
mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx四个未分支的单周期指令加上除法。商将以eax表示，其余部分将以edx表示。(这就是为什么你不想派一个编译器去做一个人的工作)。
https://stackoverflow.com/questions/16777456
复制相似问题