地板划分是指结果始终向下（朝向-∞），而不是0：
是否有可能在C / C ++中有效地实现floored或euclidean整数除法？
（显而易见的解决方案是检查红利的标志）
五年后我正在重新审视这个问题，因为这对我也很重要。我对x86-64的两个纯C版本和两个内联汇编版本进行了一些性能测量，结果可能很有趣。
经过测试的地板划分变体是：
CMOV版本。以下是我的基准程序：
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#ifndef VARIANT
#define VARIANT 3
#endif
#if VARIANT == 0
#define floordiv(a, b) (((a) < 0)?((((a) + 1) / (b)) - 1):((a) / (b)))
#elif VARIANT == 1
#define floordiv(a, b) ((((a) < 0)?((a) - ((b) - 1)):(a)) / (b))
#elif VARIANT == 2
#define floordiv(a, b) ({ \
int result; \
asm("test %%eax, %%eax; jns 1f; sub %1, %%eax;" \
"add $1, %%eax; 1: cltd; idivl %1;" \
: "=a" (result) \
: "r" (b), \
"0" (a) \
: "rdx"); \
result;})
#elif VARIANT == 3
#define floordiv(a, b) ({ \
int result; \
asm("mov %%eax, %%edx; sub %1, %%edx; add $1, %%edx;" \
"test %%eax, %%eax; cmovs %%edx, %%eax; cltd;" \
"idivl %1;" \
: "=a" (result) \
: "r" (b), \
"0" (a) \
: "rdx"); \
result;})
#endif
double ntime(void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return(tv.tv_sec + (((double)tv.tv_usec) / 1000000.0));
}
void timediv(int n, int *p, int *q, int *r)
{
int i;
for(i = 0; i < n; i++)
r[i] = floordiv(p[i], q[i]);
}
int main(int argc, char **argv)
{
int n, i, *q, *p, *r;
double st;
n = 10000000;
p = malloc(sizeof(*p) * n);
q = malloc(sizeof(*q) * n);
r = malloc(sizeof(*r) * n);
for(i = 0; i < n; i++) {
p[i] = (rand() % 1000000) - 500000;
q[i] = (rand() % 1000000) + 1;
}
st = ntime();
for(i = 0; i < 100; i++)
timediv(n, p, q, r);
printf("%g\n", ntime() - st);
return(0);
}
我使用GCC 4.9.2用gcc -march=native -Ofast编译了这个，在我的Core i5-2400上的结果如下。从运行到运行结果都是相当可重复的 - 它们总是以相同的顺序着陆，至少。
因此，CMOV的实施至少会将其他人从水中吹走。让我感到惊讶的是，变种2出现了相当广泛的纯C版本（变体1）。我原以为编译器应该能够发出至少和我一样高效的代码。
以下是一些其他平台，供比较：
AMD Athlon 64 X2 4200 +，GCC 4.7.2：
Con Ez-1271，CCC第2部分：
作为最后一点，我或许应该警告不要过于严肃地对待CMOV版本的明显性能优势，因为在现实世界中，其他版本中的分支可能不会像在此基准测试中那样完全随机，并且如果分支预测器可以做一个合理的工作，分支版本可能会变得更好。但是，实际情况将取决于实际使用的数据，因此尝试做任何通用基准可能毫无意义。
我写了一个测试程序来对这里提出的想法进行基准测试：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#define N 10000000
#define M 100
int dividends[N], divisors[N], results[N];
__forceinline int floordiv_signcheck(int a, int b)
{
return (a<0 ? a-(b-1) : a) / b;
}
__forceinline int floordiv_signcheck2(int a, int b)
{
return (a - (a<0 ? b-1 : 0)) / b;
}
__forceinline int floordiv_signmultiply(int a, int b)
{
return (a + (a>>(sizeof(a)*8-1))*(b-1)) / b;
}
__forceinline int floordiv_floatingpoint(int a, int b)
{
// I imagine that the call to floor can be replaced to a cast
// if you can get FPU rounding control to work (I couldn't).
return floor((double)a / b);
}
void main()
{
for (int i=0; i<N; i++)
{
dividends[i] = rand();
do
divisors[i] = rand();
while (divisors[i]==0);
}
LARGE_INTEGER t0, t1;
QueryPerformanceCounter(&t0);
for (int j=0; j<M; j++)
for (int i=0; i<N; i++)
results[i] = floordiv_signcheck(dividends[i], divisors[i]);
QueryPerformanceCounter(&t1);
printf("signcheck : %9llu\n", t1.QuadPart-t0.QuadPart);
QueryPerformanceCounter(&t0);
for (int j=0; j<M; j++)
for (int i=0; i<N; i++)
results[i] = floordiv_signcheck2(dividends[i], divisors[i]);
QueryPerformanceCounter(&t1);
printf("signcheck2 : %9llu\n", t1.QuadPart-t0.QuadPart);
QueryPerformanceCounter(&t0);
for (int j=0; j<M; j++)
for (int i=0; i<N; i++)
results[i] = floordiv_signmultiply(dividends[i], divisors[i]);
QueryPerformanceCounter(&t1);
printf("signmultiply : %9llu\n", t1.QuadPart-t0.QuadPart);
QueryPerformanceCounter(&t0);
for (int j=0; j<M; j++)
for (int i=0; i<N; i++)
results[i] = floordiv_floatingpoint(dividends[i], divisors[i]);
QueryPerformanceCounter(&t1);
printf("floatingpoint: %9llu\n", t1.QuadPart-t0.QuadPart);
}
结果：
signcheck : 61458768
signcheck2 : 61284370
signmultiply : 61625076
floatingpoint: 287315364
所以，根据我的结果，检查标志是最快的：
(a - (a<0 ? b-1 : 0)) / b
由于分支很昂贵，因此可以更有效地提出一些可以根据符号自由分支的结果来纠正结果。
请参阅Chapter 2的Hacker's Delight第20页，了解如何进入标志。
是否有可能在C / C ++中有效地实现floored或euclidian整数除法？
是。
（显而易见的解决方案是检查红利的标志）
我完全同意，并且很难相信存在明显更快的替代方案。
请注意：当涉及到2的幂时，x86 sar指令执行浮动除法。
由于IEEE-754指定round -inf作为所需的舍入模式之一，我想你的问题的答案是肯定的。但也许您可以解释一下，如果您正在编写编译器，或者知道如何使用特定的编译器来执行操作，您是否想知道如何实现该过程？