gpt4 book ai didi

64位有符号整数组合乘除运算无溢出

转载 作者:太空狗 更新时间:2023-10-29 16:56:48 25 4
gpt4 key购买 nike

我需要计算

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

我需要在微 Controller 上没有任何库的情况下使用纯 C/C++ 执行此操作。编译器支持 int64_t 和 uint64_t 类型;很可能没有用于乘法或除法的硬件实现。目前我有 uint32_t 因子的解决方法,但我需要因子 2^32 的解决方案。

最佳答案

OP: "Currently I have a workaround for the uint32_t factor"

factor == 2^32 是一个极端情况,是这里需要解决的所有问题,因为 OP 的“解决方法”可以处理 factor [0 ... 2^32 -1].

如果红利可以翻倍而不溢出,简单地使用factor == 2^31 和双倍的红利

如果 divisor 是偶数,则使用 factor == 2^31 和减半的 divisor@Weather Vane

否则 红利 很大。回想一下,商在 [-2^31 ... 2^31-1] 范围内。一般来说,大的dividendfactor == 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+

经过测试,dividenddivisor,唯一可表示的答案在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() 可能尚未编码,因此未发布。

关于64位有符号整数组合乘除运算无溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34498844/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com