c++ - 无溢出的 32 位整数缩放

Question

您好，我有以下值:

uint32_t value = 1230000;
uint32_t max_value = 1234567;

现在，我想执行缩放:

uint32_t scaled = value * 1000000 / max_value;

问题是如果我使用 32 位整数，那么大的数字会溢出。另一方面，我不能使用 64 位。知道如何正确实现上述缩放吗？

编辑

顺便提一下，我正在研究 STM32 - 一种 32 位微 Controller ，其中执行 64 位乘法和除法的成本非常高。因此，我想避免使用它们。

Answer 1

您可以将比例视为以 1000 为基数的数字:value = value_high*1000 + value_low。分别计算 value_high 和 value_low 对 scaled 的贡献，将中间值存储为分数:scaled = scaled_int + scaled_remainder/max_value

uint32_t value_low = value%1000;
uint32_t value_high = value/1000;
uint32_t scaled_int, scaled_remainder;

uint32_t low = value_low * 1000000;
scaled_int = low / max_value;
scaled_remainder = low % max_value;

scaled_int += value_high * 810;  // pre-calculated 1000*1000000 / max_value
scaled_remainder += value_high * 730;  // pre-calculated 1000*1000000 % max_value
scaled_int += scaled_remainder / max_value;
scaled_remainder = scaled_remainder % max_value;

此外，您不必使用 base 1000，base 1024 可能会更快一些。只要第 4 行和第 8 行不溢出最大值，它就应该可以工作。