想要使用整数数学将int缩放为int

Question

我在SDCC 2.8.0上,因此内存和代码大小非常有限.假设我的输入值介于0到127之间,我想将其缩放到20 - 100.通常我会这样做:

int scale(int input, int min, int max)
{
 // assuming max is always greater than min
 float range = (float)max - (float)min;
 int output = min + int((range / 127.f) * (float)input);
 return output;
}

通过呼叫scale(64, 20, 100);我得到60,这正好是20到100之间的一半.

如何在不使用浮点数的情况下完成此操作？任何比特变幻魔术？

Answer 1

如果(max-min)<(INT_MAX/127)那么你可以(max-min)*input在除法之前天真地乘法/127
，否则，你将不得不分解操作以避免溢出和未定义的行为......

在后面的例子中，一个简单的可能性是将两个乘数除以 127。

A=Q1*127+R1
B=Q2*127+R2
A*B = (Q1*Q2*127 + Q1*R2 + Q2*R1) * 127 + R1*R2
(A*B)/127 = Q1*Q2*127 + Q1*R2 + Q2*R1 + (R1*R2/127)

或在 C:

unsigned int range=max-min;
unsigned int output = min
    + (range/127)*(input/127)*127
    + (range/127)*(input%127)
    + (range%127)*(input/127)
    + (range%127)*(input%127) / 127;

可以肯定的是，有更有效的位移公式>>8，编译器可能已经做得很好，但可能不太好，我们最好帮助他：

A=Q1*128+R1
B= 0*128+R2 (because B<=127)
A*B = (Q1*R2) * (127+1) + R1*R2
(A*B)/127 = Q1*R2 + (Q1*R2 + R1*R2)/127

在 C:
EDIT
Ahem 中，我的意图是除以 128，即 >>7，我错误地写了 >>8 余数相同，应该是 &0x7F 而不是 &0xFF
当然最好不要那么晦涩，只写 /128 和%128 因为我们现在可以信任编译器将这些操作转换为简单的位操作......

unsigned int range=max-min;
unsigned int high=(range / 128)*input;
unsigned int low =(range % 128)*input;
unsigned int output = min + high + (high+low)/127;

EDIT2
为了更好地平衡分布，我们可能会应用某种舍入而不是截断，如下所示：

unsigned int output = min + high + (high+low+63)/127;