处理分数乘法中的溢出

Question

假设我想将 x 乘以 (3/8)。所以我可以使用如下移位操作得到结果（结果应该向零舍入）：

int Test(int x) {
    int value = (x << 1) + x;
    value = value >> 3;
    value =  value + ((x >> 31) & 1); 
    return  value;
}

所以我会在 Test(11) 中加入 4，在 Test(-9) 中加入 -3。问题是，因为我先做乘法，所以我会在某些范围内溢出，在那些情况下我不会得到正确的值：

Test(0x80000000)  // returns -268435455, but it should be -268435456

我该如何解决这个问题？

Answer 1

一种解决方案是以不同方式处理高半部分和低半部分。 x的高位先右移3，再乘以3。低位先乘以3，再右移3，然后将两个结果相加。这应该适用于积极的情况。对于负数，您需要稍微调整一下。

Answer 2

How can I fix this? (overflow at some ranges)

先除以8。

对于每 8 的倍数，结果正好增加 3。所以剩下的就是找出 3/8 的数字 -7 到 7，OP 的 test() 可以处理。可能的简化。

int Times3_8(int x) {
  int div8 = x/8;
  int value = div8*3 + Test(x%8);
}

Answer 3

int foo(int x)
{
    return x/8*3 + x%8*3/8;
}

受 chux 的回答启发：关键是先除以 8（为范围牺牲精度）并使用第二项来处理量化误差（纠正较小范围内的误差）。

Handling overflow in fraction multiplication