似乎每当我将负int除以正int时,我需要它向下舍入(朝向-inf),而不是朝向0.但是C#和C++都向0舍入.
所以我想我需要一个DivideDownward()方法.我可以用几行来写一个负面的测试,依此类推,但我的想法看起来很糟糕.所以我想知道我是否遗漏了一些东西,如果你有一种"优雅"的方式将负分区向下舍入.
Nor*_*sey 11
每当我将负int除以正int时,我需要它向下舍入.
这是地狱,不是吗？Knuth写道,为什么这是正确的做事方式,但我们仍然坚持传统的整数硬件.
如果能够承受精度损失,最简单和最干净的方法是将32位整数转换为64位,double并在将商转换回整数时使用FP舍入模式向负无穷大舍入.今天的浮点单位非常快,实际上可能比整数单位快得多 ; 可以肯定的是,你必须要衡量.
如果您需要完整的64位整数精度,我通过执行两个条件分支将这个问题作为编译器编写者处理,以便最后分割大小,然后获得正确的符号.但是,当条件分支与分裂相比便宜时,这已经有一段时间了; 在今天的硬件上,我必须先试验才能推荐一些东西.
原则上,您可以使用传统的英特尔80位浮点数来提取64位整数的浮点技巧,但它非常不可移植,我不相信英特尔会继续快速制作该单元.这些天浮点速度在SSE单位.
寻找其他技巧的地方包括Hank Warren的书Hacker's Delight(我的副本在工作中)和用于标准ML 的MLton编译器,它需要整数除法向负无穷大舍入.
无论你做什么,当你确定它时,如果你使用的是C++或C99,请将你的除法程序粘贴到.h文件中并制作它static inline.这样,当您的解决方案对于5年内交付的新的硬件硬件来说不是最理想的时候,您就有一个地方可以更改它.
小智 8
你可以通过这样做摆脱任何分支:
inline int DivideRoundDown(int a_numerator, int a_denominator)
{
return (a_numerator / a_denominator) + ((a_numerator % a_denominator) >> 31);
}
小智 7
假设b总是正数,这是一个廉价的解决方案:
inline int roundDownDivide(int a, int b) {
if (a >= 0) return a/b;
else return (a-b+1)/b;
}
如果你想以相对简洁的方式使用整数来编写它,那么你可以这样写:
var res = a / b - (a % b < 0 ? 1 : 0);
这可能会编写很多指令,但它可能仍然比使用浮点更快.
警告:对于输入a = -1,此帖子会产生错误的结果.请参阅其他答案.-Cam
[C++]
这可能就是你所说的'kludgey',但这就是我想出来的;)
int divideDown(int a, int b){
int r=a/b;
if (r<0 && r*b!=a)
return r-1;
return r;
}
在if语句中,我把r <0 - 但是我不确定这是不是你想要的.您可能希望将if语句更改为
if (a<0 && b>0)
这与你的描述是一致的"似乎每当我将负int除以积极的int "时.
许多编程语言，包括 C 和 C++ 的旧标准，都保证除法规则，即
a = b * (a / b) + a % b
a/b即使和的确切值a%b未定义。[0]可以利用以下代码（等效的）来计算多种语言和平台中的所需结果：
int divF(int a, int b) { return a / b - (a % b < 0); }
这是@TomasPetricek 答案的版本。但是，它仅适用于b > 0！
以下代码适用于任何b != 0：[1]
int sign(int x) { return (x > 0) - (x < 0); }
int divF2(int a, int b) { return a / b - (sign(a % b) == -sign(b)); }
然而，向下舍入除法（又名向下取整除法、又名高德纳除法）并不总是可取的。有人认为[2]欧几里得除法是最普遍有用的除法。对于 则向下舍入b > 0，对于 则向上舍入b < 0。它具有一个很好的属性，即对于所有和，兼容定义的余数的值始终为非负数，与它们的符号无关。此外，它与二进制补码机上用于二次幂除数的位移和屏蔽相一致。是的，计算速度也更快：ab
int divE(int a, int b) {
int c = a % b < 0;
return a / b + (b < 0 ? c : -c);
}
所有三个版本都在 amd64 上使用 clang 生成无分支代码-O3。然而，在二进制补码架构上，以下方法可能会稍微快一些：
int divE2(int a, int b) { return a / b + (-(a % b < 0) & (b < 0 ? 1 : -1)); }
divF:
cdq
idiv esi
sar edx, 31
add eax, edx
divF2:
cdq
idiv esi
xor ecx, ecx
test edx, edx
setg cl
sar edx, 31
add edx, ecx
xor ecx, ecx
test esi, esi
setg cl
shr esi, 31
sub esi, ecx
xor ecx, ecx
cmp edx, esi
sete cl
sub eax, ecx
Chazz:
cdq
idiv esi
test edx, edx
cmove edi, esi
xor edi, esi
sar edi, 31
add eax, edi
divE:
cdq
idiv esi
mov ecx, edx
shr ecx, 31
sar edx, 31
test esi, esi
cmovs edx, ecx
add eax, edx
divE2:
cdq
idiv esi
sar edx, 31
shr esi, 31
lea ecx, [rsi + rsi]
add ecx, -1
and ecx, edx
add eax, ecx
simple truncating division:
2464805950: 1.90 ns -- base
euclidean division:
2464831322: 2.13 ns -- divE
2464831322: 2.13 ns -- divE2
round to -inf for all b:
1965111352: 2.58 ns -- Chazz
1965111352: 2.64 ns -- divF2
1965111352: 5.02 ns -- Warty
round to -inf for b > 0, broken for b < 0:
1965143330: 2.13 ns -- ben135
1965143330: 2.13 ns -- divF
1965143330: 2.13 ns -- Tomas
4112595000: 5.79 ns -- runevision
round to -inf, broken for b < 0 or some edge-cases:
4112315315: 2.24 ns -- DrAltan
1965115133: 2.45 ns -- Cam
1965111351: 7.76 ns -- LegsDrivenCat
-O3在 FreeBSD 12.2、i7-8700K CPU @ 3.70GHz 上使用 clang 编译。第一列是产生相同结果的校验和分组算法。base是用于衡量测试开销的最简单的截断除法。
试验台：
static const int N = 1000000000;
int rng[N][2], nrng;
void push(int a, int b) { rng[nrng][0] = a, rng[nrng][1] = b, ++nrng; }
SN_NOINLINE void test_case(int (*func)(), const char *name) {
struct timespec t0, t1;
clock_gettime(CLOCK_PROF, &t0);
int sum = func();
clock_gettime(CLOCK_PROF, &t1);
double elapsed = (t1.tv_sec - t0.tv_sec)*1.e9 + (t1.tv_nsec - t0.tv_nsec);
printf("%10u: %5.2f ns -- %s\n", sum, elapsed/N, name);
}
#define ALL_TESTS(X) X(base) X(divF) X(divF2) X(divE) X(divE2) X(ben135) X(DrAltan) X(Cam) X(Tomas) X(Warty) X(Chazz) X(runevision) X(LegsDrivenCat)
#define LOOP_TEST(X) \
SN_NOINLINE int loop_##X() { \
int sum = 0; \
for(int i = 0; i < N; ++i) sum += X(rng[i][0], rng[i][1]); \
return sum; \
} \
/**/
ALL_TESTS(LOOP_TEST)
int main() {
srandom(6283185);
push(INT_MAX, 1); push(INT_MAX, -1); push(INT_MIN, 1);
push(INT_MAX, 2); push(INT_MAX, -2); push(INT_MIN, 2); push(INT_MIN, -2);
while(nrng < N) {
int a = random() - 0x40000000, b;
do b = (random() >> 16) - 0x4000; while(b == 0);
push(a,b);
}
#define CALL_TEST(X) test_case(loop_##X, #X);
ALL_TESTS(CALL_TEST)
}