我需要计算
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++中执行此操作，而在微 Controller 上没有任何库。
编译器支持int64_t和uint64_t类型。很可能没有用于乘法或除法的硬件实现。
当前，我有一个针对uint32_t因子的解决方法，但是我需要一个针对因子2 ^ 32的解决方案。
最佳答案
factor == 2^32是一个极端的案例，这里是所有需要解决的问题，因为OP的“解决方法”可以处理[0 ... 2^32-1]的因素。
如果dividend可以加倍而不会溢出，请简单地将factor == 2^31与doublet dividend一起使用。
如果divisor是偶数，则将factor == 2^31与减半的divisor一起使用。 @Weather Vane
否则，dividend很大。回想一下商在[-2^31 ... 2^31-1]范围内。通常，由dividend分配的大factor == 2^32和divisor乘积将超出int32_t范围，因此这些超出范围的组合将不被关注，因为“结果:保证适合int32_t”。
可接受的边条条件以最终商在int32_t范围的边条附近出现。
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()可能尚未编码，因此尚未发布。