我需要计算
result = (dividend * factor) / divisor
其中
dividend: full range of int64_t values
factor: either a full range of uint32_t values or as a special case 2^32
divisor: positive values of int64_t
result: is guaranteed to fit in a int32_t
我需要在没有任何微控制器库的情况下用普通的C/C++来完成这项工作。编译器支持int64_t和uint64_t类型;很可能没有乘法或除法的硬件实现。目前,我有一个uint32_t因子的解决方案,但我需要一个因子2^32的解决方案。
OP:"目前我有一个解决uint32_t因素的方法"
factor == 2^32
是一个角落的情况,是这里需要解决的全部问题,因为OP的"变通方法"可以处理因素[0 ... 2^32-1]
。
如果dividend
可以在没有溢出的情况下加倍,那么只需将factor == 2^31
与加倍的dividend
一起使用即可。
如果divisor
是偶数,则使用具有减半divisor
的factor == 2^31
@风向标
否则dividend
较大。回想一下,商在[-2^31 ... 2^31-1]
范围内。通常,divisor
对大dividend
和factor == 2^32
的乘积将超出int32_t
的范围,因此这些超出范围的组合不受关注,因为"结果:保证适合int32_t
"。
可接受的边缘条件出现在CCD_ 16范围的边缘附近的最终商。
pow(2,63) == 9223372036854775808
pow(2,62) == 4611686018427387904
pow(2,32) == 4294967296
pow(2,31) == 2147483648
Smallest Dividends Factor Largest Divisors Smallest Quotients
-4611686018427387905 4294967296 -9223372036854775807 2147483648.00+
-4611686018427387905 4294967296 9223372036854775807 -2147483648.00+ OK
4611686018427387904 4294967296 -9223372036854775807 -2147483648.00+ OK
4611686018427387904 4294967296 9223372036854775807 2147483648.00+
经过测试,dividend
和divisor
是INT32_MIN
中唯一可代表的答案。
样本代码:
int32_t muldiv64(int64_t dividend, uint64_t factor, int64_t divisor) {
if (factor >= 0x100000000) {
assert(factor == 0x100000000);
factor /= 2;
if (dividend >= INT64_MIN/2 && dividend <= INT64_MAX/2) {
dividend *= 2;
} else if (divisor %2 == 0) {
divisor /= 2;
} else {
return INT32_MIN;
}
}
return workaround_for_the_uint32_t_factor(dividend, factor, divisor);
}
最初的问题是检测这种边缘条件以及如何处理。workaround_for_the_uint32_t_factor()
可能还没有编码,因此没有发布。