32位整数缩放,无溢出

您可以通过将比例视为基数1000来实现: value = value_high*1000 + value_low 计算 value_high 的和 value_low 对单独缩放的贡献,将中间值存储为分数: 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行没有溢出到其最大值,它就应该可以工作。

您可以申报 scaled 像 unsigned long long 键入如下内容(&P);然后相应地执行显式类型转换。

unsigned long long scaled = (unsigned long long)value * 1000000 / max_value; /* make either operand of unsigned long long type explicitly */
printf("%llu\n",scaled);

如果您的转换器可以支持64位,那么

uint32_t scaled =(uint32_t)((uint64_t)value * 1000000 / max_value);

如果支架浮动,则

uint32_t scaled =(uint32_t)(value *1.0 / max_value* 1000000);

将有一点精度损失。

缩放的最快方法是使用2个功率缩放因子。

即使有两个数字使用不同的比例因子进行缩放,算法也很简单。

示例:

uint32_t scaledDiv(uint32_t a, uint32_t b, uint32_t *sclef)
{
    *sclef = __builtin_clz(a);
    a <<= *sclef;
    return a/b;
}

问题的形式是: value/max_1 = x/1000000 。

如果不以封闭形式解决此问题 x 可以使用二分法迭代计算。

 uint32_t step=max_value>>1;
 uint32_t v=0, x=0, step2=1000000/2 << 12;
 // step2 has been scaled to add extra precision
 while(step) {
    if (value > v+step) { v+=step; x+=step2; }
    step>>=1; step2>>=1;
 }
 x=(x+2048)>>12; // scale down and round

结果将在32次迭代中完成。