以2的幂进行四舍五入除法

Question

我正在实现一本教科书中的量化算法。现在的进展还不错，但在四舍五入时出现了越界错误。教科书对此有这样的说明：

通过加上一个偏移量，然后向右移动 p 位，可以进行四舍五入的除法运算，除数是 2^p

我明白右移的意思，但他们说的偏移量到底是什么呢？

这是我的示例代码：

def scale(x, power2=16):
    if x < 0:
        return -((-x) >> power2)
    else:
        return x >> power2
def main():
    inp = [ 12595827, -330706, 196605, -387168, -274244, 377496, -241980, 
            -545272,  -196605, 24198,   196605,  193584, 104858, 424683,
            -40330,     41944 ]
    expect = [ 192, -5, 3, -6, -4, 5, -3, -8, -3, 0, 3, 3, 1, 6, 0, 0 ]
    actual = map(scale, inp)
    for i in range(len(expect)):
        if actual[i] == expect[i]:
            continue
        print 'inp: % 8d expected: % 3d actual: % 3d err: %d' % (inp[i], 
                expect[i], actual[i], expect[i] - actual[i])
if __name__ == '__main__':
    main()

我在检查负数输入，因为对负整数进行位移的结果似乎依赖于具体的实现。

我的输出结果是：

inp:   196605 expected:   3 actual:   2 err: 1
inp:  -387168 expected:  -6 actual:  -5 err: -1
inp:  -196605 expected:  -3 actual:  -2 err: -1
inp:   196605 expected:   3 actual:   2 err: 1
inp:   193584 expected:   3 actual:   2 err: 1

教科书提到的偏移量是什么，我该如何使用它来解决这个错误呢？

Answer 1

正如你所怀疑的，你的算法实际上并不是四舍五入，而是截断除法。而且，你的教科书里也有错误。所以即使你修正了你的算法，结果也可能不会如你所期望的那样。

为了确认结果确实有问题，你可以尝试用一个正确的、基于浮点数的四舍五入除法函数来运行你的代码：

def scale(x, power2=16):
    divider = float(1<<power2)
    result = round(x/divider)
    return result

然而，我们得到了以下错误：

inp:   377496 expected:   5 actual:   6 err: -1
inp:  -241980 expected:  -3 actual:  -4 err: 1
inp:   104858 expected:   1 actual:   2 err: -1
inp:   -40330 expected:   0 actual:  -1 err: 1
inp:    41944 expected:   0 actual:   1 err: -1

通过计算正确的四舍五入除法结果，我们可以确认这些期望实际上是错误的：

377496 / 65536 = 5,7601 -> should round to 6
104858 / 65536 = 1,600 -> should round to 2
-241980 / 65536 = -3,692 -> should round to -4
104858 / 65536 = 1,600 -> should round to 2
-40330 / 65536 = -0,6154 -> should round to -1
41994 / 65536 = 0,641 -> should round to 1

因此，如果你真正想要的是四舍五入除法，那么你期望的结果列表应该是：

expect = [ 192, -5, 3, -6, -4, 6, -4, -8, -3, 0, 3, 3, 2, 6, -1, 1 ]

Answer 2

把数字向右移动 p 位，相当于把这个数字除以 2 的 p 次方，然后向下取整，也就是只保留整数部分。

如果你想要除以 2 的 p 次方，并且四舍五入到最接近的整数，可以这样做：

shift-right by (p-1)
add 1
shift-right 1

在你的代码中：

def scale(x, power2=16):
    if x < 0:
        return -((((-x) >> (power2-1)) + 1) >> 1)
    else:
        return ((x >> (power2-1)) + 1) >> 1

Answer 3

移位操作会截断数据。移位是一种二进制运算符，这里我用方括号来表示基数：

196605[10] = 101111111111111111[2]
101111111111111111[2] >> 16[10] = 10[2] = 2[10]

为了正确地进行四舍五入，你需要在进行移位之前，先把除数的一半加上。

101111111111111111[2] + 1000000000000000[2] >> 16[10] = 110111111111111111[2] >> 16[10] = 11[2] = 3[10]